3. Infix to Postfix expression
Rules for the conversion from infix to postfix expression¶
- Print the operand as they arrive.
- If the stack is empty or contains a left parenthesis on top, push the incoming operator on to the stack.
- If the incoming symbol is '(', push it on to the stack.
- If the incoming symbol is ')', pop the stack and print the operators until the left parenthesis is found.
- If the incoming symbol has higher precedence than the top of the stack, push it on the stack.
- If the incoming symbol has lower precedence than the top of the stack, pop and print the top of the stack. Then test the incoming operator against the new top of the stack.
- If the incoming operator has the same precedence with the top of the stack then use the associativity rules. If the associativity is from left to right then pop and print the top of the stack then push the incoming operator. 8. If the associativity is from right to left then push the incoming operator.
- At the end of the expression, pop and print all the operators of the stack.
References¶
In [1]:
Copied!
expression1 = "K + L - M*N + (O^P) * W/U/V * T + Q"
expression2 = "K + L - M*N + (O-P) * W/U/V * T + Q"
expression3 = "a * b / c + e / f * g + k - x * y"
expected_output1 = "KL+MN*-OP^W*U/V/T*+Q+"
expected_output2 = 'KL+MN*-OP-W*U/V/T*+Q+'
expected_output3 = 'ab*c/ef/g*+k+xy*-'
expression1 = expression1.replace(" ", "")
expression2 = expression2.replace(" ", "")
expression3 = expression3.replace(" ", "")
expression1 = "K + L - M*N + (O^P) * W/U/V * T + Q"
expression2 = "K + L - M*N + (O-P) * W/U/V * T + Q"
expression3 = "a * b / c + e / f * g + k - x * y"
expected_output1 = "KL+MN*-OP^W*U/V/T*+Q+"
expected_output2 = 'KL+MN*-OP-W*U/V/T*+Q+'
expected_output3 = 'ab*c/ef/g*+k+xy*-'
expression1 = expression1.replace(" ", "")
expression2 = expression2.replace(" ", "")
expression3 = expression3.replace(" ", "")
In [2]:
Copied!
expression1
expression1
Out[2]:
'K+L-M*N+(O^P)*W/U/V*T+Q'
In [3]:
Copied!
class Stack:
def __init__(self):
self.items = []
self.__top = -1
def is_empty(self):
return self.__top == -1
# return len(self.items) == 0
# return self.items == []
def top(self):
if self.is_empty():
print("Stack is empty, nothing to peek()")
return
else:
#print("<Element: %s>" % self.items[-1])
return self.items[-1]
def __repr__(self):
items = []
for i in range(len(self.items)-1, 0, -1):
if i == self.__top:
items.append("[Top: %s]" % self.items[i])
else:
items.append("[%s]" % self.items[i])
return ", ".join(items)
def __iter__(self):
for i in range(len(self.items)-1, 0, -1):
yield self.items[i]
def __len__(self):
return len(self.items)
def push(self, data):
print("Inserting: {} into the stack".format(data))
self.items.append(data)
self.__top += 1
def pop(self):
if self.is_empty():
print("Stack is empty, nothing to pop()")
else:
data = self.items.pop()
print("Removing: {} from top of the stack".format(data))
self.__top -= 1
return data
class Stack:
def __init__(self):
self.items = []
self.__top = -1
def is_empty(self):
return self.__top == -1
# return len(self.items) == 0
# return self.items == []
def top(self):
if self.is_empty():
print("Stack is empty, nothing to peek()")
return
else:
#print("" % self.items[-1])
return self.items[-1]
def __repr__(self):
items = []
for i in range(len(self.items)-1, 0, -1):
if i == self.__top:
items.append("[Top: %s]" % self.items[i])
else:
items.append("[%s]" % self.items[i])
return ", ".join(items)
def __iter__(self):
for i in range(len(self.items)-1, 0, -1):
yield self.items[i]
def __len__(self):
return len(self.items)
def push(self, data):
print("Inserting: {} into the stack".format(data))
self.items.append(data)
self.__top += 1
def pop(self):
if self.is_empty():
print("Stack is empty, nothing to pop()")
else:
data = self.items.pop()
print("Removing: {} from top of the stack".format(data))
self.__top -= 1
return data
In [4]:
Copied!
operator_precedence = {
"+":1,
"-":1,
"*":2,
"/":2,
"^":3,
"(":0, # if this is found then no need to check for precedence, just push so we can keep 0 precedence
")":0, # this will never be found in the stack so keep 0 precedence
}
operator_precedence = {
"+":1,
"-":1,
"*":2,
"/":2,
"^":3,
"(":0, # if this is found then no need to check for precedence, just push so we can keep 0 precedence
")":0, # this will never be found in the stack so keep 0 precedence
}
In [5]:
Copied!
def infix_to_postfix_conversion(expression):
stack = Stack()
result = ""
for i in expression:
if i in operator_precedence:
# 2. if the stack is empty or contains a left parenthesis on top,
# push the incoming operator on to the stack.
if stack.is_empty() or stack.top() == "(":
stack.push(i)
# 3. If the incoming symbol is '(', push it on to the stack.
elif i == "(":
stack.push(i)
elif i == ")":
# 4. If the incoming symbol is ')', pop the stack and print
# the operators until the left parenthesis is found.
while stack.top() != "(":
element = stack.pop()
result += element
stack.pop()
# 5. if the incoming symbol has higher precedence than the top of
# the stack, push it on the stack.
elif operator_precedence[i] > operator_precedence[stack.top()]:
stack.push(i)
else:
# 6. If the incoming symbol has lower precedence than the top of the stack,
# pop and print the top of the stack.
# Then test the incoming operator against the new top of the stack.
# 7. If the incoming operator has the same precedence with the top of the stack
# then use the associativity rules.
# If the associativity is from left to right then pop and print
# the top of the stack then push the incoming operator.
# If the associativity is from right to left then push the incoming operator. - technically
# this condition never comes at least with the above set of opeators.
# ^ is the only operator having associativity Right to Left but it also has higer precedence.
if not stack.is_empty():
while operator_precedence[i] <= operator_precedence[stack.top()]:
element = stack.pop()
result += element
if stack.is_empty():
break
stack.push(i)
else:
# 1. Print the operand as they arrive.
result += i
while not stack.is_empty():
result += stack.pop()
return result
def infix_to_postfix_conversion(expression):
stack = Stack()
result = ""
for i in expression:
if i in operator_precedence:
# 2. if the stack is empty or contains a left parenthesis on top,
# push the incoming operator on to the stack.
if stack.is_empty() or stack.top() == "(":
stack.push(i)
# 3. If the incoming symbol is '(', push it on to the stack.
elif i == "(":
stack.push(i)
elif i == ")":
# 4. If the incoming symbol is ')', pop the stack and print
# the operators until the left parenthesis is found.
while stack.top() != "(":
element = stack.pop()
result += element
stack.pop()
# 5. if the incoming symbol has higher precedence than the top of
# the stack, push it on the stack.
elif operator_precedence[i] > operator_precedence[stack.top()]:
stack.push(i)
else:
# 6. If the incoming symbol has lower precedence than the top of the stack,
# pop and print the top of the stack.
# Then test the incoming operator against the new top of the stack.
# 7. If the incoming operator has the same precedence with the top of the stack
# then use the associativity rules.
# If the associativity is from left to right then pop and print
# the top of the stack then push the incoming operator.
# If the associativity is from right to left then push the incoming operator. - technically
# this condition never comes at least with the above set of opeators.
# ^ is the only operator having associativity Right to Left but it also has higer precedence.
if not stack.is_empty():
while operator_precedence[i] <= operator_precedence[stack.top()]:
element = stack.pop()
result += element
if stack.is_empty():
break
stack.push(i)
else:
# 1. Print the operand as they arrive.
result += i
while not stack.is_empty():
result += stack.pop()
return result
In [6]:
Copied!
result = infix_to_postfix_conversion(expression1)
result = infix_to_postfix_conversion(expression1)
Inserting: + into the stack Removing: + from top of the stack Inserting: - into the stack Inserting: * into the stack Removing: * from top of the stack Removing: - from top of the stack Inserting: + into the stack Inserting: ( into the stack Inserting: ^ into the stack Removing: ^ from top of the stack Removing: ( from top of the stack Inserting: * into the stack Removing: * from top of the stack Inserting: / into the stack Removing: / from top of the stack Inserting: / into the stack Removing: / from top of the stack Inserting: * into the stack Removing: * from top of the stack Removing: + from top of the stack Inserting: + into the stack Removing: + from top of the stack
In [7]:
Copied!
result == expected_output1
result == expected_output1
Out[7]:
True
In [8]:
Copied!
result = infix_to_postfix_conversion(expression2)
result = infix_to_postfix_conversion(expression2)
Inserting: + into the stack Removing: + from top of the stack Inserting: - into the stack Inserting: * into the stack Removing: * from top of the stack Removing: - from top of the stack Inserting: + into the stack Inserting: ( into the stack Inserting: - into the stack Removing: - from top of the stack Removing: ( from top of the stack Inserting: * into the stack Removing: * from top of the stack Inserting: / into the stack Removing: / from top of the stack Inserting: / into the stack Removing: / from top of the stack Inserting: * into the stack Removing: * from top of the stack Removing: + from top of the stack Inserting: + into the stack Removing: + from top of the stack
In [9]:
Copied!
result == expected_output2
result == expected_output2
Out[9]:
True
In [10]:
Copied!
result = infix_to_postfix_conversion(expression3)
result = infix_to_postfix_conversion(expression3)
Inserting: * into the stack Removing: * from top of the stack Inserting: / into the stack Removing: / from top of the stack Inserting: + into the stack Inserting: / into the stack Removing: / from top of the stack Inserting: * into the stack Removing: * from top of the stack Removing: + from top of the stack Inserting: + into the stack Removing: + from top of the stack Inserting: - into the stack Inserting: * into the stack Removing: * from top of the stack Removing: - from top of the stack
In [11]:
Copied!
result == expected_output3
result == expected_output3
Out[11]:
True
In [12]:
Copied!
def infix_to_postfix_ref1(expression):
# do not forget to have "(" in operator priority list
operator_priority = {"(":0, "+":1, "-":1, "*":2, "/":2, "^":3}
# operator_priority = {"+":1, "-":1, "*":2, "/":2, "^":3}
stack = Stack()
result = ""
# expression = expression.replace(" ", "")
for character in expression:
if character == "(":
stack.push(character)
elif character == ")":
while stack.top() != "(":
element = stack.pop()
if element:
result += element
stack.pop()
elif character in operator_priority:
if not stack.is_empty():
while operator_priority[stack.top()] >= operator_priority[character]:
result += stack.pop()
if stack.is_empty():
break
stack.push(character)
else:
result += character
while not stack.is_empty():
result += stack.pop()
return result
def infix_to_postfix_ref1(expression):
# do not forget to have "(" in operator priority list
operator_priority = {"(":0, "+":1, "-":1, "*":2, "/":2, "^":3}
# operator_priority = {"+":1, "-":1, "*":2, "/":2, "^":3}
stack = Stack()
result = ""
# expression = expression.replace(" ", "")
for character in expression:
if character == "(":
stack.push(character)
elif character == ")":
while stack.top() != "(":
element = stack.pop()
if element:
result += element
stack.pop()
elif character in operator_priority:
if not stack.is_empty():
while operator_priority[stack.top()] >= operator_priority[character]:
result += stack.pop()
if stack.is_empty():
break
stack.push(character)
else:
result += character
while not stack.is_empty():
result += stack.pop()
return result
In [13]:
Copied!
result = infix_to_postfix_ref1(expression1)
result = infix_to_postfix_ref1(expression1)
Inserting: + into the stack Removing: + from top of the stack Inserting: - into the stack Inserting: * into the stack Removing: * from top of the stack Removing: - from top of the stack Inserting: + into the stack Inserting: ( into the stack Inserting: ^ into the stack Removing: ^ from top of the stack Removing: ( from top of the stack Inserting: * into the stack Removing: * from top of the stack Inserting: / into the stack Removing: / from top of the stack Inserting: / into the stack Removing: / from top of the stack Inserting: * into the stack Removing: * from top of the stack Removing: + from top of the stack Inserting: + into the stack Removing: + from top of the stack
In [14]:
Copied!
result == expected_output1
result == expected_output1
Out[14]:
True
In [15]:
Copied!
Operators = set(['+', '-', '*', '/', '(', ')', '^']) # collection of Operators
Priority = {'+':1, '-':1, '*':2, '/':2, '^':3} # dictionary having priorities of Operators
def infixToPostfix_ref3(expression):
stack = [] # initialization of empty stack
output = ''
for character in expression:
if character not in Operators: # if an operand append in postfix expression
output+= character
elif character=='(': # else Operators push onto stack
stack.append('(')
elif character==')':
while stack and stack[-1]!= '(':
output+=stack.pop()
stack.pop()
else:
while stack and stack[-1]!='(' and Priority[character]<=Priority[stack[-1]]:
output+=stack.pop()
stack.append(character)
while stack:
output+=stack.pop()
return output
Operators = set(['+', '-', '*', '/', '(', ')', '^']) # collection of Operators
Priority = {'+':1, '-':1, '*':2, '/':2, '^':3} # dictionary having priorities of Operators
def infixToPostfix_ref3(expression):
stack = [] # initialization of empty stack
output = ''
for character in expression:
if character not in Operators: # if an operand append in postfix expression
output+= character
elif character=='(': # else Operators push onto stack
stack.append('(')
elif character==')':
while stack and stack[-1]!= '(':
output+=stack.pop()
stack.pop()
else:
while stack and stack[-1]!='(' and Priority[character]<=Priority[stack[-1]]:
output+=stack.pop()
stack.append(character)
while stack:
output+=stack.pop()
return output
In [16]:
Copied!
result = infixToPostfix_ref3(expression2)
result = infixToPostfix_ref3(expression2)
In [17]:
Copied!
result == expected_output2
result == expected_output2
Out[17]:
True
In [ ]:
Copied!