/*
 * Name: Owen Sullivan
 * Date Submitted: 9/19/22
 * Lab Section: 006
 * Assignment Name: Lab 2: Infix to Postfix Coversion
*/

#include <iostream>
#include <string>
#include <stack>

using namespace std;

// Checks if string is an operator (as defined by assignment specifications).
// Includes check for parentheses, so function should be used alongside checks for/against
// parentheses to make sure algorithm handles parentheses correctly.
bool isOperator(const string &input) {

    if (input == "(" || input == ")" || input == "*" || input == "/" || input == "%" || input == "+" || input == "-") {

        return true;

    } else {

        return false;

    }

}

// Checks if string is a low precedence operator (as defined by assignment specifications),
// then returns 0 for low precedence and 1 for high precedence (all other operators).
// Returns int instead of bool so that <, <=, >, or >= comparisons can be made logically.
int precedence(const string &input) {

    if (input == "+" || input == "-") {

        return 0;

    } else {

        return 1;

    }

}

// Converts an infix arithmetic expression into postfix.
// The function takes 3 parameters.
// First parameter: Array of strings for infix expression;
//                  each string is either an integer number or operator symbol.
// Second parameter: Number of strings in infix expression.
// Third parameter: Array of strings for postfix expression;
//                  generated by function, same format as first parameter;
//                  assumes that postfix is at least the size of postfix.
// Return value: int, number of strings in postfix expression;
//               returns 0 if an error is encountered when converting expression.
//               An error occurs with a mismatched parenthesis, e.g. ( ( ) or ( ) ) etc.
// Operator symbols:
//     ( : left parenthesis, all operations between this and ")" take place first
//     ) : right parenthesis, all op.s back to previous "(" take place first
//     * : multiplication, higher precedence - takes place before "+" and "-"
//     / : division, higher precedence - takes place before "+" and "-"
//     % : remainder, higher precedence - takes place before "+" and "-"
//     + : addition, lower precedence - takes place after "*" , "/" , "%"
//     - : subtraction, lower precedence - takes place after "*" , "/" , "%"
// The function is not specified to work with any other operator symbols.
// Any string in infix may be assumed to be an integer operand if none
// of the above symbols.
int infixToPostfix(string infix[], int length, string postfix[]) {

    // Loop through infix array. Increment int for left
    // parentheses and decrement int for right parentheses.
    int balanced = 0;
    for (int infixPos = 0; infixPos < length; infixPos++) {

        if (infix[infixPos] == "(") {
            
            balanced++;
        
        } else if (infix[infixPos] == ")") {
            
            balanced--;
        
        }

        // If balanced int ever goes negative, the problem is inverted.
        if (balanced < 0) {

            return 0;

        }

    }

    // Check if parentheses are balanced by checking if
    // int is not equal to zero. Return zero if not, continue
    // if so.
    if (balanced != 0) {
        
        return 0;
    
    }

    // Create stack of type string for operator storage
    stack<string> operators;

    // Create int to hold length of postfix array, incremented as
    // values are added to postfix array. Returned by function.
    int postfixLength = 0;

    // Loop through infix array, with postfixPos incremented only if values
    // are added to postfix array (this is just for logical readability).
    for (int infixPos = 0, postfixPos = 0; infixPos < length; infixPos++) {

        // Check if value in infix is operand (number / not an operator).
        // Add to postfix array if so.
        if (!isOperator(infix[infixPos])) {

            postfix[postfixPos] = infix[infixPos];

            postfixPos++;
            postfixLength++;

          // Check if value in infix is an open parentheses. Add to operators
          // stack if so.
        } else if (isOperator(infix[infixPos]) && infix[infixPos] == "(") {

            operators.push(infix[infixPos]);

          // Check if value in infix is an operator other than either parentheses.
          // Compare precedence of value against top of operators stack, and add to
          // postfix array and pop operators stack if high precedence. Regardless,
          // push value in infix to operators stack.
        } else if (isOperator(infix[infixPos]) && infix[infixPos] != "(" && infix[infixPos] != ")") {

            while (!operators.empty()) {
                
                if ((precedence(infix[infixPos]) <= precedence(operators.top())) && operators.top() != "(") {

                    postfix[postfixPos] = operators.top();
                    operators.pop();

                    postfixPos++;
                    postfixLength++;

                } else {

                    break;

                }

            }

            operators.push(infix[infixPos]);

          // Check if value in infix is close parentheses. If top of operators
          // stack is a an open parentheses, pop the stack. If not, add top of
          // stack to postfix array and pop stack.
        } else if (isOperator(infix[infixPos]) && infix[infixPos] == ")") {

            while (!operators.empty()) {

                if (operators.top() != "(") {

                    postfix[postfixPos] = operators.top();
                    operators.pop();

                    postfixPos++;
                    postfixLength++;

                } else {

                    operators.pop();
                    break;

                }

            }

        }

    }

    // Create ints to hold current operators stack size and stack pos to
    // be incremented (for adding to existing values in postfix array).
    int stackLength = operators.size();
    int operatorsPos = 0;

    // Loop until operators stack is empty. Add top of stack to postfix
    // array and pop stack.
    while (!operators.empty()) {

        postfix[postfixLength + operatorsPos] = operators.top();
        operators.pop();

        operatorsPos++;

    }

    // Add the length of the operators stack prior to loop to current
    // length of postfix.
    postfixLength = postfixLength + stackLength;

    return postfixLength;

}

// Main function to test infixToPostfix().
// Should convert 2 + 3 * 4 + ( 5 - 6 + 7 ) * 8
//             to 2 3 4 * + 5 6 - 7 + 8 * +
// int main() {

//     string infixExp[] = {"2", "+", "3", "*", "4", "+", "(",
//                          "5", "-", "6", "+", "7", ")", "*",
//                          "8"};
//     string postfixExp[15];
//     int postfixLength;

//     cout << "Infix expression: ";
//     for (int i=0; i<15; i++) {
        
//         cout << infixExp[i] << " ";

//     }
//     cout << endl;
//     cout << "Length: 15" << endl << endl;

//     postfixLength = infixToPostfix(infixExp, 15, postfixExp);

//     cout << "Postfix expression: ";
//     for (int i=0; i<postfixLength; i++) {
        
//         cout << postfixExp[i] << " ";

//     }
//     cout << endl;
//     cout << "Length: " << postfixLength << endl;
    
//     return 0;

// }