1  #include <iostream>
  2  #include <vector>
  3  #include <string>
  4  #include <cctype>
  5  #include "ImprovedStack.h"
  6  
  7  using namespace std;
  8  
  9  // Split an expression into numbers, operators, and parenthese
 10  vector<string> split(const string& expression);
 11  
 12  // Evaluate an expression and return the result
 13  int evaluateExpression(const string& expression);
 14  
 15  // Perform an operation
 16  void processAnOperator(
 17    Stack<int>& operandStack, Stack<char>& operatorStack);
 18  
 19  int main()
 20  {
 21    string expression;
 22    cout << "Enter an expression: ";
 23    getline(cin, expression);
 24  
 25    cout << expression << " = " 
 26      << evaluateExpression(expression) << endl;
 27  
 28    return 0;
 29  }
 30  
 31  vector<string> split(const string& expression)
 32  {
 33    vector<string> v; // A vector to store split items as strings
 34    string numberString; // A numeric string
 35  
 36    for (unsigned int i = 0; i < expression.length(); i++)
 37    {
 38      if (isdigit(expression[i]))
 39        numberString.append(1, expression[i]); // Append a digit
 40      else
 41      {
 42        if (numberString.size() > 0)
 43        {
 44          v.push_back(numberString); // Store the numeric string
 45          numberString.erase(); // Empty the numeric string
 46        }
 47  
 48        if (!isspace(expression[i]))
 49        {
 50          string s;
 51          s.append(1, expression[i]);
 52          v.push_back(s); // Store an operator and parenthesis
 53        }
 54      }
 55    }
 56  
 57    // Store the last numeric string
 58    if (numberString.size() > 0)
 59      v.push_back(numberString);
 60  
 61    return v;
 62  }
 63  
 64  // Evaluate an expression 
 65  int evaluateExpression(const string& expression)
 66  {
 67    // Create operandStack to store operands
 68    Stack<int> operandStack;
 69  
 70    // Create operatorStack to store operators
 71    Stack<char> operatorStack;
 72  
 73    // Extract operands and operators
 74    vector<string> tokens = split(expression);
 75  
 76    // Phase 1: Scan tokens
 77    for (unsigned int i = 0; i < tokens.size(); i++)
 78    {
 79      if (tokens[i][0] == '+' || tokens[i][0] == '-')
 80      {
 81        // Process all +, -, *, / in the top of the operator stack
 82        while (!operatorStack.empty() && (operatorStack.peek() == '+'
 83         || operatorStack.peek() == '-' || operatorStack.peek() == '*'
 84         || operatorStack.peek() == '/'))
 85        {
 86          processAnOperator(operandStack, operatorStack);
 87        }
 88  
 89        // Push the + or - operator into the operator stack
 90        operatorStack.push(tokens[i][0]);
 91      }
 92      else if (tokens[i][0] == '*' || tokens[i][0] == '/')
 93      {
 94        // Process all *, / in the top of the operator stack
 95        while (!operatorStack.empty() && (operatorStack.peek() == '*'
 96          || operatorStack.peek() == '/'))
 97        {
 98          processAnOperator(operandStack, operatorStack);
 99        }
100  
101        // Push the * or / operator into the operator stack
102        operatorStack.push(tokens[i][0]);
103      }
104      else if (tokens[i][0] == '(')
105      {
106        operatorStack.push('('); // Push '(' to stack
107      }
108      else if (tokens[i][0] == ')')
109      {
110        // Process all the operators in the stack until seeing '('
111        while (operatorStack.peek() != '(')
112        {
113          processAnOperator(operandStack, operatorStack);
114        }
115  
116        operatorStack.pop(); // Pop the '(' symbol from the stack
117      }
118      else
119      { // An operand scanned. Push an operand to the stack as integer
120        operandStack.push(atoi(tokens[i].c_str()));
121      }
122    }
123  
124    // Phase 2: process all the remaining operators in the stack
125    while (!operatorStack.empty())
126    {
127      processAnOperator(operandStack, operatorStack);
128    }
129  
130    // Return the result
131    return operandStack.pop();
132  }
133  
134  // Process one opeator: Take an operator from operatorStack and 
135  // apply it on the operands in the operandStack 
136  void processAnOperator(
137      Stack<int>& operandStack, Stack<char>& operatorStack)
138  {
139    char op = operatorStack.pop();
140    int op1 = operandStack.pop();
141    int op2 = operandStack.pop();
142    if (op == '+')
143      operandStack.push(op2 + op1);
144    else if (op == '-')
145      operandStack.push(op2 - op1);
146    else if (op == '*')
147      operandStack.push(op2 * op1);
148    else if (op == '/')
149      operandStack.push(op2 / op1);
150  }