Evaluating the infix notation of the arithmetic expression, 1 + 2 * 3 is 7. What if my intention is for 1 + 2 to be calculated first, then I would have the answer, 9. In order to do that, we need to insert a pair of brackets into the arithmetic expression, i.e. (1 + 2) * 3. The two brackets seem to solve my need; however, it also increases the computer resources and computational time. In order not to include the brackets in the arithmetic expression and also be able to calculate the arithmetic expression in the intended order, we can simply rewrite the arithmetic expression from infix notation to postfix notation, i.e. from 1 + 2 * 3 (infix) to 1 2 3 * + (postfix).
After changing the infix notation of the arithmetic expression to postfix notation, then we can use Stack to calculate the answer. You can use the following algorithms for this assignment.
Infix: (8 + 2 * 5) / (1 + 3 * 2 - 4)
Postfix: 8 2 5 * + 1 3 2 * + 4 - /
Array S = (8 + 2 * 5) / (1 + 3 * 2 - 4)
Let x be the element at the top of the stack.
i = 0;
WHILE S[i] not end of string
If S[i] is (, then push S[i] on to the stack
If S[i] is a number, then enqueue S[i]
If S[i] is )
Pop the stack, if x is an operator, then enqueue x. Repeat this step until x is not an operator.
If S[i] is an operator (* or /),
Pop the stack,
i) if x is an operator (- or +), then, push x back to the stack and push S[i] to the stack as well.
ii) if x is an operator (* or /), then enqueue x. Continue to pop the stack and enqueue the x until x is +, - or (. Push x back to the stack and then push S[i] to the stack as well.
If S[i] is an operator (- or +),
Pop the stack, if x is an operator (+, -, *, /), then enqueue x. Repeat this step until x is not an operator. Push x back to the stack and then push S[i] to the stack as well.
Increment i by one
ENDWHILE
The purpose of this assignment is to learn how to use Stack and Queue to perform an effective arithmetic calculation. As for how to use Stack to evaluate the postfix arithmetic expression.