/*	File:	InfixToPostfix.cpp

			Christer Karlsson


This code implements a function that changes
an infix expression to a postfix expression.

The following algorithm is used:
    * If the symbol is a variable, add it to the postfix string.
    * If the symbol is a left parenthesis '(', push it.
    * If the symbol is an operator, the operators on the stack are examined. 
         If an operator on the top of the stack has higher or equal 
         priority to the new operator, pop the operator on the stack 
         and add it to the postfix expression. 
         This is done until either a lower priority operator or a '('
         is reached, or the stack is empty. Then push the new operator.
    * If the token is a ')', pop everything up to the matching '(' 
         and add them to the postfix expression and pop the '('.
    * When the end of the infix expression is reached, pop all operators 
         off the stack and add them to the postfix expression.     

Allowed inputs are:

Operators: +,-,*,/,%
Operands : Chars								                            */

#include <iostream>
#include <stdlib.h>
#include <stack>

using namespace std;

int main(int argc, char *argv[])
{
    const int SIZE = 80;        // Max size of the buffer = 80
    char buffer[ SIZE ];
    int length=0;
    stack<char> operand;

    // Ask the user for an infix expression
    cout << "Enter an infix expression: ";
    cin.getline(buffer, SIZE);
    length= cin.gcount()-1;     // Get the length  of the buffer
                                // Subract one cause of the endl-character

    // Run the buffer from start to end.
    for (int i=0; i<length; i++)
    {
        // If ( or ) push if '(', else pop until a '(' is reached
        if (buffer[i]=='(' || buffer[i]==')')
        {
            if ( buffer[i]=='(' )
                operand.push(buffer[i]);
            else
            {
                while ( !operand.empty() && operand.top()!='(' )
                {
                    cout << operand.top();
                    operand.pop();
                }
                operand.pop();
            }
        }
        // If buffer[i] = /,*,%,+ or -
        // pop and output all operators >=, then push the operator on the stack
        else if (buffer[i]=='*' || buffer[i]=='/' || buffer[i]=='%')
        {
            // Pop of operators from the stack
            // Stop at +,-  or (
            while ( !operand.empty() && operand.top()!='(' && operand.top()!='+' && operand.top()!='-' )
            {
                cout << operand.top();
                operand.pop();
            }
            // Push the operand on the stack
            operand.push(buffer[i]);

        }
        else if (buffer[i]=='+' || buffer[i]=='-')
        {
            // Pop of operators from the stack
            // Stop at ( or end of stack
            while ( !operand.empty() && operand.top()!='(' )
            {
                cout << operand.top();
                operand.pop();
            }
            // Push the operand on the stack
            operand.push(buffer[i]);
        }
        // Print out the variables
        else
           cout << buffer[i];
    }
    // Empty the stack
    while ( !operand.empty() )
    {
         cout << operand.top();
         operand.pop();
    }
    // End of the program
    cout << endl;
    system("PAUSE");
    return 0;
}