评估 python 中的后缀？

Question

我想编写一个函数来计算作为列表传递的后缀表达式。到目前为止我有：

def evalPostfix(text):
    s = Stack()
    for symbol in text:
        if symbol in "0123456789":
            s.push(int(symbol))
        if not s.is_empty():
            if symbol == "+":
                plus = s.pop() + s.pop()
            if symbol == "-":
                plus = s.pop() - s.pop()
            if symbol == "*":
                plus = s.pop() * s.pop()
            if symbol == "/":
                plus = s.pop() / s.pop()

但我觉得我的做法不对。帮忙？

Answer 1

你有几个问题：

遇到运算符后，您正在丢弃该值。要解决此问题，您必须将任何运算符的结果推回堆栈，然后继续下一步。
遇到数字时，您不会跳过其余逻辑（这不会使您的代码 return 成为错误答案，但仍然不是很聪明）
你的函数没有return任何东西。

像这样的东西应该可以工作：

def eval_postfix(text):
    s = list()
    for symbol in text:
        if symbol in "0123456789":
            s.append(int(symbol))

        plus = None
        elif not s.is_empty():
            if symbol == "+":
                plus = s.pop() + s.pop()
            elif symbol == "-":
                plus = s.pop() - s.pop()
            elif symbol == "*":
                plus = s.pop() * s.pop()
            elif symbol == "/":
                plus = s.pop() / s.pop()
        if plus is not None:
            s.append(plus)
        else:
             raise Exception("unknown value %s"%symbol)
    return s.pop()

Answer 2

这是一个可能适合您的解决方案。我已尝试尽可能少地更改您的代码。

更改 #1：与其检查 symbol 是否介于 0 和 9 之间，不如尝试将 symbol（以 string 开头）转换为 int。如果成功，您可以将 symbol 视为操作数。（这允许您的代码处理多位数。）

更改 #2：如果 text 中出现非数字、非运算符，则引发错误。（您不希望其中有任何其他内容。）

更改 #3：使用 eval 而不是写出每个运算符。 eval 带来了很多安全问题，但我认为在这里，因为我们要确保所有内容都是数字或运算符，所以我们没问题。

更改 #4：将中间结果推入堆栈。

更改 #5：Return s.pop() 在列表用完之后。您可能想要添加一行以确认 s 此时仅包含一个值。

警告：请注意，此代码假定每次遇到运算符时 s 将包含两个值。如果另一对 try/except 语句不正确，您可能想要捕获将引发的错误。

def evalPostfix(text):
    s = Stack()
    for symbol in text:
        try:
            result = int(symbol)
        except ValueError:
            if symbol not in '+-*/':
                raise ValueError('text must contain only numbers and operators')
            result = eval('%d %s %d' % (s.pop(), symbol, s.pop()))
        s.push(result)
    return s.pop()

Answer 3

Hosane 对您的问题提供了一个非常详细的答案，但我认为我看到了一个错误，尽管我承认我不是这方面的专家。

由于您使用的是 pop，因此您的计算过程如下。（堆栈中的最后一个数字）（运算符）（堆栈中倒数第二个数字）例如，如果您的列表中有 ["3","2","+"]，您将得到 3+2

这对于加法或乘法来说没问题，但如果你采用除法或减法，这将导致错误的答案。例如 post 中的 (3-2) fix 将是 [3,2,-]。当它应该是 (3-2) 时，您的代码会将其计算为 (2-3)。

所以你应该将除法和减法 if cases 改为;

elif symbol=="-":
        s.append(-stack.pop() + stack.pop())
elif symbol=="/":
        s.append(1/stack.pop() * stack.pop())

Answer 4

工作代码是 K&R C 示例的翻译，

def eval_postfix(text):

    stack = []
    tokens = text.split(" ")

    for token in tokens:

        if token.strip() == '':
            continue 

        elif token == "+":
            stack.append(stack.pop() + stack.pop())

        elif token == "-":
            op2 = stack.pop() 
            stack.append(stack.pop() - op2)

        elif token == '*':
            stack.append(stack.pop() * stack.pop())

        elif token == '/':
            op2 = stack.pop()
            if op2 != 0.0:
                stack.append(stack.pop() / op2)
            else:
                raise ValueError("division by zero found!")

        elif (is_number(token)):
                stack.append(float(token))

        else:
            raise ValueError("unknown token {0}".format(token))


    return stack.pop()

评估 python 中的后缀？

Evaluating postfix in python?

python

postfix-notation