Parsing mathematical expressions in Reverse Polish Notation

Question

I've wanted to make a calculator for a long time now, so I wrote one of my first parsers, where the input is in reverse polish notation, \$1 \ 1 +\$ becomes \$2\$.

It supports to following operators; +, -, *, /, // floor division, ^ or ** exponent, and % or mod modulo.

While it's the best calculator I've written, the tokens are limited to only ones that take two operators. And I don't really like the idea of having a separate dictionary for ones that take more or less. This is a shame as now I can't add functions like sqrt or sin, or constants like pi or e, without having to have a different group for each.

Personally I dislike the error you get when you ^C out of the program, and so I silenced it. I also made a new error CalculatorError to not mask unknown errors, to easily exit out of the current equation if more than one function is called, make_pop, and to have a human readable error message.

TOKENS = {
    '+': lambda a, b: a + b,
    '-': lambda a, b: a - b,
    '*': lambda a, b: a * b,
    '/': lambda a, b: a / b,
    '^': lambda a, b: a ** b,
    '**': lambda a, b: a ** b,
    '%': lambda a, b: a % b,
    'mod': lambda a, b: a % b,
    '//': lambda a, b: a // b
}

class CalculatorError(Exception):
    pass

def make_pop(stack):
    def pop():
        try:
            return stack.pop()
        except IndexError:
            raise CalculatorError('Not enough arguments for function')
    return pop

def call():
    stack = []
    pop = make_pop(stack)
    buf = []

    calculation = iter(input('> ') + ' ')

    for char in calculation:
        if char not in ' \t':
            buf.append(char)
            continue

        token = ''.join(buf)
        if not token:
            continue

        if token in TOKENS:
            a = pop()
            b = pop()
            function = TOKENS[token]
            try:
                return_value = function(b, a)
            except ZeroDivisionError:
                raise CalculatorError("Can't devide by zero")
            else:
                stack.append(return_value)
        else:
            try:
                token = float(token)
            except ValueError:
                raise CalculatorError('{!r} is not a number'.format(token))
            stack.append(token)

        buf = []

    if len(stack) > 1 or buf:
        raise CalculatorError('Invalid function, not enough operators.', stack, buf)

    if stack[0] % 1:
        print(stack[0])
    else:
        print(int(stack[0]))

def main():
    while True:
        try:
            call()
        except CalculatorError as e:
            print(e)

if __name__ == '__main__':
    print('Press ^C to exit')
    try:
        main()
    except KeyboardInterrupt:
        pass
    # For some reason my Windows raises EOF on ^C...
    except EOFError:
        print()
    print('Goodbye!')

Some example output is:

Press ^C to exit
> 2 2 + 2 2 - /
Can't devide by zero
> 3 5 * 2 //
7
> 20 mod 11
Not enough arguments for function
> 20 11 mod
9
> 
Goodbye!

Answer 1

I'm not quite sure what you're asking for, but I was bored so I typed this up anyway. Hopefully it helps. ;-)

Working from the outside in:

Invocation

if __name__ == '__main__':
    print('Press ^C to exit')
    try:
        main()
    except KeyboardInterrupt:
        pass
    # For some reason my Windows raises EOF on ^C...
    except EOFError:
        print()
    print('Goodbye!')

This is all fine, but it probably should be in the main() function, and you just write

if __name__ == '__main__':
    main()

Mostly, this is a matter of convention, but also, it's handy to have a function that can be run from another Python script that will just do everything.

Organizing the driver code

The process of evaluating an RPN expression is something that makes a lot of sense to put as its own function. That's a self-contained task you could easily want to reuse elsewhere. So I would suggest making a function evaluate_rpn(expr) which does exactly that. You can then use this function in your main loop as follows:

def main():
    print(...)
    try:
        while True:
            try:
                print(evaluate_rpn(input('> ')))
            except CalculatorError as e:
                print(e)
    except KeyboardInterrupt:
    # and so on

Evaluating

This new evaluate_rpn() function is going to do mostly the same thing as your call() function currently does, except that instead of prompting using input(), it will take a string argument, and instead of printing the result, it will return it. Let me pick on a few things in that function, though.

Let the stack just be a stack

stack = []
pop = make_pop(stack)

The only real purpose of make_pop is to make it so that you get a CalculatorError instead of an IndexError when a function or operator doesn't have enough arguments. But I don't think it makes sense to do that. See, stack is just a stack. (Well, a list that is serving as a stack.) It knows nothing of numbers or arguments or calculators and really has no business raising a CalculatorError. The code in evaluate_rpn() is the thing that knows it is a calculator. That's where you should be raising CalculatorErrors. So instead of using make_pop, just watch for IndexErrors during the evaluation, catch them, and raise a CalculatorError in the handling code. As a side effect you won't need make_pop() anymore; you can just dispense with it entirely.

try:
    a = pop()
    b = pop()
except IndexError:
    raise CalculatorError(...)

