The following algorithm transforms the infix expression X into its equivalent postfix expression Y. The algorithm uses a stack to temporarily hold operators and left parentheses. The postfix expression Y will be constructed from left to right using the operands from X and the operators which are removed from STACK.
We begin by pushing a left parenthesis onto STACK and adding a right parenthesis at the end of X. The algorithm is completed when STACK is empty.
Suppose X is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix expression Y. 1. push "(" onto stack, and add ")" to the end of X. 2. scan X from left to right and repeat Steps 3 to 6 for each element of X until the STACK is empty : 3. if an operand is encountered, add it to Y. 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 Y each operator (on the top of STACK) which has the same precedence as or higher precedence than operator. (b) Add operator to STACK. /*End of If structure */ 6. if a right parenthesis is encountered, then : (a) Repeatedly pop from STACK and add to Y 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 Y]. /* end of If structure */ /* end of Step 2 loop */ 7. exit.
This is an Algorithm to Convert Infix expression to Postfix. If you have any questions then comment below.
1 thought on “Algorithm to convert infix expression to postfix form”
conversion from prefix to postfix evaluation.