Turn Postfix Python Code to Prefix

Question

I am learning Python from interactivepython.org. On this site, they have the code for evaluating postfix expressions.. but I would like to see how it would be done for prefix expressions as well. Here is the code:

def postfixEval(postfixExpr):
    operandStack = Stack()
    tokenList = postfixExpr.split()

    for token in tokenList:
        if token in "0123456789":
            operandStack.push(int(token))
        else:
            operand2 = operandStack.pop()
            operand1 = operandStack.pop()
            result = doMath(token,operand1,operand2)
            operandStack.push(result)
    return operandStack.pop()

def doMath(op, op1, op2):
    if op == "*":
        return op1 * op2
    elif op == "/":
        return op1 / op2
    elif op == "+":
        return op1 + op2
    else:
        return op1 - op2

print(postfixEval('7 8 + 3 2 + /'))

If I understand this lesson correctly, would I just change the operand ordering?

Answer 1

No, the operands come in the same order. The difference is that you have to take the operation before the operands instead of afterward. This is complicated by the fact that you likely have to make recursive calls to evaluate the operands: if an operand begins with an operation, you recur.

Answer 2

You can write a similar parser for prefix notation arithmetic, but it's going to be more complicated because the logic of what to do when you've received a number token is more complicated (sometimes you store it, other times you evaluate an operator and either store the result or evaluate another operator, etc.). It's often easier to use recursion, since the function call stack can handle this more easily than a stack you have to manage by hand.

Here's an implementation that uses recursion (and an iterator to handle the tokens as a stream):

def prefix_eval(prefix_expr):
    return prefix_eval_rec(iter(prefix_expr.split()))

def prefix_eval_rec(expr_iter):
    token = next(expr_iter)
    if token.isdigit():
        return int(token)

    op1 = prefix_eval_rec(prefix_iter)
    op2 = prefix_eval_rec(prefix_iter)
    return doMath(token, op1, op2)

Here's a quick attempt to do this without recursion. It's quite a bit messier than the postfix code, since we need to know how many arguments the top operator on the stack has received so far. My solution is to use a list for the operator and its arguments and check its length. The current_op list is conceptually on the top of the stack. Your could instead use a more conventional stack with individual items on it, but you'd need to be able to inspect the type of the top item on the stack (hopefully without popping and re-pushing it).

def prefix_eval(prefix_expr):
    token_list = prefix_expr.split()
    stack = Stack()
    current_op = []

    for token in token_list:
        if token.isdigit():
            current_op.append(int(token))
            while len(current_op) == 3:
                result = doMath(*current_op)
                current_op = stack.pop()
                current_op.append(result)
        else:
            stack.push(current_op)
            current_op = [token]
    return current_op[0]