Do tokenization the easy way

Your input strings consist of tokens (numbers, operators, functions) separated by whitespace, right? There's a built-in method to split a whitespace-separated string: string.split(). You don't need to bother with a buffer, or with iterating through the string's characters.

for token in calculation.split():
    # and so on

Don't overuse variables

You don't really have to save a and b and return_value separately; you only use them once each.

if token in TOKENS:
    try:
        stack.append(TOKENS[token](stack.pop(), stack.pop())
    except ZeroDivisionError:
        raise CalculatorError(...)
    except IndexError: # from a couple paragraphs ago
        # and so on

If different parts of this expression could raise the same type of error, then that would be a good reason to break it down, so that you could tell exactly where a given error comes from. But that's not an issue here. You'll only ever get ZeroDivisionErrors for one reason.

Same goes for the float-parsing part:

else:
    try:
        stack.append(float(token))
    except ValueError:
        raise CalculatorError(...)

For complicated sequences of code, you have to make a subjective judgement about where to use variables and where not to in order to make the code as clear as possible. But in this case, I think most programmers would agree that the variables are fairly unnecessary.

Let output formatting be controlled by the formatting routines

Evaluating an RPN expression doesn't include formatting - in particular, deciding whether the result is an integer or not is a separate task from just getting the result in the first place. So at the end of evaluate_rpn, just return a float. When you print it, instead of print(result) you can do

print('{:g}'.format(result))

and it will automatically strip trailing zeros as needed. Of course, this does display large numbers in scientific notation (2.89146e+07); if that's a problem, then you might have to do your own formatting.

Use descriptive variable names

Your TOKENS list doesn't actually contain tokens; it contains operators, and could be generalized to contain functions. So I'd suggest naming it OPERATORS or some such thing.

Allowing arbitrary numbers of arguments

This is really more about adding a feature than reviewing your existing code, but I might as well point you in the right direction. All you have to do is store the number of arguments a function or operator requires, in addition to the code that actually evaluates the operator. For example,

OPERATORS = {
    '+':    (2, lambda x, y: x + y),
    'sqrt': (1, math.sqrt),
    # and so on
}

Then, when you invoke an operator, instead of hard-coding two arguments like you did or like I did above,

stack.append(OPERATORS[token](stack.pop(), stack.pop())

you can check how many operands the operator requires,

n_operands, evaluator = OPERATORS[token]

pop that many from the top of your stack,

# these two lines together are like a "multipop"
operands = reversed(stack[-n_operands:])
del stack[-n_operands:]

and evaluate the operator with those operands,

stack.append(evaluator(*operands))

I leave it to you to figure out the best way to put try/except blocks around this code.

Actually, the way I've done it here has a problem dealing with the case where n_operands is zero (this would happen if you include constants or zero-argument functions in the list of operators). To get around that, you can use the following:

n_operands, evaluator = OPERATORS[token]
stack.append(evaluator(*[stack.pop() for _ in range(n_operands)]))

Instead of chopping off the whole end of the list, as in the previous method, this one pops off the last n_operands elements one at a time.

Answer 2

Letting the other answers handle other aspects of the review, this answer addresses two issues:

• A simpler way to exit – Just call exit() or whatever when you encounter the token quit. If you don't want to exit() you could call a specific exception, i.e. QuitException, and catch this at the proper level
• Variable number of operands – If first using slice operators to pick out the correct number of operands, and remove them from the stack, we can use unpacking of argument lists to call the operator with the list of operands. Rather neat, actually!

Here is the code changes:

from operator import add, sub, mul
import math

def foo():
    return 100.0

TOKENS = {
     '+'   : (2, add),
     '-'   : (2, sub),
     '*'   : (2, mul),
     '/'   : (2, lambda a, b: a / b),
     '^'   : (2, lambda a, b: a ** b),
     '**'  : (2, lambda a, b: a ** b),
     '%'   : (2, lambda a, b: a % b),
     'mod' : (2, lambda a, b: a % b),
     '//'  : (2, lambda a, b: a // b),
     'sqrt': (1, math.sqrt),
     'foo' : (0, foo),       # function with no parameters
     'pi'  : (-1, math.pi),  # a constant
     }

  # Keep the else-block, but replace the if-block with:
  if token == 'quit':
      exit()   # Or possibly: raise QuitException :-)

  if token in TOKENS:
        operands_count, operator = TOKENS[token]

        if operands_count >= 0:
            operands = stack[:operands_count]
            del stack[:operands_count]
            answer = operator(*operands)
        else:
            answer = operator

        stack.append(answer)

Using this I was able to parse '4 5 + 1 + 10 * 2 ** sqrt pi * foo quit 2 *' and got the expected 31415.9265359 as my final output. Tested '20 3 mod ' equals 2 also, just to verify that operand order had not changed.

Have I mentioned that I like the slice operators, and the *operands in combination with the simplicity of adding function, constants and so on into a list? If not, considered it done!