Search code examples
pythonrpn

RPN Evaluator optimization without losing readability


I'm implementing a program that needs a RPN calculator function, I've got the one bellow, but being new to python I wonder if I can optimize it without losing the readability.

Found some solutions using dictionaries and so on, but I got lost in the 'pythonesque' parts, the lists are still somewhat of a mistery to me...

my function is :

def parseRPN(expression):
    """Parses and calculates the result fo an RPN expression
        takes a list in the form of ['2','2','*']
        returns 4
    """
    try:
        stack = []
        for val in expression:
            if val in ['-', '+', '*', '/']:
                op1 = stack.pop()
                op2 = stack.pop()
                if val=='-': result = op2 - op1
                if val=='+': result = op2 + op1
                if val=='*': result = op2 * op1
                if val=='/':
                  if op1==0:
                      result=1
                  else:
                      result = op2 / op1
                stack.append(result)
            elif val in ['sin','cos']:
                op1 =stack.pop()
                if val=='sin': result = sin(op1)
                if val == 'cos': result = cos(op1)
                stack.append(result)
            else:
                stack.append(float(val))
        return stack.pop()
    except:
        print('error parse RPN fn:parse_rpn :' + str(expression))
        return 10*10**10

Thanks in advance


Solution

  • The original implementation is fine, and clear. Here's another that uses more Pythonic features:

    • tests using py.test (<3)

    • parse errors are left alone, as they already indicate what's going on

    • the operator module is used directly for many two-argument functions, like multiply

    • likewise, single-argument math functions like sin/cos just call the math library

    • for convenience, the expression can be specified as a single string, like "2 3 /"

    Calculators are a lot of fun, and are a great introduction to cool topics like compiling and parsing. Have fun!

    RPN calculator

    import math
    import operator
    
    import pytest
    
    
    ERROR_VALUE = -1.
    
    
    def safe_divide(darg1, darg2):
        try:
            return darg1/darg2
        except ZeroDivisionError:
            return ERROR_VALUE
    
    def parseRPN(expression):
        """Parses and calculates the result of a RPN expression
            takes a list in the form of ['2','2','*']
            returns 4
        """
        # allow simple string: "2 3 /"
        if isinstance(expression, basestring):
            expression = expression.split()
    
        function_twoargs = {
        '*': operator.mul,
        '/': safe_divide,
        '+': operator.add,
        '-': operator.sub,
        }
        function_onearg = {
        'sin': math.sin,
        'cos': math.cos,
        }
        stack = []
        for val in expression:
            result = None
            if val in function_twoargs:
                arg2 = stack.pop()
                arg1 = stack.pop()
                result = function_twoargs[val](arg1, arg2)
            elif val in function_onearg:
                arg = stack.pop()
                result = function_onearg[val](arg)
            else:
                result = float(val)
            stack.append(result)
        return stack.pop()
    
    
    def test_happy_paths():
        assert parseRPN([2, 3, '*']) == 6.
        assert parseRPN('0 sin') == 0.
        assert parseRPN([2, 3, '/']) == 2./3
    
    def test_safe_divide():
        assert parseRPN([2, 0, '/']) == ERROR_VALUE
    
    def test_parse_error():
        with pytest.raises(ValueError) as excinfo:
            parseRPN('gin')
        assert str(excinfo.value) == 'could not convert string to float: gin'