前缀表达式（波兰表示法）

前缀表达式是一种将运算符置于操作数之前的表达式表示方式，也称为波兰表示法。例如，中缀表达式 3 + 4 对应的前缀形式为 + 3 4。在计算时，采用栈结构从右至左扫描表达式：遇到操作数则入栈；遇到运算符则弹出栈顶两个元素进行计算，并将结果重新压入栈中。

中缀表达式

中缀表达式是人类习惯的数学表达形式，如 1 + ( ( 2 + 3 ) * 4 ) - 5。虽然直观易读，但由于需处理括号和运算符优先级，对计算机直接求值较为复杂，通常需要先转换为更易处理的形式。

后缀表达式（逆波兰表示法）

后缀表达式将运算符置于操作数之后，例如 3 4 + 表示 3 + 4。这种形式无需括号即可明确运算顺序，非常适合使用栈来求值。从左到右遍历表达式，操作数入栈，遇到运算符时弹出两个操作数执行运算并将结果压回栈中。

基于栈的后缀表达式求值实现

以下是一个完整的 Java 实现，用于解析并计算后缀表达式：

import java.util.*;

public class ReversePolishCalculator {
    public static void main(String[] args) {
        String expression = "3 4 + 5 * 6 -";
        List<String> tokens = tokenize(expression);
        int result = evaluate(tokens);
        System.out.println("计算结果：" + result); // 输出：29
    }

    // 将表达式字符串拆分为标记列表
    public static List<String> tokenize(String exp) {
        return new ArrayList<>(Arrays.asList(exp.split("\\s+")));
    }

    // 计算后缀表达式的值
    public static int evaluate(List<String> tokens) {
        Stack<Integer> operandStack = new Stack<>();
        for (String token : tokens) {
            if (isNumeric(token)) {
                operandStack.push(Integer.parseInt(token));
            } else {
                int b = operandStack.pop();
                int a = operandStack.pop();
                int computed = performOperation(a, b, token);
                operandStack.push(computed);
            }
        }
        return operandStack.pop();
    }

    // 判断字符串是否为数字
    private static boolean isNumeric(String str) {
        return str.matches("\\d+");
    }

    // 执行指定的运算
    private static int performOperation(int a, int b, String op) {
        return switch (op) {
            case "+" -> a + b;
            case "-" -> a - b;
            case "*" -> a * b;
            case "/" -> a / b;
            default -> throw new IllegalArgumentException("不支持的运算符: " + op);
        };
    }
}

中缀表达式转后缀表达式

将中缀表达式转换为后缀表达式可通过"调度场算法"（Shunting Yard Algorithm）实现，核心思想如下：

• 准备一个操作数/操作符输出队列 output 和一个运算符栈 operatorStack。
• 从左到右扫描中缀表达式的每个元素：
• 若为数字，直接加入输出队列。
• 若为左括号 (，压入栈中。
• 若为右括号 )，持续弹出栈顶元素加入输出队列，直到遇到左括号为止（左右括号配对丢弃）。
• 若为运算符，则比较其与栈顶运算符的优先级：只要栈顶运算符优先级 ≥ 当前运算符，就将其弹出并加入输出队列；最后将当前运算符压入栈。
• 遍历结束后，将栈中剩余的所有运算符依次弹出并加入输出队列。

转换过程代码实现

// 中缀转后缀主方法
public static List<String> infixToPostfix(List<String> infixTokens) {
    List<String> output = new ArrayList<>();
    Stack<String> operators = new Stack<>();

    for (String token : infixTokens) {
        if (token.matches("\\d+")) {
            output.add(token);
        } else if (token.equals("(")) {
            operators.push(token);
        } else if (token.equals(")")) {
            while (!operators.peek().equals("(")) {
                output.add(operators.pop());
            }
            operators.pop(); // 移除 '('
        } else if (isOperator(token)) {
            while (!operators.isEmpty() && 
                   !operators.peek().equals("(") &&
                   precedence(operators.peek()) >= precedence(token)) {
                output.add(operators.pop());
            }
            operators.push(token);
        }
    }

    while (!operators.isEmpty()) {
        output.add(operators.pop());
    }

    return output;
}

// 获取运算符优先级
private static int precedence(String op) {
    return switch (op) {
        case "+", "-" -> 1;
        case "*", "/" -> 2;
        default -> 0;
    };
}

// 判断是否为运算符
private static boolean isOperator(String s) {
    return Set.of("+", "-", "*", "/").contains(s);
}

// 解析中缀字符串为标记列表
public static List<String> parseInfixExpression(String exp) {
    List<String> list = new ArrayList<>();
    int i = 0;
    while (i < exp.length()) {
        char c = exp.charAt(i);
        if (!Character.isDigit(c)) {
            list.add(String.valueOf(c));
            i++;
        } else {
            StringBuilder num = new StringBuilder();
            while (i < exp.length() && Character.isDigit(exp.charAt(i))) {
                num.append(exp.charAt(i++));
            }
            list.add(num.toString());
        }
    }
    return list;
}

通过上述方法，可将任意合法中缀表达式（如 1+((2+3)*4)-5）成功转换为对应的后缀表达式，并进一步利用栈完成高效求值。