calculator expression evaluator - prefix vs postfix notation?

Question

For writing your own calculator (expression evaluator) for expressions like:

3+2*5

7+(8/2)*5

3*5+8*7

I'm under the impression that the only sensible way to accomplish this is to convert to either prefix notation or postfix notation, then evaluate from there.

I've done this before a while ago using postfix notation and it seemed to work pretty well. At the time I got the idea from somewhere (can't remember where at the moment) that postfix notation is more standard for this puspose. I've not tried this with prefix notation.

What are advantages/disadvantages of choosing prefix notation vs postfix notation for this task? For a typical interview question (ex. https://leetcode.com/problems/basic-calculator-ii/) what would be the better choice and why?

P.S. Does Python's eval use prefix, postfix, or an entirely different method? I'm under the impression that this is the source https://github.com/python/cpython/blob/master/Python/ceval.c for Python's eval but it's not very clear what the general strategy is.

Answer 1

There's no need to convert to prefix or postfix first. If you're only going to evaluate it once or a few times, then you can do it while you parse. I usually use recursive descent like this:

import re

def evalExpr(infixStr):
    # precedences for infix operators
    precs = {'+':0 , '-':0, '/':1, '*':1, '^':2}
    # functions of operators
    funcs = {
        '+': (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)
    }

    # divide string into tokens
    tokens = re.split(r' *([\(\)\+\-\*\^/]) *', infixStr)
    tokens = [t for t in tokens if t!='']

    # current parse position
    pos = 0

    # evaluate infix expression at the parse point,
    # processing only operators above a given precedence
    def eval2(minprec,closer=None):
        nonlocal pos, tokens
        # first we need a number or parenthesized expression
        if (pos >= len(tokens)):
            raise Exception("Unexpected end")
        if (tokens[pos]=="("):
            pos += 1
            val = eval2(0,")")
            pos += 1
        else:
            val = float(tokens[pos])
            pos += 1
        # gather operators that consume the value
        while pos < len(tokens):
            op = tokens[pos]
            if op == closer:
                return val
            prec = precs.get(op)
            if prec == None:
                raise Exception("operator expected. got " + op)
            if prec<minprec: # precedence too low for us
                break
            pos += 1 # operator OK

            # get the argument on the operator's right
            # this will go to the end, or stop at an operator
            # with precedence <= prec
            arg2 = eval2(prec+1,closer)
            val = (funcs[op])(val, arg2)
        if closer != None:
            raise Exception("Expected " + closer)
        return val

    return eval2(0)

print(evalExpr("5+3*4^2+1"))  # prints 54.0
print(evalExpr("7+(8/2)*5"))  # prints 27.0
print(evalExpr("3*5+8*7"))    # prints 71.0

This recursive descent style is the result of having written many expression parsers, and now I almost always parse expressions in this way. It is just about as simple as an expression parser can be, and it makes it easy to add unary operators and different kinds of brackets, and operators that associate right-to-left like the assignment operator.

The secret is the signature of eval2 that makes it easy to implement the precedence rules.