complicated expressions in Shunting-yard algorithm causing calculator error

Question

I have implemented the shunting-yard algorithm as can be seen here:

#!/usr/bin/env python

import sys
import string
import operator
import signal

class InvalidStackError(Exception): pass
class BadParenError(Exception): pass

def hook_ctrl_c(signal, frame):
    print ""
    sys.exit(0)

signal.signal(signal.SIGINT, hook_ctrl_c)

ops = {
    "*" : [operator.mul, 3, "left"],
    "x" : [operator.mul, 3, "left"],
    "/" : [operator.div, 3, "left"],
    "+" : [operator.add, 2, "left"],
    "-" : [operator.sub, 2, "left"],
    "^" : [operator.pow, 4, "right"],
    "(" : [None, 5, "neither"],
    ")" : [None, 5, "neither"]
}

def parse(raw):
    return raw.split()

def compile_to_rpn(tokens):
    operator_stack = []
    rpn_code = []

    for token in tokens:
        try:
            current_number = int(token)
            rpn_code.append(current_number)

        except ValueError:
            if token == "(":
                operator_stack.append(token)

            elif token == ")":
                try:
                    while True:
                        current_operator = operator_stack.pop()

                        if current_operator == "(":
                            break

                        rpn_code.append(current_operator)

                except IndexError:
                    print "(error) mismatched parens"

            elif token in ops:
                if len(operator_stack) > 0 and ((ops[token][2] == "left" and ops[token][1] <= ops[operator_stack[-1]][1]) or (ops[token][2] == "right" and ops[token][1] < ops[operator_stack[-1]][1])):
                    operator = operator_stack.pop()

                    if operator != "(":
                        rpn_code.append(operator_stack.pop())

                    else:
                        operator_stack.append("(")

                operator_stack.append(token)
    try:
        while len(operator_stack) != 0:
            current_operator = operator_stack.pop()

            if current_operator in ["(", ")"]:
                raise BadParenError

            rpn_code.append(current_operator)

    except BadParenError:
        print "(error) mismatched parens"

    return rpn_code

current_token = None

while True:
    try:
        tokens = parse(raw_input("-> "))
        stack = []

        if tokens == ["quit"]:
            sys.exit(0)

        tokens = compile_to_rpn(tokens)

        for token in tokens:
            current_token = token

            if token not in ops:
                stack.append(int(token))

            else:
                rhs, lhs = stack.pop(), stack.pop()
                stack.append(ops[token][0](lhs, rhs))

        if len(stack) > 1:
            raise InvalidStackError

        print "Result: %s\n" % stack[0]

    except ValueError:
        print "(error) token {%s} is a not a number or operator\n" % current_token

    except IndexError:
        print "(error) expression has insufficient number of values\n"

    except InvalidStackError:
        print "(error) too many values\n"

It works fine for simple expressions such as "3 + 4", but if I enter anything complicated, this happens:

$ ./rpn.py

-> 4 - 5 * 6 + 3 ^ 2

(error) too many values

Thanks in advance and I appreciate any help!

Answer 1

At least one problem with your code is here:

           if len(operator_stack) > 0 and ((ops[token][2] == "left" and ops[token][1] <= ops[operator_stack[-1]][1]) or (ops[token][2] == "right" and ops[token][1] < ops[operator_stack[-1]][1])):
                operator = operator_stack.pop()

                if operator != "(":
                    rpn_code.append(operator_stack.pop())

You pop from operator_stack and then do it again when appending to rpn_code. This triggers one of your exceptions. Replace the last line in this fragment with

                    rpn_code.append(operator)

And expressions like 5 * 6 + 4 will work properly. Unfortunately this isn't the only bug in your code because the example you give doesn't evaluate correctly. Perhaps this is because of another problem with your code: when doing this part of the algorithm (Wikipedia):

If the token is an operator, o1, then:

    while there is an operator token, o2, at the top of the operator stack, and either

        o1 is left-associative and its precedence is less than or equal to that of o2, or
        o1 is right associative, and has precedence less than that of o2,

    then pop o2 off the operator stack, onto the output queue;

    push o1 onto the operator stack.

You're only carrying it out once, not for as long as the while condition is met.