/************************************************/
/*                                              */
/* COSC 1337, CS2, Unix/C++,                    */
/* Lamar University,            Chung-Chih Li   */
/*                                Oct-19-2004   */
/************************************************/              
#include <iostream>
#include <string>
#include <vector>
#include <deque>
using namespace std;

struct token 
{
    int value;    // The value of operand or ascii of an operator
    int priority; // 0 means operand 
};

int main()
{
    string expression;
    deque<token> token_string(0);
    vector<token> op_stack(0);
    vector<int> value_stack(0);
    token k;
    int i, value=0;

    cout << "\nInput an Arithmetic Expression:\n\n";
    cin >> expression;
    
    k.value = 0;
    k.priority = -1;            // In case the 1st token is not a number, 
                                // make it to nonzero, so no extra token will
                                // be pushed at lines 45-46;
    for (i=0; i<expression.length(); i++)
    {
        if ('0' <= expression[i] && expression[i] <= '9')
        {
            k.priority = 0;
            k.value = k.value*10+(expression[i]-'0');
            continue;           // Only if the next character is not a
                                // digit, we complete reading a whole number
                                // and push_back the token; 
        }
        if (k.priority == 0)            // Previous token is a number;
            token_string.push_back(k);  // which is not pushed back yet;

        switch (expression[i])          // Define appropriate priority
        {
        case '+' :
        case '-' : k.value = expression[i];
                   k.priority = 10;
                   break;
        case '*' :
        case '/' : k.value = expression[i];
                   k.priority = 20;
                   break;
                   break;
        case '(' : k.value = expression[i];
                   k.priority = 30;
                   break;
        case ')' : k.value = expression[i];
                   k.priority = 5;
                   break;
        }
     
        token_string.push_back(k);      // This token is an operator or (,) 
        k.value =  0;                   // Make it ready for next number, if any 
        
    } // end for loop
    
    if (k.priority == 0)                // The last token is a number,  
        token_string.push_back(k);      // which is not pushed back yet. 

    k.value = 0;                        // Prepare a token to indicate the
    k.priority = 1;                     // end of the expression;
    token_string.push_back(k); 

    // Now, the input string is prepared as a token string
    // stored in token_string, which is a deque.
    // We are ready to evaluate the expression.

    while (0 < token_string.size())
    {
        k = token_string[0];
        token_string.pop_front();
        if (k.priority==0)                  // This token is an operand;
        {                                   // nothing to be done but putting
            value_stack.push_back(k.value); // it into the value stack;
            continue;                       // then, continue to read next
        }                                   // token.
        
                                            // Now, k is an operator or (,)
        int top = op_stack.size();          
        if (top == 0)                       // operator stack is empty;
        {
            if (k.value == '(')             // 
                k.priority=5;               // Change to the lowest before 
            op_stack.push_back(k);          // push back;
            continue;
        }

        top--;                               // index 
        if (op_stack[top].priority < k.priority)
        {
            if (k.value == '(') 
                k.priority=5;             // In the stack, '(' priority is lowest;
            op_stack.push_back(k);        
            continue;
        }    
        
        // Now, the priority of k is smaller than the priority of the one
        // on the top of of stack; so we put it back to the token string;
        token_string.push_front(k);             // Evaluate k next time;

        // The following evaluates one op on top of the op_stack;
        k = op_stack[top];
        if (k.value == '(')
        {
            if (token_string[0].value == ')')   // A pair of (, ) matched,
            {                                   // we simply remove
                op_stack.pop_back();            //  ( from op_stack, and
                token_string.pop_front();       //  ) from token string.
                continue;
            }
            else // Error
            {
                cout << "\n\nIll expression!!\n\n"; return 0;
            }
        }
        
        int a,b,c;                      // Evaluate a = b op c, where op is
                                        // saved in k.value;
                                        
        if (value_stack.size() < 2)             // Assume all operators are binary 
        {                                       // operator. Thus, if there are fewer
            cout << "\n\nIll Expression!!\n\n"; // than 2 operands, thing goes wrong
            return 0;                            
        }
        
        c = value_stack[value_stack.size()-1];  // Get value for c
        value_stack.pop_back();
        b = value_stack[value_stack.size()-1];  // Get value for b
        value_stack.pop_back();         

        switch (k.value)                        // Find appropriate operation
        {
        case '+' : a = b+c; break;
        case '-' : a = b-c; break;
        case '*' : a = b*c; break;
        case '/' : a = b/c; break;
        default  : cout << "\n\nIll expression!!\n\n"; return 0;
        }
        op_stack.pop_back();                    // This operator is done
        value_stack.push_back(a);               // Save the result;
        
    } // end while loop
    
    value = value_stack[0];                     // This is the final result.                     
    cout << "= " << value << endl << endl;
    return value;
}