// cl /EHsc infixExpression4.cpp

#include "tStack4.h"
#include <iostream>
using std::cin;
using std::cout;
using std::endl;

void calculate(Stack<int> &operandStack, char op);
int precedence(char op1, char op2);
int readExpression(int data[]);

int main()
{
    int operand1, operand2, i, ndata, data[100];
    char op;
    Stack<int> operandStack(5);
    Stack<char> operatorStack(5);

    ndata = readExpression(data);

    try
    {
        for (i=0; i<ndata; i++)
        {
            if (data[i]>=0) // operand: 0~999
            {
                cout << data[i] << ' ';
                operandStack.push(data[i]);
            }
            else if (data[i] == -')')
            {
                while ((op = -operatorStack.top()) != '(')
                {
                    cout << op << ' ';
                    calculate(operandStack, op);
                    operatorStack.pop();
                }
                operatorStack.pop();
            }
            else if ((data[i] == -'(') ||
                     (precedence(data[i], operatorStack.top()) > 0))
                operatorStack.push(data[i]);
            else
            {
                do
                {
                    cout << (op=-operatorStack.top()) << ' ';
                    operatorStack.pop();
                    calculate(operandStack, op);
                }
                while (precedence(data[i], operatorStack.top()) <= 0);
                operatorStack.push(data[i]);
            }
        }
        while (!operatorStack.isEmpty())
        {
            cout << (op=-operatorStack.top()) << ' ';
            operatorStack.pop();
            calculate(operandStack, op);
        }
    
        cout << '\n' << operandStack.top() << '\n';
    }
    catch (push_out_of_range<char> &e)
    {
        cout << "\nOperator stack:" << e.what() << endl;
    }
    catch (push_out_of_range<int> &e)
    {
        cout << "\nOperand stack:" << e.what() << endl;
    }
    catch (pop_out_of_range<char> &e)
    {
        cout << "\nOperator stack:" << e.what() << endl;
    }
    catch (pop_out_of_range<int> &e)
    {
        cout << "\nOperand stack:" << e.what() << endl;
    }

    return 0;
}

int readExpression(int data[])
{
    char c;
    int ndata=0;
    while ((c=cin.get())!=EOF)
    {
        if (c == '\n')
            break;
        else if (c == ' ' || c == '\t')
            continue;
        else if ((c == '+') || (c == '-') || 
                 (c == '*') || (c == '/') || (c == '%') ||
                 (c == '(') || (c == ')') )
            data[ndata++] = -c;
        else
        {
            cin.unget();
            cin >> data[ndata++];
        }
    }
    return ndata;
}

int precedence(char op1, char op2)
{                                                    // 99: eos
    static char op[] = {'(', ')', '+', '-', '*', '/', '%', 99};
    static int isp[] = { 0, 19, 12, 12, 13, 13, 13, 0};
    static int icp[] = {20, 19, 12, 12, 13, 13, 13, 0};
    static int nops = sizeof(op)/sizeof(char);
    int indOP1, indOP2;
    for (indOP1=0; indOP1<nops; indOP1++)
        if (-op1 == op[indOP1]) break;
    for (indOP2=0; indOP2<nops; indOP2++)
        if (-op2 == op[indOP2]) break;
    return icp[indOP1] - isp[indOP2];
}


void calculate(Stack<int> &operandStack, char op)
{
    int operand1, operand2;
    operand1 = operandStack.top(); operandStack.pop();
    operand2 = operandStack.top(); operandStack.pop();
    if (op == '+')
        operandStack.push(operand1+operand2);
    else if (op == '-')
        operandStack.push(operand2-operand1);
    else if (op == '*')
        operandStack.push(operand1*operand2);
    else if (op == '/')
        operandStack.push(operand2/operand1); // integer division
    else if (op == '%')
        operandStack.push(operand2%operand1); // integer remainder
}

/*

23 * 312 + ( 525 - 411 ) 

23 312 * 525 411 - +
7290

2 * 3 + ( 5 - 4 )

2 3 * 5 4 - +
7


2 * 4 - 2 * 3 / ( 6 - 2 * 2 )

2 4 * 2 3 * 6 2 2 * - / -
5


1 - 2 * 3 / ( 6 - 5 * ( 1 + 2 * 2 - 3 ) % 7 )

1 2 3 * 6 5 1 2 2 * + 3 - * 7 % - / -
-1


1 - 2 * 3 / ( 6 - 5 * ( 1 + 2 * 2 - 3 ) % 7 )
1 2 3 * 6 5
Operator stack:Stack<>::push(): full stack

*/