#include <string>
#include <vector>
#include <cstdlib>
#include "genericLinkedListStack.h"

using namespace std;

vector<string> convert2Vec(string line) //done
{
    //convert the string to put into a vector
    vector<string> equation;
    for(int i=0; i<line.size(); i++){
        if(line[i] != ' '){
            if((equation.size() != 0)  && (line[i] >= '0') && (line[i] <= '9') ){
                if(line[i-1] >= '0' && line[i-1] <= '9'){
                    equation[equation.size()-1] += line[i];
                } else {
                    equation.push_back(string(1,line[i]));
                }
            } else {
                equation.push_back(string(1,line[i]));
            }
        }
    }
    return equation;
}

/*
returns:
    0 = has no addition or subtraction, but has multiplication or division
    1 = has addition or subtraction
    2 = has parenthesis at the start and end of the array
*/
int hasAddSub(vector<string> equation, int start, int end)
{
    int bracket =0, count =0;
    for(int i=0; i<equation.size(); i++){
        if(equation[i] == "("){
            bracket++;
        }else if(equation[i] == ")" ){
            bracket--;
        }else if(bracket == 0){
            if((equation[i] == "+")||(equation[i] == "-")) return 1;
            if((equation[i] == "*")||(equation[i] == "/")) count++;
        }
    }

    if(count != 0){
        return 0;
    }
    return 2;
}

int isOp(string val)
{
    if((val == "+")||(val == "-")) return 1;
    if((val == "*") || (val == "/")) return 2;
    return 0;
}

void recPostfix(string& posfix, const vector<string>& equation, int start, int end)
{
    //base case:
    if(start == end){
        posfix = equation[start] + posfix;
        return;
    }

    int bracket = 0, index = 0;
    int addSub = hasAddSub(equation, start, end);

    //if there are parenthesis around the whole equation
    if(addSub == 2){
        start++;
        end--;
        addSub = hasAddSub(equation, start, end);
    }

    //finds a middle operator
    for(int i=end; i>=start; i--){
        if(equation[i] == "("){
            bracket++;
        }else if(equation[i] == ")" ){
            bracket--;
        } else if( bracket == 0 && isOp(equation[i])!=0){
            if(addSub == 1){
                if(isOp(equation[i]) == 1){
                    index = i;
                    break;
                }
            }else{ //theres no addition/subtraction
                index = i;
                break;
            }
        }
    }

    posfix = equation[index] + posfix;
    //recurse towards the end of the array:
    recPostfix(posfix, equation, index+1, end);
    //recurse towards the front of the array:
    recPostfix(posfix, equation, start, index-1);
}

string getPostfix(string line)
{
    //do not have to use genericLinkedList Stack
    vector<string> equation = convert2Vec(line);
    string posfix = "";
    recPostfix(posfix, equation, 0, equation.size()-1);
    return posfix;
}

int main(int argc, char** argv)
{
    //vector<string> equation = convert2Vec(argv[1]);

    /*int bracket = 0, index = 0, start = 0, end = equation.size()-1;
    int addSub = hasAddSub(equation, start, end);

    //if there are parenthesis around the whole equation
    if(addSub == 2){
        start++;
        end--;
        addSub = hasAddSub(equation, start, end);
    }

    //finds a middle operator
    for(int i=end; i>=start; i--){
        if(equation[i] == "("){
            bracket++;
        }else if(equation[i] == ")" ){
            bracket--;
        } else if( bracket == 0 && isOp(equation[i])!=0){
            if(addSub == 1){
                if(isOp(equation[i]) == 1){
                    index = i;
                    break;
                }
            }else{ //theres no addition/subtraction
                index = i;
                break;
            }
        }
    }*/
    cout << getPostfix(argv[1]) << endl;

    return 0;
}