In-fix- to Postfix Transformation:
Algorithms to convert from infix expression to postfix expression is
as follows:
1. Scan input string from left to right character by character.
2. If the character is an operand, put it into the output stack.
3. If the character is an operator and the operator's stack is empty,
push the operator into operators' stack.
4. If the operator's stack is not empty, there may be the following
possibilities.
a. If the precedence of the scanned operator is greater than the
top most operator of the operator's stack, push this operator
into the operator stack.
b. If the precedence of the scanned operator is less than or
equal to the top most operator of operator's stack, pop the
operators from operator stack until we find a lower
precedence operator than the scanned character. Never pop
out ( '(' ) or ( ')' ) whatever may be the precedence level of
scanned character.
c. If the character is an opening round bracket ( '(' ), push it
into the operator's stack.
d. If the character is a closing round bracket ( ')' ), pop out
operators from operator's stack until we find an opening
bracket ('(' ).
e. Now pop out all the remaining operators from the
operator's stack and push into the output stack.
Examples
1. (A+B)*(C-D)
2. a+b*(c^d-e)^(f+g*h)-i
3. (A+B)/(C-D)-(E-F)
4. K + L - M*N + (O^P) * W/U/V * T + Q
Convert the following infix expression A + B * C – D/H*G into its
equivalent postfix expression.
Infix to Postfix Table
Sr No Expression Stack Postfix
0 a a
1 + + a
2 b + ab
3 * +* ab
4 c +* abc
5 - - abc*+
6 d - abc*+d
7 abc*+d-
Source Code:
# Python program to convert infix expression to postfix
# Function to return precedence of operators
def prec(c):
if c == '^':
return 3
elif c == '/' or c == '*':
return 2
elif c == '+' or c == '-':
return 1
else:
return -1
# Function to perform infix to postfix conversion
def infixToPostfix(s):
st = []
result = ""
for i in range(len(s)):
c = s[i]
# If the scanned character is
# an operand, add it to the output string.
if (c >= 'a' and c <= 'z') or (c >= 'A' and c <= 'Z') or
(c >= '0' and c <= '9'):
result += c
# If the scanned character is an
# ‘(‘, push it to the stack.
elif c == '(':
st.append('(')
# If the scanned character is an ‘)’,
# pop and add to the output string from the stack
# until an ‘(‘ is encountered.
elif c == ')':
while st[-1] != '(':
result += st.pop()
st.pop()
# If an operator is scanned
else:
while st and (prec(c) < prec(st[-1]) or prec(c) == prec(st[-1])):
result += st.pop()
st.append(c)
# Pop all the remaining elements from the stack
while st:
result += st.pop()
print(result)
exp = "a+b*c-d"
infixToPostfix(exp)
In-fix- to Prefix Transformation:
Algorithms to convert from infix expression to prefix expression is
as follows:
1. Reverse the infix expression. Note while reversing each ‘(‘ will
become ‘)’ and each ‘)’ becomes ‘(‘.
2. Scan input string from left to right character by character.
3. If the character is an operand, put it into the output stack.
4. If the character is an operator and the operator's stack is empty,
push the operator into operators' stack.
5. If the operator's stack is not empty, there may be the following
possibilities.
a. If the precedence of scanned operator is greater than the top
most operator of operator's stack, push this operator into
operator stack.
b. If the precedence of the scanned operator is less than the
top most operator of operator's stack, pop the operators
from operator stack until we find a lower precedence
operator than the scanned character. Never pop out ( '(' ) or
( ')' ) whatever may be the precedence level of scanned
character.
c. If the character is an opening round bracket ( '(' ), push it
into the operator's stack.
d. If the character is a closing round bracket ( ')' ), pop out
operators from operator's stack until we find an opening
bracket ('(' ).
e. Now pop out all the remaining operators from the
operator's stack and push into the output stack.
6. Reverse the Output stack (Pop )
Source Code:
# Python program to convert infix expression to prefix
# Function to return precedence of operators
def prec(c):
if c == '^':
return 3
elif c == '/' or c == '*':
return 2
elif c == '+' or c == '-':
return 1
else:
return -1
# Function to perform infix to prefix conversion
def infixToPrefix(exp):
st = []
result = ""
s=exp[::-1]
for i in range(len(s)):
c = s[i]
# If the scanned character is
# an operand, add it to the output string.
if (c >= 'a' and c <= 'z') or (c >= 'A' and c <= 'Z') or (c >= '0' and c
<= '9'):
result += c
# If the scanned character is an
# ‘(‘, push it to the stack.
elif c == ')':
st.append(')')
# If the scanned character is an ‘)’,
# pop and add to the output string from the stack
# until an ‘(‘ is encountered.
elif c == '(':
while st[-1] != ')':
result += st.pop()
st.pop()
# If an operator is scanned
else:
while st and (prec(c) < prec(st[-1])):
result += st.pop()
st.append(c)
# Pop all the remaining elements from the stack
while st:
result += st.pop()
result=result[::-1]
print(result)
exp = "a+b*c-d"
infixToPrefix(exp)
Convert the following infix expression A + B * C – D / E * H into its
equivalent prefix expression.
Step 1. Reverse the expression H * E / D - C * B + A
Infix to Prefix Table
Sr No Expression Stack Prefix
0 H H
1 * * H
2 E * HE
3 / */ HE
4 D */ HED
5 - - HED/*
6 C - HED/*C
7 * -* HED/*C
8 B -* HED/*CB
9 + -+ HED/*CB*
10 A -+ HED/*CB*A+-
Reverse the Output string : -+A*BC*/DEH
Algorithm for Prefix to Infix:
● Read the Prefix expression in reverse order (from right to left)
● If the symbol is an operand, then push it onto the Stack
● If the symbol is an operator, then pop two operands from the
Stack
Create a string by concatenating the two operands and the
operator between them.
string = (operand1 + operator + operand2)
And push the resultant string back to Stack
● Repeat the above steps until the end of Prefix expression.
● At the end stack will have only 1 string i.e resultant string
# Python Program to convert prefix to Infix
def prefixToInfix(prefix):
stack = []
# read prefix in reverse order
i = len(prefix) - 1
while i >= 0:
if not isOperator(prefix[i]):
# symbol is operand
stack.append(prefix[i])
i -= 1
else:
# symbol is operator
str = stack.pop() + prefix[i] + stack.pop()
stack.append(str)
i -= 1
return stack.pop()
def isOperator(c):
if c == "*" or c == "+" or c == "-" or c == "/" or c == "^":
return True
else:
return False
str = "*-A/BC-/AKL"
print(prefixToInfix(str))
# Output is Infix : ((A-(B/C))*((A/K)-L))
Algorithm for Postfix to Infix Conversion:
● Read the Postfix expression from left to right
● If the symbol is an operand, then push it onto the Stack
● If the symbol is an operator, then pop two operands from the
Stack
Create a string by concatenating the two operands and the
operator between them.
string = (operand2 + operator + operand1)
And push the resultant string back to Stack
● Repeat the above steps until the end of the Postfix expression.
● At the end stack will have only 1 string i.e resultant string
OR
# Python3 program to find infix for a given postfix.
def isOperand(x):
return ((x >= 'a' and x <= 'z') or
(x >= 'A' and x <= 'Z'))
# Get Infix for a given postfix
# expression
def getInfix(exp) :
s = []
for i in exp:
# Push operands
if (isOperand(i)) :
s.insert(0, i)
# We assume that input is a
# valid postfix and expect
# an operator.
else:
op1 =s.pop(0)
op2 = s.pop(0)
s.insert(0, "(" + op1 + i +
op2 + ")")
# There must be a single element in
# stack now which is the required
# infix.
return s[0]
exp = "ab*c+"
print(getInfix(exp.strip()))
