Programming Problem C++:
Write a program to implement the algorithm for evaluating postfix expressions that involve only singledigit integers and the integer operations: +, - , *, and /. To trace the action of postfix evaluation, display each token as it is encountered, and display the action of each stack operation.
Your program should output an error message if the postfix expression is not well formed. I.e. not correct. For example given the expression 9 2 1 + / 4 * the output of your program should resemble the following: Token = 9 Push 9 Token = 2 Push 2 Token = 1 Push 1 Token = + Pop 1 Pop 2 Push 3 Token = / Pop 3 Pop 9 Push 3 Token = 4 Push 4 Token = * Pop 4 Pop 3 Push 12 Token = Pop 12 The algorithm for evaluating postfix expressions is given below. ALGORITHM TO EVALUATE POSTFIX EXPRESSIONS Each time an operand is encountered, it is pushed onto the stack.
When an operator is encountered, the top two values are popped from the stack, the operator applied to them, and the result pushed back onto the stack.
The following algorithm summarizes this procedure:
1. Initialize an empty stack
2. Repeat the following until the end of the expression is encountered: a) Get the next token (character, variable, arithmetic operator) in the postfix expression.
b) If token is an operand, push it onto the stack. If it is an operator, do the following:
i) Retrieve and pop the top two values from the operand stack. If the operand stack does not contain two items, an error due to a malformed postfix expression has occurred and evaluation is terminated.
ii) Apply the operator token to these two values. iii) Push the resulting value back onto the operand stack.
3. When the end of the expression is encountered, its value is on top of the stack (and in fact must be the only value in the stack).