每日算法 — 使用java实现后缀表达式：中缀转后缀与栈求值算法

可莉爸爸 AI算法

引言

后缀表达式（Reverse Polish Notation，RPN），又称逆波兰表示法，是一种将运算符置于操作数之后的表达式记法。与日常熟悉的中缀表达式（如 3 + 4 * 2）相比，后缀表达式无需括号即可明确运算顺序，天然适合计算机的栈结构处理。本文将用 Java 完整实现中缀表达式转后缀表达式以及后缀表达式求值两大核心算法。

核心原理

中缀与后缀的区别

表达式类型 示例 特点
中缀表达式 3 + 4 * 2 / (1 - 5) 运算符在操作数中间，需括号明确优先级
后缀表达式 3 4 2 * 1 5 - / + 运算符在操作数之后，无括号，顺序唯一

调度场算法（Shunting Yard Algorithm）

Edsger Dijkstra 于 1961 年提出的调度场算法，是使用栈将中缀表达式转换为后缀表达式的经典方法。核心思想：

  1. 遇到操作数，直接输出到结果
  2. 遇到运算符，与栈顶运算符比较优先级，弹出所有优先级更高或相等的运算符，再将当前运算符入栈
  3. 遇到左括号，直接入栈
  4. 遇到右括号，弹出栈中元素直到遇到左括号
  5. 表达式结束后，弹出栈中所有剩余运算符

后缀表达式求值

使用后缀表达式求值极为简洁：
1. 从左到右扫描表达式
2. 遇到操作数，压入栈
3. 遇到运算符，弹出栈顶两个操作数进行运算，结果压回栈
4. 最终栈中唯一元素即为结果

完整实现

import java.util.*;

/**
 * 表达式处理工具类：支持中缀转后缀与后缀求值
 */
public class ExpressionEvaluator {

    /**
     * 运算符优先级定义
     */
    private static int precedence(char op) {
        switch (op) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
            case '%':
                return 2;
            case '^':
                return 3; // 幂运算，右结合
            default:
                return 0;
        }
    }

    /**
     * 判断运算符是否为右结合
     */
    private static boolean isRightAssociative(char op) {
        return op == '^';
    }

    /**
     * 判断字符是否为运算符
     */
    private static boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/' || c == '%' || c == '^';
    }

    /**
     * 执行二元运算
     */
    private static double applyOp(double a, double b, char op) {
        switch (op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            case '/':
                if (b == 0) throw new ArithmeticException("Division by zero");
                return a / b;
            case '%': return a % b;
            case '^': return Math.pow(a, b);
            default:
                throw new IllegalArgumentException("Unsupported operator: " + op);
        }
    }

    /**
     * 中缀表达式转后缀表达式（调度场算法）
     * @param infix 中缀表达式字符串，支持 + - * / % ^ 和括号
     * @return 后缀表达式（以空格分隔的Token列表）
     */
    public static String infixToPostfix(String infix) {
        StringBuilder output = new StringBuilder();
        Deque<Character> operatorStack = new ArrayDeque<>();

        int i = 0;
        while (i < infix.length()) {
            char c = infix.charAt(i);

            // 跳过空白字符
            if (Character.isWhitespace(c)) {
                i++;
                continue;
            }

            // 处理数字（包括小数）
            if (Character.isDigit(c) || c == '.') {
                StringBuilder num = new StringBuilder();
                while (i < infix.length() && 
                       (Character.isDigit(infix.charAt(i)) || infix.charAt(i) == '.')) {
                    num.append(infix.charAt(i));
                    i++;
                }
                output.append(num).append(' ');
                continue;
            }

            // 处理左括号
            if (c == '(') {
                operatorStack.push(c);
            }
            // 处理右括号
            else if (c == ')') {
                while (!operatorStack.isEmpty() && operatorStack.peek() != '(') {
                    output.append(operatorStack.pop()).append(' ');
                }
                if (operatorStack.isEmpty()) {
                    throw new IllegalArgumentException("Mismatched parentheses");
                }
                operatorStack.pop(); // 弹出左括号
            }
            // 处理运算符
            else if (isOperator(c)) {
                while (!operatorStack.isEmpty() && operatorStack.peek() != '(') {
                    char topOp = operatorStack.peek();
                    int topPrec = precedence(topOp);
                    int currPrec = precedence(c);

                    // 弹出优先级更高或相等（左结合）的运算符
                    if (topPrec > currPrec || 
                        (topPrec == currPrec && !isRightAssociative(c))) {
                        output.append(operatorStack.pop()).append(' ');
                    } else {
                        break;
                    }
                }
                operatorStack.push(c);
            }
            else {
                throw new IllegalArgumentException("Invalid character: " + c);
            }
            i++;
        }

        // 弹出栈中剩余运算符
        while (!operatorStack.isEmpty()) {
            char op = operatorStack.pop();
            if (op == '(' || op == ')') {
                throw new IllegalArgumentException("Mismatched parentheses");
            }
            output.append(op).append(' ');
        }

        return output.toString().trim();
    }

    /**
     * 后缀表达式求值
     * @param postfix 以空格分隔的后缀表达式
     * @return 计算结果
     */
    public static double evaluatePostfix(String postfix) {
        Deque<Double> stack = new ArrayDeque<>();
        String[] tokens = postfix.split("\\s+");

        for (String token : tokens) {
            if (token.isEmpty()) continue;

            char c = token.charAt(0);
            // 是操作数
            if (token.length() > 1 || Character.isDigit(c)) {
                stack.push(Double.parseDouble(token));
            }
            // 是运算符
            else if (isOperator(c)) {
                if (stack.size() < 2) {
                    throw new IllegalArgumentException("Invalid postfix expression");
                }
                double b = stack.pop(); // 先弹出的是右操作数
                double a = stack.pop();
                stack.push(applyOp(a, b, c));
            }
            else {
                throw new IllegalArgumentException("Invalid token: " + token);
            }
        }

        if (stack.size() != 1) {
            throw new IllegalArgumentException("Invalid postfix expression");
        }
        return stack.pop();
    }

    /**
     * 直接计算中缀表达式的值
     */
    public static double evaluateInfix(String infix) {
        String postfix = infixToPostfix(infix);
        return evaluatePostfix(postfix);
    }
}

