用Python将中缀表达式转换为后缀表达式的算法

Question

我正在尝试用Python编写一个算法，这个算法的目的是把简单的数学表达式从中缀形式转换为后缀形式：

Create a new empty list, 'operators'
Create a new empty list 'postfix'

For each token in the infix expression
  If the token is an integer then
    Append the token to 'postfix'
  If the token is an operator then
    While 'operators' is not empty and the last item in 'operators' is not an open parenthesis
    and precedence(token) < precedence(last item in 'operators') do
        Remove the last item from 'operators' and append it to 'postfix'
      Append the token to 'operators'
  If the token is an open parenthesis then
    Append the token to 'operators'
  If the token is a close parenthesis then
    While the last item in 'operators' is not an open parenthesis do
        Remove the last item from 'operators' and append it to 'postfix'
      Remove the open parenthesis from 'operators'

While 'operators' is not the empty list do
  Remove the last item from 'operators' and append it to 'postfix'

Return 'postfix' as the result of the algorithm

不过，我对“从operators中移除开括号”这一行有点困惑。我见过在operators中同时存在多个开括号的情况。那么，这时候应该移除哪一个呢？

Answer 1

你刚找到的那个，当然是最合适的。别忘了上下文：

    **While** the last item in *operators* is not an open parenthesis **do**
        Remove the last item from *operators* and append it to *postfix*
      Remove the open parenthesis from *operators*

这个 while 循环会一直删除东西，直到 operators 中最后一个项目是一个左括号，然后你就把这个左括号也删掉。

我想把这个算法用一种更简单、更易读的方式展示出来，所以我写了一个简单的 Python 版本。

for infix in '3+4*5', '(3+4)*5':

    precedence = '+-*/'.index
    operators = []
    postfix = []
    for token in infix:
        if token.isdigit():
            postfix.append(token)
        if token in '+-*/':
            while operators and operators[-1] != '(' and precedence(token) < precedence(operators[-1]):
                postfix.append(operators.pop())
            operators.append(token)
        if token == '(':
            operators.append(token)
        if token == ')':
            while operators[-1] != '(':
                postfix.append(operators.pop())
            operators.pop()
    while operators:
        postfix.append(operators.pop())

    print(*postfix)

在线尝试这个！：

3 4 5 * +
3 4 + 5 *

Answer 2

缩进看起来有点乱，因为有些行前面有星号 **，而有些行没有。

    **While** the last item in *operators* is not an open parenthesis **do**
        Remove the last item from *operators* and append it to *postfix*
     Remove the open parenthesis from *operators*

第三行开头不应该有多余的空格。应该是这样的：

    While the last item in *operators* is not an open parenthesis do
        Remove the last item from *operators* and append it to *postfix*
    Remove the open parenthesis from *operators*

因为 Remove 指令紧接在 While 循环的结束后，而 While 循环的条件是“操作符列表中的最后一个项目不是一个左括号”，这意味着当 While 循环结束时，操作符列表中的最后一个项目必须是一个左括号。

这是你此时唯一能看到并且可以移除的左括号。

重要的是要注意，operators 是一个 栈，也叫做 后进先出 结构：你只能看到、访问和移除它的最后一个（或“顶部”）元素。所以，这个左括号是你此时唯一能看到的，也是唯一能移除的。

要注意，这三行代码只有在假设括号在中缀表达式中是正确匹配的情况下才能正常工作。如果你按照写的方式在像 3+4) 这样的表达式上运行这个算法，里面有一个不匹配的右括号，那么 While 循环“只要最后一个项目不是左括号，就移除最后一个项目”会移除所有项目，然后栈就会空了，程序会崩溃，因为你试图从一个空栈中移除一个项目。