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

但我觉得我的方法不正确，能帮忙吗？

- ASm

---

你为什么认为这种方法是错误的？ - Stefan Pochmann

@dbliss 我正在使用栈（抽象数据类型），并且有一个类使用push和pop方法向栈中添加/删除元素。 - ASm

主要是因为我不确定如何返回正确的值。 - ASm

@dbliss 如果可能的话，我希望能够处理更多的操作，至少包括乘法和除法。 - ASm

你可以处理乘法和除法。plus是一个糟糕的变量名，因为它不仅保存加法的结果，还保存任何操作的结果。你没看到代码中吗？我应该在之前的评论中添加：这段代码只适用于每个表达式只有一个运算符的情况。 - abcd

Answer 1

您有几个问题：

1. 在遇到运算符后，您会丢弃值。要解决这个问题，您需要将任何运算符的结果推回栈中，然后继续下一步。
2. 当遇到数字时，您不跳过其余逻辑（虽然这不会使您的代码返回错误的答案，但仍然不是很聪明）
3. 您的函数没有返回任何内容。

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

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

- Hosane

---

很好。你的回答让我意识到中间结果应该被推到堆栈中。我的回答看起来正确吗？ - abcd

你换到list上是为了让你和其他人都可以测试它吗？你可以使用class Stack(list): push = list.append。我只是这样说因为我喜欢你试图不改变太多的做法。 - Stefan Pochmann

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Hosane

我认为OP的push可能会将项添加到栈的前面，而不是像append那样添加到末尾。由于OP没有指定，所以我们无法确定... - abcd

是的，push将项目添加到列表的前面，我使用堆栈是因为您无法将append方法用于堆栈，但是在列表上使用append方法同样有效，非常感谢@Hosane。 - ASm

Answer 2

这里有一个解决方案，可能适用于你。我尽量保持你的代码改动最小。

更改#1：与其检查“symbol”是否在0到9之间，不妨尝试将“symbol”（起初是一个字符串）转换为“int”。如果成功，您可以将“symbol”视为操作数。（这样可以处理多位数字。）

更改#2：如果在文本中出现非数字、非运算符，则引发错误。（您不希望还有别的东西。）

更改#3：使用eval而不是编写每个运算符。eval带有许多安全问题，但我认为在这里，因为我们确保一切都是数字或运算符，所以没关系。

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

更改#5：在列表用完后返回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() 

- abcd

---

我认为“我尽可能少地更改了您的代码”是个谎言 :-P - Stefan Pochmann

哈，是的，那是我一开始的目标。 - abcd

我并不是很喜欢异常处理的方法。如果你只需要判断单个字符数字（这里就是这种情况），你也可以使用 symbol.isdigit() 方法来解决。 - Hosane

在这里使用eval是一个坏主意，因为eval在任何地方都是一个坏主意。而且，即使eval是合理的，使用Python解析器来评估算术完全忽略了从头开始编写表达式求值器的重点。 - 9999years

Answer 3

Hosane已经对你的问题提供了详细的答案，但我认为有一个错误，虽然我不是这个主题的专家。

由于您使用了pop，所以您的计算如下。 （堆栈中的最后一个数字）（运算符）（堆栈中的倒数第二个数字） 例如，如果您的列表中有["3","2","+"]，则会得到3+2。

这对于加法或乘法来说是可以的，但如果您进行除法或减法，则会得出错误的答案。例如，后缀表达式中的(3-2)将是[3,2,-]。您的代码会将其计算为(2-3)，但应该是(3-2)。

因此，您应该将除法和减法的情况更改为;

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

- Haritha Jayasinghe

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

- rjha94