每日算法 — 使用java实现表达式求值：调度场算法与双栈中缀求值

引言

表达式求值是编译器、计算器和电子表格软件的核心功能。给定一个中缀表达式如 ( 3 + 5 \times (2 – 8) )，如何正确计算其结果？直接按从左到右的顺序计算会得到错误答案，因为忽略了运算符优先级和括号。Dijkstra提出的调度场算法（Shunting Yard Algorithm）使用双栈结构（操作数栈和运算符栈）巧妙地解决了这一问题。本文将深入讲解该算法原理，并用Java实现一个支持加减乘除、括号和负数的通用表达式求值器。

算法原理

调度场算法的核心思想：

1. 操作数栈：存储待计算的数字
2. 运算符栈：存储待处理的运算符
3. 优先级规则：乘除优先级高于加减，括号改变优先级
4. 遇到运算符时：比较栈顶运算符与新运算符的优先级，如果栈顶优先级更高或相等，则先计算栈顶运算

优先级定义

Java实现

核心求值器

import java.util.Stack;

/**
 * 中缀表达式求值器
 * 支持 +, -, *, /, 括号 和 负数
 */
public class ExpressionEvaluator {

    /**
     * 计算中缀表达式的值
     * @param expression 中缀表达式字符串，如 "3+5*(2-8)"
     * @return 计算结果
     */
    public static double evaluate(String expression) {
        if (expression == null || expression.trim().isEmpty()) {
            throw new IllegalArgumentException("表达式不能为空");
        }

        // 去除所有空格
        expression = expression.replaceAll("\s+", "");

        Stack<Double> operands = new Stack<>();   // 操作数栈
        Stack<Character> operators = new Stack<>(); // 运算符栈

        int i = 0;
        int n = expression.length();

        while (i < n) {
            char ch = expression.charAt(i);

            // 处理数字（包括小数）
            if (Character.isDigit(ch) || ch == '.') {
                StringBuilder numStr = new StringBuilder();
                while (i < n && (Character.isDigit(expression.charAt(i)) || expression.charAt(i) == '.')) {
                    numStr.append(expression.charAt(i));
                    i++;
                }
                operands.push(Double.parseDouble(numStr.toString()));
                continue;  // i已经在内层循环中递增
            }

            // 处理负号：判断是减号运算符还是负数符号
            if (ch == '-') {
                // 负号的条件：在开头，或在 '(' 后，或在另一个运算符后
                if (i == 0 || expression.charAt(i - 1) == '(' || isOperator(expression.charAt(i - 1))) {
                    // 这是一个负号，属于数字的一部分
                    StringBuilder numStr = new StringBuilder("-");
                    i++;
                    while (i < n && (Character.isDigit(expression.charAt(i)) || expression.charAt(i) == '.')) {
                        numStr.append(expression.charAt(i));
                        i++;
                    }
                    operands.push(Double.parseDouble(numStr.toString()));
                    continue;
                }
            }

            // 处理左括号：直接入栈
            if (ch == '(') {
                operators.push(ch);
            }
            // 处理右括号：计算到匹配的左括号
            else if (ch == ')') {
                while (!operators.isEmpty() && operators.peek() != '(') {
                    applyTopOperator(operands, operators);
                }
                // 弹出左括号
                if (!operators.isEmpty() && operators.peek() == '(') {
                    operators.pop();
                } else {
                    throw new IllegalArgumentException("括号不匹配");
                }
            }
            // 处理运算符
            else if (isOperator(ch)) {
                // 当栈顶运算符优先级 >= 当前运算符时，先计算栈顶
                while (!operators.isEmpty() && 
                       precedence(operators.peek()) >= precedence(ch)) {
                    applyTopOperator(operands, operators);
                }
                operators.push(ch);
            }

            i++;
        }

        // 处理栈中剩余的运算符
        while (!operators.isEmpty()) {
            if (operators.peek() == '(' || operators.peek() == ')') {
                throw new IllegalArgumentException("括号不匹配");
            }
            applyTopOperator(operands, operators);
        }

        // 最终结果
        if (operands.size() != 1) {
            throw new IllegalArgumentException("表达式格式错误");
        }
        return operands.pop();
    }

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

    /**
     * 获取运算符优先级
     */
    private static int precedence(char op) {
        switch (op) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            case '(':
                return 0;  // 左括号优先级最低
            default:
                return -1;
        }
    }

    /**
     * 应用栈顶运算符进行计算
     */
    private static void applyTopOperator(Stack<Double> operands, Stack<Character> operators) {
        if (operands.size() < 2) {
            throw new IllegalArgumentException("操作数不足");
        }

        double b = operands.pop();  // 右操作数
        double a = operands.pop();  // 左操作数
        char op = operators.pop();

        double result;
        switch (op) {
            case '+':
                result = a + b;
                break;
            case '-':
                result = a - b;
                break;
            case '*':
                result = a * b;
                break;
            case '/':
                if (b == 0) {
                    throw new ArithmeticException("除数不能为零");
                }
                result = a / b;
                break;
            default:
                throw new IllegalArgumentException("未知运算符: " + op);
        }

        operands.push(result);
    }
}

扩展：支持函数调用

import java.util.*;

/**
 * 增强版表达式求值器
 * 支持常用数学函数：sin, cos, sqrt, pow, abs, log
 */
public class AdvancedExpressionEvaluator {

