分流场算法中的复杂表达式导致计算器错误

Question

我已经实现了调车场算法，如下所示：

#!/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: %sn" % stack[0]
    except ValueError:
        print "(error) token {%s} is a not a number or operatorn" % current_token
    except IndexError:
        print "(error) expression has insufficient number of valuesn"
    except InvalidStackError:
        print "(error) too many valuesn"

它适用于简单的表达式，例如"3 + 4"，但是如果我输入任何复杂的东西，就会发生这种情况：

$ ./rpn.py

-> 4 - 5 * 6 + 3 ^ 2

（错误）值过多

提前感谢，感谢任何帮助！

Answer 1

你的代码至少有一个问题在这里：

           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())

您从operator_stack弹出，然后在追加到rpn_code时再次执行此操作。这会触发您的一个异常。将此片段中的最后一行替换为

                    rpn_code.append(operator)

像5 * 6 + 4这样的表达式将正常工作。不幸的是，这不是代码中唯一的错误，因为您给出的示例无法正确评估。也许这是因为您的代码存在另一个问题：在执行算法的这一部分（维基百科）时：

如果令牌是运算符 o1，则：

    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.

你只执行一次，只要满足条件，就不能