Algorithm: Postfix Evaluation
This algorithm finds the VALUE of an arithmetic expression P written in postfix notation.
1. Add a right parenthesis “)” at the end of P. [to indicate the end of expression]
2. Scan P from left to right and repeat steps 3 and 4 for each element of P until the “)” is
encountered.
3. If an operand is encountered, PUSH it on STACK.
4. If an operator © is encountered, then.
a. POP the element and store it into B.
b. POP the element and store it into A
c. Evaluate A © B
d. PUSH the result on STACK.
5. Set VALUE equal to the top element on STACK.
6. Exit.
Algorithm: Prefix Evaluation
This algorithm finds the VALUE of an arithmetic expression P written in prefix notation.
1. Reverse the prefix expression.
2. Add a right parenthesis “)” at the end of P. [to indicate the end of expression]
3. Scan P from left to right and repeat steps 3 and 4 for each element of P until the “)” is
encountered.
4. If an operand is encountered, PUSH it on STACK.
5. If an operator © is encountered, then.
a. POP the element and store it into A.
b. POP the element and store it into B.
c. Evaluate A © B
d. PUSH the result on STACK.
6. Set VALUE equal to the top element on STACK.
7. Exit.
Algorithm: REVERSE POLISH(Q,P) – Infix to postfix
Suppose Q is an arithmetic expression written in infix notation. This algorithm finds the
equivalent postfix expression P
1. PUSH “(“ onto STACK, and add “)” to the end of Q.
2. Scan Q from left to right and repeat Steps 3 to 6 for each element of Q until the STACK is
empty.
3. If an operand is encountered append it to P.
4. If a left parenthesis is encountered, PUSH it onto STACK.
5. If an operator © is encountered, then.
a. Repeatedly POP from STACK add append to P each operator,
i. which has the higher precedence than ©
ii. which has same precedence and left to right associativity.
b. PUSH © to the STACK
6. If a right parenthesis is encountered, then.
a. Repeatedly POP from STACK and append to P each operator until a left
parenthesis is encountered.
b. POP the left parenthesis [Don’t append this to P]
7. Exit
Algorithm: POLISH (Q, P) – Infix to prefix
Suppose Q is an arithmetic expression written in infix notation. This algorithm finds the
equivalent prefix expression P.
1. REVERSE the infix expression.
2. PUSH “(“ onto STACK, and add “)” to the end of Q.
3. Scan Q from left to right and repeat Steps 3 to 6 for each element of Q until the STACK is
empty.
4. If an operand is encountered append it to P.
5. If a left parenthesis is encountered, PUSH it onto STACK.
6. If an operator © is encountered, then.
a. Repeatedly POP from STACK add append to P each operator,
i. which has the higher precedence than ©
b. which has same precedence and right to left associativity.
c. PUSH © to the STACK
7. If a right parenthesis is encountered, then.
a. Repeatedly POP from STACK and append to P each operator until a left
parenthesis is encountered.
b. POP the left parenthesis [Don’t append this to P]
8. Exit