逆波兰表达式

逆波兰表达式（Reverse Polish Notation, RPN）

逆波兰表达式是一种数学表达式的表示方法，其特点是运算符位于操作数之后，无需使用括号来指定运算顺序，因此也被称为 “后缀表达式”。它在计算机科学中被广泛应用于表达式求值、编译器设计等领域。

基本概念

与传统表达式的对比

中缀表达式（日常使用）：运算符位于操作数中间，如 3 + 4 × 2 ÷ (1 - 5)。缺点：需要括号和运算符优先级（先乘除后加减）来确定运算顺序，计算机解析复杂。
逆波兰表达式（后缀表达式）：运算符位于操作数之后，如 3 4 2 × 1 5 - ÷ +。优点：无需括号，仅通过顺序扫描即可确定运算顺序，计算机解析高效。

核心原理

逆波兰表达式的求值过程可通过栈（Stack）数据结构实现，步骤如下：

从左到右扫描表达式的每个元素（操作数或运算符）。
若遇到操作数，将其压入栈中。
若遇到运算符，从栈中弹出两个操作数（注意顺序：后弹出的是第一个操作数），使用该运算符计算结果，再将结果压回栈中。
扫描结束后，栈中仅剩的元素即为表达式的结果。

示例解析

例 1：计算 `3 + 4`

逆波兰表达式：
1
3 4 +
求值步骤：
1. 扫描到 3，压栈 → 栈：[3]
2. 扫描到 4，压栈 → 栈：[3, 4]
3. 扫描到 +，弹出 4 和 3，计算 3 + 4 = 7，压栈 → 栈：[7]
4. 结果：7

例 2：计算 `(3 + 4) × 5`

逆波兰表达式：
1
3 4 + 5 ×
求值步骤：
1. 压入 3 → [3]
2. 压入 4 → [3, 4]
3. 遇到 +，计算 3+4=7 → [7]
4. 压入 5 → [7, 5]
5. 遇到 ×，计算 7×5=35 → [35]
6. 结果：35

Java 实现逆波兰表达式求值

以下是使用栈实现逆波兰表达式求值的核心代码：

import java.util.Stack;

public class RPNCalculator {
    public static int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        
        for (String token : tokens) {
            // 判断是否为运算符
            if (token.equals("+") || token.equals("-") || 
                token.equals("*") || token.equals("/")) {
                // 弹出两个操作数（注意顺序：后弹出的是左操作数）
                int b = stack.pop();
                int a = stack.pop();
                int result = 0;
                
                switch (token) {
                    case "+":
                        result = a + b;
                        break;
                    case "-":
                        result = a - b;
                        break;
                    case "*":
                        result = a * b;
                        break;
                    case "/":
                        // 题目通常保证除法为整数除法，且除数不为0
                        result = a / b;
                        break;
                }
                stack.push(result);
            } else {
                // 操作数直接压栈
                stack.push(Integer.parseInt(token));
            }
        }
        // 栈中最后剩余的元素即为结果
        return stack.pop();
    }

    public static void main(String[] args) {
        // 示例：计算 (3 + 4) × 5 - 6 → 逆波兰表达式：3 4 + 5 * 6 -
        String[] tokens = {"3", "4", "+", "5", "*", "6", "-"};
        System.out.println(evalRPN(tokens)); // 输出：29
    }
}

中缀表达式转逆波兰表达式

若需要将日常使用的中缀表达式转换为逆波兰表达式，步骤如下：

初始化一个运算符栈和一个结果列表。
扫描中缀表达式的每个元素：
- 若为操作数，直接加入结果列表。
- 若为左括号 (，压入运算符栈。
- 若为右括号 )，弹出栈顶运算符至结果列表，直到遇到左括号（左括号不加入结果）。
- 若为运算符，弹出栈中优先级高于或等于当前运算符的运算符至结果列表，再将当前运算符压栈。
扫描结束后，将栈中剩余运算符全部弹出至结果列表。

示例：中缀转逆波兰

中缀表达式：3 + 4 × 2 ÷ (1 - 5)
逆波兰表达式：3 4 2 × 1 5 - ÷ +

应用场景

计算器实现：高效解析表达式，避免复杂的括号和优先级判断。
编译器 / 解释器：在代码编译阶段将源代码中的表达式转换为逆波兰表达式，便于机器执行。
栈数据结构实践：逆波兰表达式的求值过程是栈的经典应用案例。

逆波兰表达式的核心优势在于消除了括号依赖，通过栈即可线性扫描求值，时间复杂度为 (O(n))（n 为表达式长度），是计算机处理数学表达式的高效方式。