2

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

#!/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

（错误）太多的值

在此先感谢，感谢您的帮助！

4

1 回答 1

0

您的代码至少存在一个问题：

           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)

并且表达式 like5 * 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.

你只执行一次，只要满足 while 条件就不会。

于 2015-06-16T19:23:52.270 回答