Inter-Conversion of Postfix and Infix Expression in Python
This post deals with an algorithm to inter-convert between postfix and infix expressions in Python.
Prerequisites: Basics of python classes and objects, arrays and strings (refer to this)
Postfix and Infix Expressions
The postfix and infix are basically representations of an arithmetic expression. Infix expression is simply the kind of expression we write down usually, like say, 2+3-5*8.
The problem, however, is that to evaluate this expression, one would have to apply the BODMAS rule while solving it. This might be very simple for us, but for a computer, it takes up too many back and forth traversals in the expression. It wastes valuable memory and time.
Hence, most programming languages first apply the operator precedence rules on the infix expression and convert them once and for all into postfix notation. The postfix notation doesn’t need any brackets. The order of operations can be easily understood using a stack, in the following manner,
- Starting from the left side of the postfix expression, keep pushing elements into a stack if it is an operand
- If an operator is found, pop one or two operands from the stack (depending on whether the operator is unary or binary)
- Operate on the operands and push the result into the stack
- Repeat until the end of the postfix expression
This method will easily evaluate the postfix expression. It will use the same precedence order based on which the postfix expression was created.
Inter-Conversion Using Stacks: Postfix and Infix
Developing an algorithm and programming to inter-convert infix and postfix expressions, will not only be a good way to practice stacks but will also help to understand the conversion process much better. It is strongly recommended that the readers try to come up with their own solution before taking a look at the program provided.
We first need a stack for this implementation,
class Stack(): def __init__(self): self.size = 0 self.content = list() def is_empty(self): return not bool(self.content) def push(self,elem): self.content.append(elem) self.size = len(self.content)-1 def pop_(self): if not self.is_empty(): elem = self.content.pop() size = len(self.content)-1 return elem else: return None def peek(self): if not self.is_empty(): return self.content[-1] else: return None def display(self): if not self.is_empty(): return self.content else: return None
how we can convert postfix to infix
def post_to_in(entry): changer = Stack() for k in entry: if k.isalpha(): changer.push(k) elif k in ['+','-','*','/','^']: b = changer.pop_() a = changer.pop_() add_str = '('+a+k+b+')' changer.push(add_str) changer.display() return changer.pop_()
As mentioned in the previous part, the algorithm uses a stack to keep pushing operands, pop them when an operator is found, operate on them and push them back.
These implementations, however, aim, not to evaluate the expression, but to inter-convert the expressions containing single-character arithmetic variables. The output will make this point clear.
Convert infix to postfix
def in_to_post(entry): changer = Stack() new_exp = list() for k in entry: if k.isalpha(): new_exp.append(k) elif k in ['+','-','*','/','^',]: prec_check = operator_precedence[k] while True: curr_op = changer.peek() if curr_op in ['+','-','*','/','^']: curr_op_val = operator_precedence[curr_op] if curr_op_val <= prec_check: add = changer.pop_() new_exp.append(add) else: break else: break changer.push(k) elif k == '(': changer.push(k) elif k == ')': while True: if changer.peek() == '(': changer.pop_() break else: add = changer.pop_() new_exp.append(add) return new_exp
NOTE: The input for this must be provided with the precedence clearly indicated. It should denote the order of evaluation, using brackets (see output)
The algorithm as follows:
- Read expression from left to right and repeat the below steps till stack is empty.
- If we find an operand, add it to the final expression.
- Else, if we find a left parenthesis, push it onto Stack.
- Else, If we find an operator, then:
- Repeatedly pop from Stack and append to final expression each operator. Only those which have the same precedence as or higher precedence than the operator.
- Push operator to Stack.
- If a right parenthesis is encountered, then:
- Repeatedly pop from Stack and append to the final expression, each operator until we reach a left parenthesis
- Remove the left Parenthesis
This will convert the infix into a postfix expression.
Feel free to leave behind any sort of feedback, suggestions, doubts below.