将后缀表达式转换为中缀表达式

引言

后缀表达式，又称逆波兰表示法，是一种数学表达式的语法，其中数学运算符总是放在操作数之后。例如，1 和 2 的加法在后缀表达式中写为“1 2 +”。计算机科学家和软件开发人员对后缀表达式感兴趣，因为后缀表达式可以使用简单的栈式机器轻松高效地求值。此外，后缀表达式已用于某些手持计算器，因为它允许输入和求值任意复杂的表达式，而无需使用括号，也无需用户跟踪中间结果。特别是，惠普公司生产了许多使用后缀表达式的科学和工程计算器。

虽然后缀表达式易于计算机高效求值，但人类阅读起来可能很困难。使用标准带括号中缀表达式的复杂表达式通常比相应的后缀表达式更具可读性。因此，我们有时希望允许最终用户使用中缀表达式，然后将其转换为后缀表达式进行计算机处理。有时，表达式以后缀形式存储或生成，我们希望将其转换为中缀表达式以便于阅读和编辑。

在 The Code Project 和其他地方有许多文章讨论了求值后缀表达式以及将标准中缀表达式转换为后缀表达式的方法。讨论将后缀表达式转换为中缀表达式的方法并不常见。在本文中，我将介绍一种将后缀表达式转换为中缀表达式的通用算法，并提供 C# 实现。

通用方法

求值后缀表达式最常用的算法是使用栈来维护中间结果。表达式从左到右扫描。遇到数字时，将其压入栈中。遇到运算符时，将操作数从栈中弹出，并将结果压回栈中。扫描完成后，表达式的最终值留在栈中。

我们将使用类似的基于栈的方法将后缀表达式转换为中缀表达式。通用算法将以相同的方式工作，但我们不是使用栈来存储中间结果，而是使用它来存储中间中缀子表达式。基本思想如下：

1. 后缀表达式从左到右扫描。
2. 如果标记是数字，则将标记压入栈中。
3. 如果标记是运算符，则将栈顶的两个中缀子表达式弹出，并通过以正常中缀方式将这些子表达式与运算符组合来构造新的中缀表达式。然后将结果表达式压入栈中。最初，我们将每个子表达式放在括号中，以确保最终表达式中求值的正确顺序。

表 1 说明了“1 2 * 3 4 * + 5 *”的转换。

Token	栈（| 分隔）	注释
1	1	标记是数字。它被压入栈中。
2	2 | 1	标记是数字。它被压入栈中。
*	1*2	标记是运算符。栈顶的两个元素被弹出，并以中缀方式与运算符组合。结果表达式“1*2”被压入栈中。
3	3 | 1*2	标记是数字。它被压入栈中。
4	4 | 3 | 1*2	标记是数字。它被压入栈中。
*	3*4 | 1*2	标记是运算符。栈顶的两个元素被弹出，并以中缀方式与运算符组合。结果表达式“3*4”被压入栈中。
+	(1*2)+(3*4)	标记是运算符。栈顶的两个元素被弹出，并以中缀方式与运算符组合。结果表达式“(3*4)+(1*2)”被压入栈中。
5	5 | (1*2)+(3*4)	标记是数字。它被压入栈中。
+	5*((1*2)+(3*5))	标记是运算符。栈顶的两个元素被弹出，并以中缀方式与运算符组合。结果表达式“5*((1*2)+(3*4))”被压入栈中。由于没有更多标记，这是最终的中缀表达式。

括号问题

假设表达式 A 是“3+2”，表达式 B 是“5”。如果我们构造 A + B 而不添加额外的括号，我们将得到“3+2*5”。这肯定不是预期的。由于 A 求值为 5，B 求值为 5，我们期望一个求值为 10 的表达式。然而，这个表达式求值为 13，因为运算符优先级的正常规则要求我们首先求值“2*5”，然后加 3。

我们在上一节中通过始终在子表达式周围添加括号来解决此问题。采用这种方法，A + B 将生成“(3+2)+5”，这是我们想要的。然而，这种解决方案的问题在于它有时会生成带有许多不必要括号的表达式。实际上，表 1 中生成的最终表达式等价于“5*(1*2+3*4)”，它少了两个括号对。在复杂表达式的情况下，多余的括号会显著降低表达式的可读性。

解决方案是仅在需要时才在子表达式周围添加括号。仅当子表达式的主运算符的优先级低于用于将其与另一个子表达式组合的运算符时，才需要在子表达式周围添加括号。否则，无需任何额外的括号即可保持正确的求值顺序。

更正式地说，假设我们正在使用操作符 opNew 从子表达式 A 和 B 构造一个新表达式。请注意，A 本身是使用某个操作符 operA 构造的，B 是使用某个操作符 operB 构造的。在我们构造新表达式时，我们可以通过比较 operA 和 operB 的优先级与 operNew 来确定是否需要在 A 或 B 周围添加括号。如果它们的优先级小于或大于 operNew，则不需要括号。否则，我们将在构造新表达式时在子表达式周围添加括号。

