调车场算法中引起计算的复杂表达式

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: %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"

它适用于“3+4”等简单表达式，但如果输入任何复杂的内容，则会发生以下情况：

$ ./rpn.py

-> 4 - 5 * 6 + 3 ^ 2

(error) too many values

提前谢谢你，谢谢你的帮助！在

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时再次执行该操作。这会触发一个异常。将此片段中的最后一行替换为

^{pr2}$

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

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.

你只执行一次，而不是只要满足while条件。在