Algorithm to convert an Infix expression into Postfix expression using Stack.
1. Push “(“onto Stack, and add “)” to the end of X.
2. Scan X from left to right and repeat Step 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:
1. 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.
2. Add operator to Stack.
[End of If]
6. If a right parenthesis is encountered ,then:
1. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) until a left
parenthesis is encountered.
2. Remove the left Parenthesis.
[End of If]
[End of If]
7. END.
Conversion of Infix to Prefix Using Stack
1. Create an empty stack and an empty output string.
2. Reverse the infix expression: Reverse the order of all elements in the infix expression, including
operands and operators.
3. Iterate through the reversed infix expression from left to right.
4. If the current character is an operand (number or variable), append it to the output string.
5. If the current character is a closing bracket ‘)’, push it onto the stack.
6. If the current character is an operator or an opening bracket ‘(‘, compare its precedence with the
precedence of the operator at the top of the stack.
7. If the current operator has higher precedence than the operator at the top of the stack or the stack is
empty, push the current operator onto the stack.
8. If the current operator has lower or equal precedence than the operator at the top of the stack, pop the
operators from the stack and append them to the output string until an operator with lower precedence
is encountered or the stack becomes empty. Then push the current operator onto the stack.
9. If the current character is an opening bracket ‘(‘, pop the operators from the stack and append them to
the output string until the corresponding closing bracket ‘)’ is encountered.
10. Repeat steps 4 to 9 until all characters in the reversed infix expression have been processed.
11. Pop the remaining operators from the stack and append them to the output string.
12. Discard the closing bracket.
13. Reverse the output string to obtain the prefix expression.