假设 operA 是 +，operB 是 *，operNew 是 *。由于 operNew 的优先级高于 operA，我们需要在 A 周围添加括号。由于 operNew 的优先级与 operB 相同，我们不必在 B 周围添加括号。因此，我们的新表达式将采用 (A)*B 的形式。我们可以更具体地假设 A 是“1+2”，B 是“3*4”。应用括号规则，我们的新表达式将是“(1+2)*3*4”，其中只有在需要括号的子表达式周围才添加括号，以确保正确的求值顺序。

在表 2 中，我们演示了与表 1 相同的示例，但这次我们使用括号规则来确定何时在子表达式周围添加括号。

Token	栈（| 分隔）	注释
1	1	标记是数字。它被压入栈中。
2	2 | 1	标记是数字。它被压入栈中。
*	1*2	标记是运算符。栈顶的两个元素被弹出，并以中缀方式与运算符组合。结果表达式“1*2”被压入栈中。
3	3 | 1*2	标记是数字。它被压入栈中。
4	4 | 3 | 1*2	标记是数字。它被压入栈中。
*	3*4 | 1*2	标记是运算符。栈顶的两个元素被弹出，并以中缀方式与运算符组合。结果表达式“3*4”被压入栈中。
+	1*2+3*4	标记是运算符。栈顶的两个元素被弹出，并以中缀方式与运算符组合。结果表达式“3*4+1*2”被压入栈中。请注意，两个子表达式都没有放在括号中，因为 * 的优先级高于 +。
5	5 | 1*2+3*4	标记是数字。它被压入栈中。
+	5*(1*2+3*5)	标记是运算符。栈顶的两个元素被弹出，并以中缀方式与运算符组合。结果表达式“5*(1*2+3*4)”被压入栈中。右侧子表达式放在括号中，因为 + 的优先级低于 *。由于没有更多标记，这是最终的中缀表达式。

C# 实现

清单 1 包含将后缀表达式转换为中缀表达式函数的完整 C# 实现。类 Intermediate 用于表示栈上的中间子表达式。成员 expr 存储子表达式字符串，成员 oper 存储用于构造子表达式的运算符。oper 用于确定当 expr 组合成一个更大的表达式时是否需要添加括号。事实证明，唯一需要添加括号的时间是当使用 * 或 / 构造新表达式时，并且子表达式是使用 + 或 - 构造的。

//
// class used to represent intermediate expressions on the stack.
//
public class Intermediate
{
    public string expr;     // subexpression string
    public string oper;     // the operator used to create this expression

    public Intermediate(string expr, string oper)
    {
        this.expr = expr;
        this.oper = oper;
    }
}

//
// PostfixToInfix
//
static string PostfixToInfix(string postfix)
{
    // Assumption: the postfix expression to be processed is space-delimited.
    // Split the individual tokens into an array for processing.
    var postfixTokens = postfix.Split(' ');

    // Create stack for holding intermediate infix expressions
    var stack = new Stack<Intermediate>();

    foreach(string token in postfixTokens)
    {
        if (token == "+" || token == "-")
        {
            // Get the left and right operands from the stack.
            // Note that since + and - are lowest precedence operators,
            // we do not have to add any parentheses to the operands.
            var rightIntermediate = stack.Pop();
            var leftIntermediate = stack.Pop();

            // construct the new intermediate expression by combining the left and right 
            // expressions using the operator (token).
            var newExpr = leftIntermediate.expr + token + rightIntermediate.expr;

            // Push the new intermediate expression on the stack
            stack.Push(new Intermediate(newExpr, token));
        }
        else if (token == "*" || token == "/")
        {
            string leftExpr, rightExpr;
            
            // Get the intermediate expressions from the stack.  
            // If an intermediate expression was constructed using a lower precedent
            // operator (+ or -), we must place parentheses around it to ensure 
            // the proper order of evaluation.
            
            var rightIntermediate = stack.Pop();
            if (rightIntermediate.oper == "+" || rightIntermediate.oper == "-")
            {
                rightExpr = "(" + rightIntermediate.expr + ")";
            }
            else
            {
                rightExpr = rightIntermediate.expr;
            }

            var leftIntermediate = stack.Pop();
            if (leftIntermediate.oper == "+" || leftIntermediate.oper == "-")
            {
                leftExpr = "(" + leftIntermediate.expr + ")";
            }
            else
            {
                leftExpr = leftIntermediate.expr;
            }

            // construct the new intermediate expression by combining the left and right 
            // using the operator (token).
            var newExpr = leftExpr + token + rightExpr;

            // Push the new intermediate expression on the stack
            stack.Push(new Intermediate(newExpr, token));
        }
        else 
        {
            // Must be a number. Push it on the stack.
            stack.Push(new Intermediate(token, ""));
        }
    }

    // The loop above leaves the final expression on the top of the stack.
    return stack.Peek().expr;
}