Repeat Programming Problem 6, but use the following algorithm to evaluate an infi x expression infi xExp. The algorithm uses two stacks: One stack opStack contains operators, and the other stack valStack contains values of operands and intermediate results. Note that the algorithm treats parentheses as operators with the lowest precedence.
for ( each character ch in infixExp)
{
switch (ch)
{
case ch is an operand, that is, a digit
valStack.push(ch)
break
case ch is a '('
opStack.push(ch)
break
case ch is an operator
if (opStack.isEmpty())
opStack.push(ch)
else if (precedence(ch) > precedence(opStack.peek()))
opStack.push(ch)
else
{
while (!opStack.isEmpty() and
precedence(ch)
Execute
opStack.push(ch)
}
break
case ch is a ')'
while (opStack.peek() is not a '(')
Execute
opStack.pop()
break
}
}
while (!opStack.isEmpty())
Execute
result = valStack.peek()
Note that Execute means:
operand2 = valStack.peek()
valStack.pop()
operand1 = valStack.peek()
valStack.pop()
op = opStack.peek()
opStack.pop()
result = operand1 op operand2
valStack.push(result)
Choose one of the following two approaches for your implementation:
• The operator stack opStack contains characters, but the operand stack valStack contains integers.
• The stack opStack contains integer codes that represent the operators, so both stacks contain integers.