支持负数的增强版本

上述基础实现未处理一元负号。以下是支持负数表达式的增强版：

/**
 * 增强版表达式求值：支持一元负号
 */
public class AdvancedExpressionEvaluator {

    private static int precedence(char op) {
        switch (op) {
            case 'u': return 4; // 一元负号，最高优先级
            case '^': return 3;
            case '*':
            case '/':
            case '%': return 2;
            case '+':
            case '-': return 1;
            default: return 0;
        }
    }

    private static boolean isRightAssociative(char op) {
        return op == '^' || op == 'u';
    }

    private static boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/' || c == '%' || c == '^';
    }

    /**
     * 中缀转后缀（支持一元负号）
     */
    public static String infixToPostfix(String infix) {
        StringBuilder output = new StringBuilder();
        Deque<Character> stack = new ArrayDeque<>();

        int i = 0;
        while (i < infix.length()) {
            char c = infix.charAt(i);

            if (Character.isWhitespace(c)) {
                i++;
                continue;
            }

            // 数字（含小数）
            if (Character.isDigit(c) || c == '.') {
                StringBuilder num = new StringBuilder();
                while (i < infix.length() && 
                       (Character.isDigit(infix.charAt(i)) || infix.charAt(i) == '.')) {
                    num.append(infix.charAt(i));
                    i++;
                }
                output.append(num).append(' ');
                continue;
            }

            // 判断一元负号：在开头、左括号后、或另一个运算符后
            if (c == '-') {
                boolean isUnary = (i == 0);
                if (i > 0) {
                    char prev = infix.charAt(i - 1);
                    while (Character.isWhitespace(prev) && i > 1) {
                        prev = infix.charAt(--i - 1 + 1);
                    }
                    // 简化判断：如果前一个非空白字符是运算符或左括号，则当前为 unary
                }
                // 实际检测
                int j = i - 1;
                while (j >= 0 && Character.isWhitespace(infix.charAt(j))) j--;
                isUnary = (j < 0) || (infix.charAt(j) == '(') || isOperator(infix.charAt(j));

                if (isUnary) {
                    c = 'u'; // 用 'u' 表示一元负号
                }
            }

            if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    output.append(stack.pop()).append(' ');
                }
                if (stack.isEmpty()) throw new IllegalArgumentException("Mismatched parentheses");
                stack.pop();
            } else if (isOperator(c) || c == 'u') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    char top = stack.peek();
                    int topPrec = precedence(top);
                    int currPrec = precedence(c);
                    if (topPrec > currPrec || (topPrec == currPrec && !isRightAssociative(c))) {
                        output.append(stack.pop()).append(' ');
                    } else {
                        break;
                    }
                }
                stack.push(c);
            } else {
                throw new IllegalArgumentException("Invalid character: " + c);
            }
            i++;
        }

        while (!stack.isEmpty()) {
            char op = stack.pop();
            if (op == '(') throw new IllegalArgumentException("Mismatched parentheses");
            output.append(op).append(' ');
        }

        return output.toString().trim();
    }

    private static double applyOp(double a, double b, char op) {
        switch (op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            case '/':
                if (b == 0) throw new ArithmeticException("Division by zero");
                return a / b;
            case '%': return a % b;
            case '^': return Math.pow(a, b);
            default: throw new IllegalArgumentException("Unknown operator: " + op);
        }
    }

    public static double evaluatePostfix(String postfix) {
        Deque<Double> stack = new ArrayDeque<>();
        for (String token : postfix.split("\\s+")) {
            if (token.isEmpty()) continue;
            if (token.equals("u")) {
                stack.push(-stack.pop());
            } else if (token.length() == 1 && isOperator(token.charAt(0))) {
                double b = stack.pop();
                double a = stack.pop();
                stack.push(applyOp(a, b, token.charAt(0)));
            } else {
                stack.push(Double.parseDouble(token));
            }
        }
        return stack.pop();
    }
}

