前缀、中缀和后缀表达式的比较与总结

前缀表达式（Prefix）、中缀表达式（Infix）和后缀表达式（Postfix）是三种常见的数学表达式表示法。它们在运算顺序和括号的使用上有所不同。下面是这三种表达式的总结、优缺点和具体示例。

1. 中缀表达式（Infix Expression）

中缀表达式是我们日常生活中最常见的数学表达式格式。在中缀表达式中，操作符位于两个操作数之间。例如：

  • 3 + 4
  • a * (b + c)
  • (3 + 4) * 5

计算规则：

  • 需要括号来明确运算顺序。
  • 运算符的优先级（如 * 比 + 优先）和括号决定了运算顺序。
  • 解析中缀表达式通常需要先将其转换为其他形式（如前缀或后缀）以便进行计算。

示例：

1
表达式： (3 + 4) * 5

计算步骤：

  1. 首先计算括号中的 3 + 4 = 7。
  2. 然后计算 7 * 5 = 35，最终结果为 35。

2. 后缀表达式（Postfix Expression，也称为逆波兰表示法）

后缀表达式的特点是操作符位于操作数之后，避免了括号的使用和运算符优先级的处理。在后缀表达式中，操作符紧随其操作数之后。例如：

  • 3 4 +
  • a b c + *
  • (3 + 4) * 5 转换为后缀表达式是：3 4 + 5 *

计算规则：

  • 操作数入栈：遇到操作数时，将其压入栈中。
  • 操作符出栈计算：遇到操作符时，从栈中弹出两个操作数，进行计算，再将结果压入栈中。
  • 计算完后，栈中剩下的唯一元素即为结果。

示例：

1
后缀表达式： 3 4 + 5 *

计算步骤：

  1. 扫描到 3，将其压入栈中：栈 = [3]。
  2. 扫描到 4，将其压入栈中：栈 = [3, 4]。
  3. 扫描到 +，弹出 4 和 3，计算 3 + 4 = 7，将 7 压入栈中：栈 = [7]。
  4. 扫描到 5，将其压入栈中：栈 = [7, 5]。
  5. 扫描到 *，弹出 5 和 7，计算 7 * 5 = 35，将 35 压入栈中：栈 = [35]。
  6. 扫描结束，栈中的唯一元素 35 即为结果。

3. 前缀表达式（Prefix Expression，也称为波兰表示法）

前缀表达式的特点是操作符位于操作数之前。前缀表达式不需要括号来明确运算顺序。它的格式是先写操作符，然后是两个操作数。例如：

  • + 3 4
  • * + 3 4 5
  • (3 + 4) * 5 转换为前缀表达式是：* + 3 4 5

计算规则：

  • 操作数入栈：遇到操作数时，将其压入栈中。
  • 操作符出栈计算：遇到操作符时，从栈中弹出两个操作数进行运算，结果再压入栈中。
  • 计算完后，栈中剩下的唯一元素即为结果。

示例：

1
前缀表达式： * + 3 4 5

计算步骤：

  1. 扫描到 5，将其压入栈中：栈 = [5]。
  2. 扫描到 4，将其压入栈中：栈 = [5, 4]。
  3. 扫描到 +，弹出 4 和 5，计算 4 + 5 = 9，将 9 压入栈中：栈 = [9]。
  4. 扫描到 3，将其压入栈中：栈 = [9, 3]。
  5. 扫描到 *，弹出 3 和 9，计算 9 * 3 = 27，将 27 压入栈中：栈 = [27]。
  6. 扫描结束，栈中的唯一元素 27 即为结果。

表达式中括号的使用

带括号的表达式在转换成后缀或前缀表达式时，括号用于控制运算的优先级。在处理中，括号需要遵循特定的规则：

对于后缀表达式的转换：

  1. 左括号 (：

    • 当遇到左括号时，将其压入栈中，表示一个新的子表达式开始。

  2. 右括号 )：

    • 当遇到右括号时，将栈中的操作符弹出并输出，直到遇到左括号为止。此时左括号被弹出，但不输出。

  3. 操作符：

    • 操作符会根据优先级决定是否压入栈中。如果栈顶操作符的优先级较高，则先弹出栈顶操作符进行计算，否则将当前操作符压入栈中。

