如何用Java实现的Shunting Yard算法求解字符串格式数学题？

核心思路 #

Shunting Yard算法核心是把中缀表达式（如5 + 2 * 3）转换为后缀表达式（逆波兰表达式），再通过栈对后缀表达式求值。针对你的需求，需先从输入字符串中提取出纯数学表达式（去掉开头的calculate ），再分两步处理：中缀转后缀、后缀求值。

步骤拆解与代码实现 #

1. 定义基础工具与运算符优先级 #

先封装判断字符类型、定义运算符优先级的工具方法：

import java.util.*;

public class ExpressionCalculator {
    // 运算符优先级：*、/ 优先级高于 +、-
    private static final Map<Character, Integer> OPERATOR_PRIORITY = new HashMap<>();
    static {
        OPERATOR_PRIORITY.put('+', 1);
        OPERATOR_PRIORITY.put('-', 1);
        OPERATOR_PRIORITY.put('*', 2);
        OPERATOR_PRIORITY.put('/', 2);
    }

    // 判断是否为运算符
    private static boolean isOperator(char c) {
        return OPERATOR_PRIORITY.containsKey(c);
    }

    // 判断是否为数字（支持多位数）
    private static boolean isDigit(char c) {
        return Character.isDigit(c);
    }
}

2. 中缀表达式转后缀表达式 #

这是Shunting Yard算法的核心逻辑，用栈管理运算符的入栈与出栈：

// 中缀转后缀表达式
private static List<String> infixToPostfix(String infix) {
    List<String> postfix = new ArrayList<>();
    Deque<Character> operatorStack = new ArrayDeque<>();
    StringBuilder numBuilder = new StringBuilder();

    for (char c : infix.toCharArray()) {
        // 跳过表达式中的空格
        if (Character.isWhitespace(c)) {
            continue;
        }

        // 拼接多位数
        if (isDigit(c)) {
            numBuilder.append(c);
        } else if (isOperator(c)) {
            // 将之前拼接的数字加入后缀列表
            if (numBuilder.length() > 0) {
                postfix.add(numBuilder.toString());
                numBuilder.setLength(0);
            }

            // 弹出栈中优先级大于等于当前运算符的元素
            while (!operatorStack.isEmpty() && OPERATOR_PRIORITY.get(operatorStack.peek()) >= OPERATOR_PRIORITY.get(c)) {
                postfix.add(String.valueOf(operatorStack.pop()));
            }
            operatorStack.push(c);
        }
    }

    // 处理最后一个未加入的数字
    if (numBuilder.length() > 0) {
        postfix.add(numBuilder.toString());
    }

    // 弹出栈中剩余的所有运算符
    while (!operatorStack.isEmpty()) {
        postfix.add(String.valueOf(operatorStack.pop()));
    }

    return postfix;
}

3. 后缀表达式求值 #

用栈对后缀表达式进行计算，得到最终结果：

// 计算后缀表达式的值
private static double evaluatePostfix(List<String> postfix) {
    Deque<Double> numStack = new ArrayDeque<>();

    for (String token : postfix) {
        if (isOperator(token.charAt(0)) && token.length() == 1) {
            // 弹出操作数，注意顺序：后弹出的是第一个运算数
            double num2 = numStack.pop();
            double num1 = numStack.pop();
            double result = 0;

            switch (token.charAt(0)) {
                case '+':
                    result = num1 + num2;
                    break;
                case '-':
                    result = num1 - num2;
                    break;
                case '*':
                    result = num1 * num2;
                    break;
                case '/':
                    if (num2 == 0) {
                        throw new ArithmeticException("除数不能为0");
                    }
                    result = num1 / num2;
                    break;
            }
            numStack.push(result);
        } else {
            // 数字转成double入栈
            numStack.push(Double.parseDouble(token));
        }
    }

    // 栈中剩余的唯一元素就是计算结果
    return numStack.pop();
}

4. 主方法处理输入 #

编写主方法，解析以calculate开头的输入字符串并执行计算：

public static void main(String[] args) {
    // 示例输入
    String input = "calculate 10 + 3 * 4 - 6 / 2";
    // 提取纯数学表达式部分
    String expression = input.substring("calculate ".length()).trim();

    try {
        List<String> postfix = infixToPostfix(expression);
        double result = evaluatePostfix(postfix);
        System.out.println("计算结果：" + result);
    } catch (Exception e) {
        System.out.println("表达式格式错误或计算异常：" + e.getMessage());
    }
}

关键说明 #

• 支持多位数的加减乘除运算，自动忽略表达式中的空格
• 处理了除数为0的异常情况
• 运算符优先级遵循常规数学规则：先乘除后加减

内容的提问来源于stack exchange，提问作者Gehan