测试用例

public class ExpressionTest {
    public static void main(String[] args) {
        String[] testCases = {
            "3 + 4 * 2 / (1 - 5)",
            "2 ^ 3 + 5",
            "(1 + 2) * (3 + 4)",
            "10 / 2 + 3 * 4",
            "5 + ((1 + 2) * 4) - 3"
        };

        for (String expr : testCases) {
            String postfix = ExpressionEvaluator.infixToPostfix(expr);
            double result = ExpressionEvaluator.evaluatePostfix(postfix);
            System.out.printf("中缀: %-30s -> 后缀: %-25s = %.4f%n", expr, postfix, result);
        }
    }
}

预期输出：

中缀: 3 + 4 * 2 / (1 - 5)        -> 后缀: 3 4 2 * 1 5 - / +      = 1.0000
中缀: 2 ^ 3 + 5                   -> 后缀: 2 3 ^ 5 +             = 13.0000
中缀: (1 + 2) * (3 + 4)           -> 后缀: 1 2 + 3 4 + *         = 21.0000
中缀: 10 / 2 + 3 * 4              -> 后缀: 10 2 / 3 4 * +        = 17.0000
中缀: 5 + ((1 + 2) * 4) - 3       -> 后缀: 5 1 2 + 4 * + 3 -    = 14.0000

复杂度分析

操作 时间复杂度 空间复杂度
中缀转后缀 $O(n)$ $O(n)$
后缀求值 $O(n)$ $O(n)$

其中 $n$ 为表达式长度。两种操作均为线性时间，栈的深度最坏情况下为 $O(n)$（如连续遇到优先级递减的运算符）。

应用场景

  • 编译器前端：表达式解析是编译器语法分析的核心步骤
  • 计算器实现：后缀表达式求值逻辑简洁，无需递归
  • 电子表格软件：如 Excel 的公式计算引擎
  • 逆波兰计算器（RPN Calculator）：HP 计算器的经典设计

总结

后缀表达式是理解栈数据结构应用的绝佳案例。通过 Dijkstra 的调度场算法，我们能够优雅地处理中缀表达式的优先级和括号嵌套；而后缀求值则展示了栈”后进先出”特性的威力。掌握这一算法，是深入理解编译原理和表达式解析的基础。

Tagged with: