Question

3.9.中缀，前缀和后缀表达式

当你编写一个算术表达式如 B*C 时，表达式的形式使你能够正确理解它。在这种情况下，你知道 B 乘以 C, 因为乘法运算符 * 出现在表达式中。这种类型的符号称为中缀，因为运算符在它处理的两个操作数之间。看另外一个中缀示例，A+B*C，运算符 + 和 * 仍然出现在操作数之间。这里面有个问题是，他们分别作用于哪个运算数上，+ 作用于 A 和 B , 还是 * 作用于 B 和 C？表达式似乎有点模糊。

事实上，你已经读写过这些类型的表达式很长一段时间，所以它们对你不会导致什么问题。这是因为你知道运算符 +和 *。每个运算符都有一个优先级。优先级较高的运算符在优先级较低的运算符之前使用。唯一改变顺序的是括号的存在。算术运算符的优先顺序是将乘法和除法置于加法和减法之上。如果出现具有相等优先级的两个运算符，则使用从左到右的顺序排序或关联。

我们使用运算符优先级来解释下表达式 A+B*C。B 和 C 首先相乘，然后将 A 与该结果相加。(A+B)*C 将强制在乘法之前执行 A 和 B 的加法。在表达式 A+B+C 中，最左边的 + 首先使用。

虽然这一切对你来说都很明显。但请记住，计算机需要准确知道要执行的操作符和顺序。一种保证不会对操作顺序产生混淆的表达式的方法是创建一个称为完全括号表达式的表达式。这种类型的表达式对每个运算符都使用一对括号。括号没有歧义的指示操作的顺序。也没有必要记住任何优先规则。

表达式 A+B*C+D 可以重写为 ((A + (B * C)) + D) ，表明先乘法，然后是左边的加法，A + B + C + D 可以写为 (((A + B) + C) + D)，因为加法操作从左向右相关联。

有两种非常重要的表达式格式，你可能一开始不会很明显的看出来。中缀表达式 A+B, 如果我们移动两个操作数之间的运算符会发生什么？结果表达式变成 + A B。同样，我们也可以将运算符移动到结尾，得到 A B + ，这样看起来有点奇怪。

改变操作符的位置得到了两种新的表达式格式，前缀和后缀。前缀表达式符号要求所有运算符在它们处理的两个操作数之前。另一个方面，后缀要求其操作符在相应的操作数之后。看下更多的例子 (见 Table 2)

A+B*C 将在前缀中写为 + A * B C 。乘法运算符紧接在操作数 B 和 C 之前，表示 * 优先于 +。然后加法运算符出现在 A 和乘法的结果之前。

在后缀中，表达式将是 A B C * +，再次，操作的顺序被保留，因为 * 紧接在 B 和 C 之后出现，表示 * 具有高优先级，+ 优先级低。虽然操作符在它们各自的操作数前后移动，但是顺序相对于彼此保持完全相同。

Table 2

现在考虑中缀表达式 (A + B) * C，回想下，在这种情况下，中缀需要括号在乘法之前强制执行加法。然而，当 A+B 写到前缀中时，加法运算符简单的移动到操作数 + A B 之前。这个操作的结果成为乘法的第一个操作数。乘法运算符移动到整个表达式的前面，得出 * + A B C，同样，在后缀 A B +中，强制先加法。可以直接对该结果和剩余的操作数 C 相乘。然后，得出后缀表达式为 A B + C *。

再次考虑这三个表达式(见 Table 3)，括号不见了。为什么在前缀和后缀的时候不需要括号了呢？答案是操作符对于他们的操作数不再模糊，只有中缀才需要括号，前缀和后缀表达式的操作顺序完全由操作符的顺序决定。

Table 3

Table 4 展示了一些其他的例子

Table 4

3.9.1.中缀表达式转换前缀和后缀

到目前为止，我们已经使用特定方法在中缀表达式和等效前缀和后缀表达式符号之间进行转换。正如你可能期望的，有一些算法来执行转换，允许任何复杂表达式转换。

我们考虑的第一种技术使用前面讨论的完全括号表达式的概念。回想一下，A + B * C可以写成（A +（B * C）），以明确标识乘法优先于加法。然而，仔细观察,你可以看到每个括号对还表示操作数对的开始和结束，中间有相应的运算符。

看上面的子表达式（B * C）中的右括号。 如果我们将乘法符号移动到那个位置，并删除匹配的左括号，得到 B C *，我们实际上已经将子表达式转换为后缀符号。 如果加法运算符也被移动到其相应的右括号位置并且匹配的左括号被去除，则将得到完整的后缀表达式（见 Figure 6）。

