Question

Write an algorithm to convert an infix expression to a postfix expression. Execute your algorithm with the following infix expression as your input. 

(m + n)* (k + p) (g h) ↑ (a ↑ b c)

Answer 1

Algorithm: Polish (Q,P) 

Suppose Q is an arithmatic expression written in fix 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, add 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 and add to p each operator (on the top of stack) has the same precedence as or higher precedence than(b) add   to STACK.

6. If a right parenthesis is encountered, then:

(a) Repeatedly pop from STACK and add to P each operator (on the top of STACK) until a left parenthesis is encountered. 

(b) Remove the left parenthesis. [ Do not add the left parenthesis to P] 

[End of If structure.]

[End of Step 2 loop.] 

7. Exit

Example : 

Input (m+n)*(k+p)/(g/h)^(a^b/c)