    private static final Set<String> FUNCTIONS = new HashSet<>(
        Arrays.asList("sin", "cos", "sqrt", "pow", "abs", "log")
    );

    public static double evaluate(String expression) {
        expression = expression.replaceAll("\s+", "").toLowerCase();

        Stack<Double> operands = new Stack<>();
        Stack<String> operators = new Stack<>();  // 支持多字符运算符和函数名

        int i = 0, n = expression.length();

        while (i < n) {
            char ch = expression.charAt(i);

            // 处理数字
            if (Character.isDigit(ch) || ch == '.') {
                int j = i;
                while (j < n && (Character.isDigit(expression.charAt(j)) || expression.charAt(j) == '.')) {
                    j++;
                }
                operands.push(Double.parseDouble(expression.substring(i, j)));
                i = j;
                continue;
            }

            // 处理函数名
            if (Character.isLetter(ch)) {
                int j = i;
                while (j < n && Character.isLetter(expression.charAt(j))) {
                    j++;
                }
                String func = expression.substring(i, j);
                if (FUNCTIONS.contains(func)) {
                    operators.push(func);
                } else {
                    throw new IllegalArgumentException("未知函数: " + func);
                }
                i = j;
                continue;
            }

            // 处理逗号（函数参数分隔符）
            if (ch == ',') {
                while (!operators.isEmpty() && !operators.peek().equals("(")) {
                    applyTopOperator(operands, operators);
                }
                i++;
                continue;
            }

            // 处理左括号
            if (ch == '(') {
                operators.push("(");
            }
            // 处理右括号
            else if (ch == ')') {
                while (!operators.isEmpty() && !operators.peek().equals("(")) {
                    applyTopOperator(operands, operators);
                }
                if (!operators.isEmpty() && operators.peek().equals("(")) {
                    operators.pop();  // 弹出左括号
                }
                // 检查右括号前是否有函数
                if (!operators.isEmpty() && FUNCTIONS.contains(operators.peek())) {
                    applyFunction(operands, operators.pop());
                }
            }
            // 处理运算符
            else if (isOperator(ch)) {
                while (!operators.isEmpty() && 
                       precedence(operators.peek()) >= precedence(String.valueOf(ch))) {
                    applyTopOperator(operands, operators);
                }
                operators.push(String.valueOf(ch));
            }

            i++;
        }

        while (!operators.isEmpty()) {
            applyTopOperator(operands, operators);
        }

        return operands.pop();
    }

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

    private static int precedence(String op) {
        if (op.equals("+") || op.equals("-")) return 1;
        if (op.equals("*") || op.equals("/")) return 2;
        return 0;
    }

    private static void applyTopOperator(Stack<Double> operands, Stack<String> operators) {
        double b = operands.pop();
        double a = operands.pop();
        String op = operators.pop();

        switch (op) {
            case "+": operands.push(a + b); break;
            case "-": operands.push(a - b); break;
            case "*": operands.push(a * b); break;
            case "/": operands.push(a / b); break;
        }
    }

    private static void applyFunction(Stack<Double> operands, String func) {
        double arg = operands.pop();
        switch (func) {
            case "sin": operands.push(Math.sin(arg)); break;
            case "cos": operands.push(Math.cos(arg)); break;
            case "sqrt": operands.push(Math.sqrt(arg)); break;
            case "abs": operands.push(Math.abs(arg)); break;
            case "log": operands.push(Math.log(arg)); break;
        }
    }
}

测试与演示

public class ExpressionEvaluatorDemo {
    public static void main(String[] args) {
        System.out.println("=== 基础表达式求值测试 ===\n");

        String[] testExpressions = {
            "3+5*(2-8)",
            "10+2*6",
            "100*(2+12)",
            "100*(2+12)/14",
            "(1+2)*(3+4)",
            "-5+3",
            "3+-2",
            "(2.5+3.5)*4"
        };

        for (String expr : testExpressions) {
            try {
                double result = ExpressionEvaluator.evaluate(expr);
                System.out.printf("%-20s = %.4f%n", expr, result);
            } catch (Exception e) {
                System.out.printf("%-20s 错误: %s%n", expr, e.getMessage());
            }
        }

        System.out.println("\n=== 增强版（含函数）测试 ===\n");
        String[] advancedTests = {
            "sqrt(16)+3*2",
            "abs(-5)+10",
            "sin(0)+cos(0)"
        };

        for (String expr : advancedTests) {
            try {
                double result = AdvancedExpressionEvaluator.evaluate(expr);
                System.out.printf("%-20s = %.4f%n", expr, result);
            } catch (Exception e) {
                System.out.printf("%-20s 错误: %s%n", expr, e.getMessage());
            }
        }
    }
}

复杂度分析

应用场景

1. 计算器软件：Windows计算器、手机计算器的核心引擎
2. 电子表格：Excel公式解析与计算
3. 编译器：编译原理中语法分析阶段的中缀转后缀
4. 数据库：SQL查询中的表达式计算
5. 科学计算：MATLAB、Mathematica的表达式解析

总结

调度场算法通过巧妙地使用双栈结构，将复杂的中缀表达式求值问题转化为可线性处理的流程。本文实现的基础版和增强版求值器展示了算法的扩展性——从基础四则运算到函数调用，核心逻辑始终保持清晰。掌握这一算法是理解编译器前端和表达式引擎的基础。