Figure 6

如果我们不是将符号移动到右括号的位置，我们将它向左移动，我们得到前缀符号（见 Figure 7）。圆括号对的位置实际上是包含的运算符的最终位置的线索。

Figure 7

所以为了转换表达式，无论是对前缀还是后缀符号，先根据操作的顺序把表达式转换成完全括号表达式。然后将包含的运算符移动到左或右括号的位置，具体取决于需要前缀或后缀符号。

这里面有个更复杂的例子, (A + B) * C - (D - E) * (F + G) ，Figure 8 显示了如何转换为后缀和前缀。

Figure 8

3.9.2.中缀转后缀通用法

我们需要开发一个算法来将任何中缀表达式转换为后缀表达式。 为了做到这一点，我们仔细看看转换过程。

再次考虑表达式 A + B * C。如上所示，A B C * +是等价的后缀表达式。 我们已经注意到，操作数 A，B 和 C 保持在它们的相对位置。只有操作符改变位置。再看中缀表达式中的运算符。从左到右出现的第一个运算符为 +。 然而，在后缀表达式中，+ 在结束位置，因为下一个运算符 * 的优先级高于加法。 原始表达式中的运算符的顺序在生成的后缀表达式中相反。

当我们处理表达式时，操作符必须保存在某处，因为它们相应的右操作数还没有看到。 此外，这些保存的操作符的顺序可能由于它们的优先级而需要反转。这是在该示例中的加法和乘法的情况，由于加法运算符在乘法运算符之前，并且具有较低的优先级，因此需要在使用乘法运算符之后出现。 由于这种顺序的反转，考虑使用栈来保存运算符直到用到它们是有意义的。

(A + B)* C的情况会是什么样呢？ 回想一下，A B + C *是等价的后缀表达式。从左到右处理此中缀表达式，我们先看到 +。 在这种情况下，当我们看到 *，+已经放置在结果表达式中，由于括号它的优先级高于*。 我们现在可以开始看看转换算法如何工作。当我们看到左括号时，我们保存它，表示高优先级的另一个运算符将出现。该操作符需要等到相应的右括号出现以表示其位置（回忆完全括号的算法）。 当右括号出现时，可以从栈中弹出操作符。

当我们从左到右扫描中缀表达式时，我们将使用栈来保留运算符。这将提供我们在第一个例子中注意到的反转。 堆栈的顶部将始终是最近保存的运算符。每当我们读取一个新的运算符时，我们需要考虑该运算符如何与已经在栈上的运算符（如果有的话）比较优先级。

假设中缀表达式是一个由空格分隔的标记字符串。 操作符标记是*，/，+和 - ，以及左右括号。操作数是单字符 A，B，C 等。 以下步骤将后缀顺序生成一个字符串。

1. 创建一个名为 opstack 的空栈以保存运算符。给输出创建一个空列表。
2. 通过使用字符串方法拆分将输入的中缀字符串转换为标记列表。
3. 从左到右扫描标记列表。
   • 如果标记是操作数，将其附加到输出列表的末尾。
   • 如果标记是左括号，将其压到 opstack 上。
   • 如果标记是右括号，则弹出 opstack，直到删除相应的左括号。将每个运算符附加到输出列表的末尾。
   • 如果标记是运算符，*，/，+或 - ，将其压入 opstack。但是，首先删除已经在 opstack 中具有更高或相等优先级的任何运算符，并将它们加到输出列表中。
4. 当输入表达式被完全处理时，检查 opstack。仍然在栈上的任何运算符都可以删除并加到输出列表的末尾。

Figure 9 展示了对表达式 A * B + C * D 的转换算法。注意，第一个 * 在看到 + 运算符时被删除。另外，当第二个 * 出现时， + 保留在栈中，因为乘法优先级高于加法。在中缀表达式的末尾，栈被弹出两次，删除两个运算符，并将 + 作为后缀表达式中的最后一个运算符。

Figure 9

为了在 Python 中编写算法，我们使用一个名为 prec 的字典来保存操作符的优先级。这个字典将每个运算符映射到一个整数，可以与其他运算符的优先级（我们使用整数3，2和1）进行比较。左括号将赋予最低的值。这样，与其进行比较的任何运算符将具有更高的优先级，将被放置在它的顶部。第15行将操作数定义为任何大写字符或数字。完整的转换函数见 ActiveCode 1。

