Stack Postfix Expressions in Python

How to get Python to do some maths for us.

Overview

Postfix, or Reverse Polish Notation is ideal for performing maths on a stack.

Postfix does ‘one weird little trick’ on our familiar algebra (infix notation) :

infix: (10 - 5) / 4 + 8 
postfix: 8 10 5 - 4 / + 

The upshot is that we can run the postfix expression through stack operations to do the math.

When given a string of operands and operators in postfix notation:

• push the operands into the stack until we get an operator,
• pop twice to retrieve the last two operands, then solve the equation with the operator,
• push the result into the stack.

The following exercise is inspired by the example in:

Brad Miller and David Ranum, Luther College, Problem Solving with Algorithms and Data Structures using Python, pythonds, Runestone Academy: 4.9. Infix, Prefix and Postfix Expressions.

To perform this exercise we will need to use the Stack class we created previously:

"""stacking postfix in python 
Performing Reverse Polish Notation calculations on stacks in Python 3  
Adam Heinz 2022-11-27 

>>>postfix_eval('8 10 5 - 4 / +') 
9.25
>>>postfix_eval('4 24 6 / 2 + * 20 + 2 - 4 +') 
46.0
>>>postfix_eval('10 25 5 9 - - - 60 * 8 + 15 -') 
-1147
""" 

from stack import Stack 

def postfix_math(rpn_operator, rpn_operand1, rpn_operand2): 
    """Performs BODMAS without brackets B 
    on Reverse Polish Notation (RPN) Maths""" 
      
    if rpn_operator == chr(42):             # Multiplication 
        return rpn_operand1 * rpn_operand2 
    
    if rpn_operator == chr(47):             # Division  
        return rpn_operand1 / rpn_operand2 
    
    if rpn_operator == chr(43):             # Addition 
        return rpn_operand1 + rpn_operand2 
    
    else:                                   # Subtraction 
        return rpn_operand1 - rpn_operand2 
    
    

def postfix_eval(postfix_expression): 
    """Stacks and calculates a postfix expression 
    (RPN - Reverse Polish Notation""" 
    
    postfix_stack = Stack() 
    postfix_list = postfix_expression.split() 
    
    for item in postfix_list: 
        
        if item[0] in '0123456789': 
            postfix_stack.push(float(item)) 
                       
        else: 
            operand2 = postfix_stack.pop() 
            operand1 = postfix_stack.pop() 
            rpn_result = postfix_math( item, operand1, operand2) 
            postfix_stack.push(float(rpn_result))  
            
    return postfix_stack.pop() 
    


# verify the doctests 
if __name__ == '__main__': 
    postfix_eval('8 10 5 - 4 / +') 
    postfix_eval('10 25 5 9 - - - 60 * 8 + 15 -') 
 
# Adam Heinz 2022-11-27  

QED

© Adam Heinz

27 November 2022