FOR FREE YEAR SOLVED
Postfix to Infix Conversion
Back to ProgrammingDescription
Infix: The expression in which the operator appears in between the operands is known as infix expression. For example, (a+b), where a and b are operands, + is an operator that appears between the operands a and b.
Postfix: Similarly, the expression in which the operator appears after the operands is known as postfix expression. For example, ab+, where a and b are operands, + is an operator that appears after the operands a and b.
Postfix: AB + C * DE – FG + * -
Infix: (A+B) * C – (D-E) * (F+G)
Conversion from postfix to infix:
There is rules/algorithm for converting an expression from infix to postfix. The rules are:
- The infix expression should be scanned from left to right.
- If the symbol is an operand then it will be pushed into the stack.
- If the symbol is an operator then
a. Pop the top two operand op1, op2 from the stack.
b. Put the operator between two recently pop operand and form a string like (op1 + op2).
c. Push the resultant string into a stack.
4. After completion of the iteration when the stack contains only one string then we can treat this string as an infix expression.
5. Return the result.
Input: AB + C * DE – FG + * - (Postfix)
.png)
So, output: (A+B) * C - (D-E)*(F+G) (infix)
Code
Time complexity:
To convert postfix to infix we have to scan n symbols. So, the Time complexity for postfix to infix conversion is O(n).
Space complexity:
We require n stack to convert postfix to infix. So, space complexity is O(n).
Contributed by
