FOR FREE CONTENT
Prefix to Infix conversion using Stack
Back to ProgrammingDescription
Introduction:
In a prefix expression, the operator appears in the expression before the operands. The form of a prefix expression is (OperatorOperand1Operand2).
For example,*+AB-CD.
In an infix expression, the operator appears in the expression in between the operands. The form of an infix expression is (Operand1OperatorOperand2).
For example, (A+B)*(C-D).
Procedure to convert a prefix expression into infix expression using stack data structure:
Let us consider a prefix expression*+AB-CD.
prefix=”*+AB-CD”.
First , we start by parsing the expression from right to left.
The top of the stack contains the infix expression.
infix=”((A+B)*(C-D))”
Algorithm
Algorithm:
Input:
Prefix expression prefix.
Output:
Infix expression infix.
Algo:
Step 1: Start.
Step 2: Defining theprefix2Infix(prefix) function
l Set infix←””.
l Set stack←[].
l Set i←length(prefix)-1.
l Repeat substeps while i != -1
(a) Set symbol←prefix[i].
(b) If symbol is an operator then,
u Set op1←stack.pop().
u Set op2←stack.pop().
u stack.push(“(“+op1+symbol+op2+”)”).
(c) Else then,
u stack.push(symbol).
(d) Set i←i-1.
l Set infix←stack.pop().
l Return infix.
Step 3: Stop.
Code
Application:
Computers usually perform computation in prefix or postfix, but for humans, it is much easier to understand an infix expression rather than a prefix.
Complexity:
(a) Time Complexity:
In prefix to infix conversion, the processes that are involved are traversing the prefix expression in reverse and pushing them all into stack which requiresO(n) and then popping them one by one which requires O(n), thus the time complexity is O(n) where n is the length of the prefix expression.
(b) Space Complexity:
In prefix to infix conversion, where the prefix expression is of length n, the space complexity is O(n).