示例：表达式 (3 + 4) * 5

  1. (：压入栈中：栈 = [(]
  2. 3：压入栈中：栈 = [(, 3]
  3. +：压入栈中：栈 = [(, 3, +]
  4. 4：压入栈中：栈 = [(, 3, +, 4]
  5. )：弹出 + 和 3、4 进行计算，得到 7，然后左括号被弹出，栈 = [7]
  6. *：压入栈中：栈 = [7, *]
  7. 5：压入栈中：栈 = [7, *, 5]
  8. 计算完毕，弹出 *、7 和 5 进行计算，得到 35。

所以，后缀表达式为：3 4 + 5 *。

对于前缀表达式的转换：

  1. 左括号 (：

    • 当遇到左括号时，将其压入栈中，表示一个新的子表达式开始。

  2. 右括号 )：

    • 当遇到右括号时，弹出栈中的操作符并进行计算，直到遇到左括号为止。此时左括号被弹出，但不输出。

  3. 操作符：

    • 操作符会根据优先级决定是否压入栈中。如果栈顶操作符的优先级较低，则先弹出栈顶操作符进行计算，否则将当前操作符压入栈中。

示例：表达式 (3 + 4) * 5

  1. (：压入栈中：栈 = [(]
  2. 3：压入栈中：栈 = [(, 3]
  3. +：压入栈中：栈 = [(, +, 3]
  4. 4：压入栈中：栈 = [(, +, 3, 4]
  5. )：弹出 + 和 3、4 进行计算，得到 7，然后左括号被弹出，栈 = [7]
  6. *：压入栈中：栈 = [7, *]
  7. 5：压入栈中：栈 = [7, *, 5]
  8. 计算完毕，弹出 *、7 和 5 进行计算，得到 35。

所以，前缀表达式为：* + 3 4 5。

总结对比

特性 中缀表达式（Infix） 后缀表达式（Postfix） 前缀表达式（Prefix）
运算顺序 需要根据优先级和括号来决定运算顺序 运算顺序由操作符的顺序决定，操作符紧跟在操作数之后 运算顺序由操作符的顺序决定，操作符在操作数之前
括号 需要括号来明确运算顺序 不需要括号 不需要括号
运算符优先级 需要处理运算符优先级（如 * 优先于 +） 不需要运算符优先级，顺序即是优先级 不需要运算符优先级，顺序即是优先级
计算方式 直接计算，但需要先解析优先级和括号 使用栈处理，顺序执行 使用栈处理，顺序执行
表达式实例 (3 + 4) * 5 3 4 + 5 * * + 3 4 5

适用场景：

  • 中缀表达式：最常用，容易理解，适合人类阅读，但计算机在处理时需要优先转换为其他形式（如后缀或前缀）才能高效执行。
  • 后缀表达式：无需考虑括号和优先级，计算效率高，适合计算机处理，常用于栈实现的计算器或编译器中。
  • 前缀表达式：同样不需要括号和优先级，且从右到左扫描，更适合某些特定的递归计算场景。

在后缀表达式（Postfix）转换中，优先级的处理主要是通过栈来控制操作符的顺序。转换过程遵循如下的步骤：

  1. 遇到操作数（数字或变量）：
    直接将其添加到后缀表达式中。

  2. 遇到操作符（如 +, -, *, / 等）：
    弹出栈中所有优先级大于或等于当前操作符的操作符，并将它们添加到后缀表达式中。
    将当前操作符压入栈中。

  3. 遇到左括号 (：
    将其直接压入栈中，表示后续操作符需在括号内进行计算。

  4. 遇到右括号 )：
    弹出栈中操作符并加入后缀表达式，直到遇到左括号 (，将其弹出栈，但不加入后缀表达式。

  5. 栈中剩余操作符：
    当输入完全读取完毕后，将栈中剩余的操作符全部弹出并添加到后缀表达式。

通过这三种不同的表达式格式，可以在不同的计算机程序中实现灵活的运算处理，而这些格式的转换和计算通常依赖于栈的数据结构。