from pythonds.basic.stack import Stack

def infixToPostfix(infixexpr):
    prec = {}
    prec["*"] = 3
    prec["/"] = 3
    prec["+"] = 2
    prec["-"] = 2
    prec["("] = 1
    opStack = Stack()
    postfixList = []
    tokenList = infixexpr.split()

    for token in tokenList:
        if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
            postfixList.append(token)
        elif token == '(':
            opStack.push(token)
        elif token == ')':
            topToken = opStack.pop()
            while topToken != '(':
                postfixList.append(topToken)
                topToken = opStack.pop()
        else:
            while (not opStack.isEmpty()) and \
               (prec[opStack.peek()] >= prec[token]):
                  postfixList.append(opStack.pop())
            opStack.push(token)

    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    return " ".join(postfixList)

print(infixToPostfix("A * B + C * D"))
print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))

执行结果如下

>>> infixtopostfix("( A + B ) * ( C + D )")
'A B + C D + *'
>>> infixtopostfix("( A + B ) * C")
'A B + C *'
>>> infixtopostfix("A + B * C")
'A B C * +'
>>>

3.9.3.后缀表达式求值

作为最后栈的示例，我们考虑对后缀符号中的表达式求值。在这种情况下，栈再次是我们选择的数据结构。但是，在扫描后缀表达式时，它必须等待操作数，而不像上面的转换算法中的运算符。 解决问题的另一种方法是，每当在输入上看到运算符时，计算两个最近的操作数。

要详细的了解这一点，考虑后缀表达式 4 5 6 * +， 首先遇到操作数 4 和 5，此时，你还不确定如何处理它们，直到看到下一个符号。将它们放置到栈上，确保它们在下一个操作符出现时可用。

在这种情况下，下一个符号是另一个操作数。所以，像先前一样，压入栈中。并检查下一个符号。现在我们看到了操作符 *，这意味着需要将两个最近的操作数相乘。通过弹出栈两次，我们可以得到正确的两个操作数，然后执行乘法（这种情况下结果为 30）。

我们现在可以通过将其放回栈中来处理此结果，以便它可以表示为表达式后面的运算符的操作数。当处理最后一个操作符时，栈上只有一个值，弹出并返回它作为表达式的结果。Figure 10 展示了整个示例表达式的栈的内容。

Figure 10

Figure 11 是个稍微复杂的示例，7 8 + 3 2 + / 。在这个例子中有两点需要注意，首先，栈的大小增长收缩，然后再子表达式求值的时候再次增长。第二，除法操作需要谨慎处理。回想下，后缀表达式的操作符顺序没变，仅仅改变操作符的位置。当用于除法的操作符从栈中弹出时，它们被反转。由于除法不是交换运算符，换句话说 15/5和 5/15 不同，因此我们必须保证操作数的顺序不会交换。

Figure 11

假设后缀表达式是一个由空格分隔的标记字符串。 运算符为*，/，+和 - ，操作数假定为单个整数值。 输出将是一个整数结果。

1. 创建一个名为 operandStack 的空栈。
2. 拆分字符串转换为标记列表。
3. 从左到右扫描标记列表。
   • 如果标记是操作数，将其从字符串转换为整数，并将值压到operandStack。
   • 如果标记是运算符*，/，+或-，它将需要两个操作数。弹出operandStack 两次。 第一个弹出的是第二个操作数，第二个弹出的是第一个操作数。执行算术运算后，将结果压到操作数栈中。
4. 当输入的表达式被完全处理后，结果就在栈上，弹出 operandStack 并返回值。

用于计算后缀表达式的完整函数见 ActiveCode 2，为了辅助计算，定义了一个函数 doMath, 它将获取两个操作数和运算符，执行相应的计算。

from pythonds.basic.stack import Stack

def postfixEval(postfixExpr):
    operandStack = Stack()
    tokenList = postfixExpr.split()

    for token in tokenList:
        if token in "0123456789":
            operandStack.push(int(token))
        else:
            operand2 = operandStack.pop()
            operand1 = operandStack.pop()
            result = doMath(token,operand1,operand2)
            operandStack.push(result)
    return operandStack.pop()

def doMath(op, op1, op2):
    if op == "*":
        return op1 * op2
    elif op == "/":
        return op1 / op2
    elif op == "+":
        return op1 + op2
    else:
        return op1 - op2

print(postfixEval('7 8 + 3 2 + /'))