Algorithm for converting infix expression to postfix form
Algorithm
POLISH (Q, P)
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, 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 P each operator (on the top of Stack) which has the same precedence as or higher precedence then ⛒.
(b) Add ⛒ to Stack.
[End of If structure.]
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
0 Comments