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

疑问点 #

我在尝试用Python实现上述中缀转后缀的算法，但对Remove the open parenthesis from operators这一行存在疑惑：当operators列表中同时存在多个左括号时，应该移除哪一个？

解答 #

你完全不用纠结——这里要移除的就是栈顶的那个左括号。

原因很简单：算法处理右括号时，会从栈顶开始逐个弹出运算符到后缀列表，直到碰到第一个左括号为止。这个左括号就是和当前处理的右括号配对的那一个，此时它必然处于栈顶位置。栈里更深处的其他左括号属于更早出现的括号对，会等后续处理到对应的右括号时再处理，和当前的右括号无关。

举个实际例子，比如处理表达式(3 + (4 * 5))：
当处理到最后一个右括号)时，operators栈的内容是['(', '+', '(']，循环会先弹出'*'到postfix，此时栈顶变成'('，循环停止。这时候直接移除栈顶的这个'('就好，栈里剩下的'('和'+'会留到后续步骤处理。

内容的提问来源于stack exchange，提问作者user829347