/*
 * Rick van der Zwet
 * 0433373
 * Scheme programming assigment 1a
 * Licence: BSD
 * $Id: exercise1b.cc 375 2007-12-10 23:02:34Z rick $
 */
#include <stdio.h>
#include <sysexits.h>
#include <iostream>
#include <string>

using namespace std;

/* Make good use of the predifined input of replace string */
string
sub_atoms (string input, const string rstring)
{
    size_t bi, ri;

    for (bi = 0; bi < input.length(); bi++) {
        if (input.at(bi) != ' ') {
            for (ri = 2; ri < rstring.length(); ri++) {
                if (input.at(bi) == rstring.at(ri)) {
                    input.replace(bi, 1, rstring, ri + 2, 1);
                    break;
                }
            }
        }
    }
    return(input);
}

string
substritute (string input, const string rstring)
{
    size_t cii;
    int brackets = 1;
    int start;
    string output;

    // Debug: cout << "Input: " << input << endl;

    /* Find the first bracket */
    start = input.find('(');

    /* Cool list has only atoms left start replacing */
    if (start == -1)
    return(sub_atoms(input, rstring));

    start++;
    /* Find closing bracket */
    for (cii = start; cii != input.length(); cii++) {
        if (input.at(cii) == '(')
            brackets++;
        else if (input.at(cii) == ')')
            brackets--;

        if (brackets == 0)
            break;
    }

    /* ... <start - 1=(> ... <cii=)> ... */
    // Debug: cout << "Output: " << input.substr(start, cii - start)  << endl;
    // Debug: cout << "start: " << start << " cii: " << cii << endl;

    /* Call recursive the front, the sub itself and the tail if found */
    if (start > 1)
        output += substritute(input.substr(0, start - 1), rstring);
    output += "(";
    output += substritute(input.substr(start, cii - start), rstring);
    output += ")";
    if (cii <= input.length())
        output += substritute(input.substr(cii + 1), rstring);

    return(output);
}

int
main (int argv, char * argc[])
{
    cout << "Expected: ((z (y c) d) z (f y))" << endl;
    cout << "Actual  : ";
    cout << substritute("((a (b c) d) a (f b))", "((a z) (b y))");
    cout << endl;
    return (EX_OK);
}