Stacks can be used to evaluate expressions.
Stacks have many applications. This section gives an application of using stacks. You can enter an arithmetic expression from Google to evaluate the expression as shown in Figure 12.3.
How does Google evaluate an expression? This section presents a program that evaluates a compound expression with multiple operators and parentheses (e.g., (15 + 2) * 34 – 2). For simplicity, assume that the operands are integers and operators are of four types: +, -, *, and /.
The problem can be solved using two stacks, named operandStack and operatorStack, for storing operands and operators, respectively. Operands and operators are pushed into the stacks before they are processed. When an operator is processed, it is popped from operatorStack and applied on the first two operands from operandStack (the two operands are popped from operandStack). The resultant value is pushed back to operandStack.
The algorithm takes two phases:
Phase 1: Scanning expression
The program scans the expression from left to right to extract operands, operators, and the parentheses.
- If the extracted item is an operand, push it to operandStack.
- If the extracted item is a + or – operator, process all the operators at the top of operatorStack with higher or equal precedence (i.e., +, -, *, /), push the extracted operator to operatorStack.
- If the extracted item is a * or / operator, process all the operators at the top of operatorStack with higher or equal precedence (i.e., *, /), push the extracted operator to operatorStack.
- If the extracted item is a ( symbol, push it to operatorStack.
- If the extracted item is a ) symbol, repeatedly process the operators from the top of operatorStack until seeing the ( symbol on the stack.
Phase 2: Clearing stack
Repeatedly process the operators from the top of operatorStack until operatorStack is empty.
Table 12.2 shows how the algorithm is applied to evaluate the expression (1 + 2) * 4 – 3.
Listing 12.11 gives the program
Listing 12.11 EvaluateExpression.cpp
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 parentheses
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 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 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 }
The program reads an expression as a string (line 23) and invokes the evaluateExpression function (line 26) to evaluate the expression.
The evaluateExpression function creates two stacks operandStack and operatorStack (lines 68, 71) and invokes the split function to extract numbers, operators, and parentheses from the expression (line 74) into tokens. The tokens are stored in a vector of strings. For example, if the expression is (13 + 2) * 4 – 3, the tokens are (, 13, +, 2, ), *, 4, -, and 3.
The evaluateExpression function scans each token in the for loop (lines 77-122). If a token is an operand, push it to operandStack (line 120). If a token is a + or – operator (line 79), process all the operators from the top of operatorStack if any (lines 81-87) and push the newly scanned operator to the stack (line 90). If a token is a * or / operator (line 92), process all the * and / operators from the top of operatorStack if any (lines 95-99) and push the newly scanned operator to the stack (line 102). If a token is a ( symbol (line 104), push it to operatorStack. If a token is a ) symbol (line 108), process all the operators from the top of operatorStack until seeing the ) symbol (lines 111-114) and pop the ) symbol from the stack (line 116).
After all tokens are considered, the program processes the remaining operators in operatorStack (lines 125-128).
The processAnOperator function (lines 136-150) processes an operator. The function pops the operator from operatorStack (line 139) and pops two operands from operandStack (lines 140-141). Depending on the operator, the function performs an operation and pushes the result of the operation back to operandStack (lines 143, 145, 147, 149).
Source: Liang Y. Daniel (2013), Introduction to programming with C++, Pearson; 3rd edition.