/******************************************************************************
Dr. K Zemoudeh, Date: 1/12/98, File: exprEval.cpp

Modified RJBotting Sun Nov  7 08:12:17 PST 2004

This programs evaluates simple expressions that consist of whole
numbers, -, +, *,
/, ^ (exponentiation), ), and ( operators.

Each expression is input with values and operators separated by white space
and must be terminated by an equal sign.

It performs little error checking, and assumes all operators are left to right
associative. ^ has the highest precedence, * and / are at the next lower level,
and + and - are at the lowest precedence.

This program illustrates the use of Stack data structure.
******************************************************************************/

#include <string>
#include <cstdlib>      // for atoi(), exit(), and EXIT_FAILURE
#include <iostream>
#include <cmath>        // for pow()
#include <typeinfo>

#include "stack.h"

using namespace std;


// Functions used in main program
    void evaluate(Stack& operand, Stack& oprator);
    int convert(string);
    bool isOperator(string);
    int intValue(string);

main()
{
  try{
    Stack operand, oprator; // 'operator' is a special C++ word.
    int op; // integer equivalent of the operator returned from convert()
    string token;

    cout << "input an expression ending with =. Separate integers and operators.\n";
    cin >> token;
    while (token != "=")
    {   if (isOperator(token))
            if (token == ")")
            {   while (oprator.top() != 6) // 6 == "("
                    evaluate(operand, oprator);
                oprator.pop(); // pop "("
            } else
            {   op = convert(token);
                while (!oprator.empty() && oprator.top() != 6 && op <= oprator.top())
                    evaluate(operand, oprator);
                oprator.push(op);
            }
        else // token is a number
            operand.push(intValue(token));
        cin >> token;
    }
    while (!oprator.empty())
        evaluate(operand, oprator);
    cout << operand.top() << endl;
    operand.pop();
   }
   catch(exception &e)
   {
	cerr<< "Exception thrown: "<< typeid(e).name()<< " " << e.what()<<endl;
   }
} // main

/******************************************************************************
This function pops 2 operands and one operator, evaluates, and pushs
the result back on the operand stack
******************************************************************************/
void evaluate(Stack& operand, Stack& oprator)
{   int operand1, operand2;
    int op;
    int result;

    operand2 = operand.top(); operand.pop();
    operand1 = operand.top(); operand.pop();
    op = oprator.top(); oprator.pop();
    switch (op)
    {   case 1: result = operand1 + operand2;
                break;
        case 2: result = operand1 - operand2;
                break;
        case 3: result = operand1 * operand2;
                break;
        case 4: result = operand1 / operand2;
                break;
        case 5: result = (int)(pow((double)operand1, operand2));
                break;
        default: cerr << "Invalid operator on stack: " << op << endl;
                 exit(EXIT_FAILURE);
    }
    operand.push(result);
} // evaluate


/******************************************************************************
This function encodes operators to integers. This function is needed because
our Stack (in Stack.h) can only hold integers.
******************************************************************************/
int convert(string s)
{   if (s == ")") return 0;
    if (s == "+") return 1;
    if (s == "-") return 2;
    if (s == "*") return 3;
    if (s == "/") return 4;
    if (s == "^") return 5;
    if (s == "(") return 6;
    cerr << "Invalid operator read: " << s << endl;
    exit(EXIT_FAILURE);
} // convert


// returns true if s is an operator
bool isOperator(string s)
{    return s == ")" || s == "+" || s == "-" || s == "*" || s == "/" ||
            s == "^" || s == "(";
} // isOperator


// returns integer representation of string s; assumes s is all digits
int intValue(string s)
{    return atoi(s.c_str()); // atoi means ASCII to int, from <cstdlib>
} // intValue