INFIX TO POSTFIX AND POSTFIX EVALUATION (PYTHON)

 Stack Expressions : INFIX TO POSTFIX AND POSTFIX EVALUATION

Infix to Postfix Conversion  Infix expression: The expression of the form a op b. When an operator is in-between every pair of operands.  Postfix expression: The expression of the form a b op. When an operator is followed for every pair of operands.  Algorithm: 1. Scan the infix expression from left to right. 2. If the scanned character is an operand, output it. 3. Else,     3.1 If the precedence of the scanned operator is greater than the precedence of the     operator in the stack(or the stack is empty or the stack contains a ‘(‘ ), push it.     3.2 Else, Pop all the operators from the stack which are greater than or equal to in     precedence than that of the scanned operator. After doing that Push the scanned operator     to the stack. (If you encounter parenthesis while popping then stop there and push the     scanned operator in the stack.) 4. If the scanned character is an ‘(‘, push it to the stack. 5. If the scanned character is an ‘)’, pop the stack and and output it until a ‘(‘ is encountered, and discard both the parenthesis. 6. Repeat steps 2-6 until infix expression is scanned. 7. Print the output 8. Pop and output from the stack until it is not empty.      Program: OPERATORS = set(['+', '-', '*', '/', '(', ')']) PRIORITY = {'+':1, '-':1, '*':2, '/':2} def infix_to_postfix(formula):     stack = [] # only pop when the coming op has priority     output = ''     for ch in formula:         if ch not in OPERATORS:             output += ch         elif ch == '(':             stack.append('(')         elif ch == ')':             while stack and stack[-1] != '(':                 output += stack.pop()            stack.pop() # pop '('         else:             while stack and stack[-1] != '(' and PRIORITY[ch] < PRIORITY[stack[-1]]:                 output += stack.pop()             stack.append(ch) # leftover     while stack: output += stack.pop()     print (output) infix_to_postfix('a+b')   OUTPUT: ab+
  Postfix Evaluation  The procedure for getting the result is: 1. Convert the expression in post-fix notation. 2. Push the operands into the stack in the order they are appear. 3. When any operator is encountered then pop two topmost operands for executing the operation. 4. After execution push the result obtained into the stack. 5. After the complete execution of expression the final result remains on the top of the stack.            Program:  OPERATORS = set(['+', '-', '*', '/', '(', ')']) PRIORITY = {'+':1, '-':1, '*':2, '/':2} def evaluate_postfix(formula):     stack = []     for ch in formula:         if ch not in OPERATORS:             stack.append(float(ch))         else:             b = stack.pop()             a = stack.pop()             c = {'+':a+b, '-':a-b, '*':a*b, '/':a/b}[ch]             stack.append(c)     print (stack[-1]) evaluate_postfix('14+') OUTPUT: 5.0