Java四则运算器实现教程详解

本教程旨在指导开发者使用Java实现一个简单的四则运算器，支持加减乘除和括号运算。核心思想是将常见的中缀表达式转化为后缀表达式（逆波兰表达式），再进行求值。首先，通过词法分析将输入的表达式字符串拆解为词元，例如数字、运算符和括号。然后，利用经典的调度场算法，根据操作符的优先级和括号，将中缀表达式转换成后缀表达式。最后，借助栈数据结构，对后缀表达式进行求值，遇到数字则入栈，遇到操作符则弹出栈顶的两个数字进行计算，并将结果压入栈中。该方法有效解决了表达式计算中操作符优先级和括号嵌套的问题，使得运算逻辑清晰高效。掌握此方法，能够构建出功能完善且易于维护的Java计算器。

要实现一个支持四则运算和括号的Java计算器，核心步骤是先将中缀表达式转换为后缀表达式（逆波兰表达式），再对后缀表达式求值。1. 首先进行词法分析，将输入字符串拆分为有意义的词元，如数字、运算符和括号；2. 使用调度场算法（Shunting-yard algorithm）将中缀表达式转为后缀表达式，利用栈处理操作符优先级和括号，确保运算顺序正确；3. 利用栈对后缀表达式求值，遇到数字入栈，遇到操作符则弹出两个数计算后将结果压入栈，最终栈中唯一元素即为结果。该方法有效解决了操作符优先级、结合性和括号嵌套带来的复杂性，使表达式求值逻辑清晰高效。

用Java实现一个四则运算器，核心思路通常是分两步走：先把我们日常书写的算术表达式（中缀表达式）转换成一种计算机更容易处理的形式，比如逆波兰表达式（后缀表达式），然后再对这种后缀表达式进行求值。这听起来有点绕，但一旦你理解了其中的逻辑，会发现它其实非常优雅且高效。

解决方案

要构建一个能够处理加减乘除以及括号的Java计算器，我们通常会采用“调度场算法”（Shunting-yard algorithm）来完成中缀到后缀的转换，然后用一个简单的栈来评估后缀表达式。

1. 表达式的解析与词法分析 (Tokenization) 首先，我们需要把输入的字符串表达式拆分成一个个有意义的“词元”（tokens），比如数字、运算符、括号。这就像把一句话拆成一个个单词。

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Calculator {

    // 定义操作符优先级
    private static final Map PRECEDENCE = new HashMap<>();
    static {
        PRECEDENCE.put('+', 1);
        PRECEDENCE.put('-', 1);
        PRECEDENCE.put('*', 2);
        PRECEDENCE.put('/', 2);
    }

    // 检查是否是操作符
    private static boolean isOperator(char c) {
        return PRECEDENCE.containsKey(c);
    }

    // 获取操作符优先级
    private static int getPrecedence(char op) {
        return PRECEDENCE.getOrDefault(op, 0);
    }

    // 词法分析：将表达式字符串拆分为词元列表
    public List tokenize(String expression) {
        List tokens = new ArrayList<>();
        Pattern pattern = Pattern.compile("(\\d+\\.?\\d*)|([+\\-*/()])"); // 匹配数字或运算符/括号
        Matcher matcher = pattern.matcher(expression.replaceAll("\\s+", "")); // 移除空格

        while (matcher.find()) {
            tokens.add(matcher.group());
        }
        return tokens;
    }

    // ... 后续方法
}

2. 中缀表达式转后缀表达式 (Shunting-yard Algorithm) 这是最关键的一步。我们用两个数据结构：一个栈（用于存放操作符和括号）和一个列表（用于存放转换后的后缀表达式）。

// ... 接上 Calculator 类

    // 中缀表达式转后缀表达式
    public List infixToPostfix(List tokens) {
        List postfix = new ArrayList<>();
        Stack operatorStack = new Stack<>();

        for (String token : tokens) {
            char c = token.charAt(0); // 简化处理，假设token都是单字符或完整数字

            if (Character.isDigit(c)) { // 如果是数字，直接输出
                postfix.add(token);
            } else if (c == '(') { // 左括号入栈
                operatorStack.push(c);
            } else if (c == ')') { // 右括号，弹出栈中操作符直到遇到左括号
                while (!operatorStack.isEmpty() && operatorStack.peek() != '(') {
                    postfix.add(String.valueOf(operatorStack.pop()));
                }
                if (!operatorStack.isEmpty() && operatorStack.peek() == '(') {
                    operatorStack.pop(); // 弹出左括号
                } else {
                    throw new IllegalArgumentException("Mismatched parentheses");
                }
            } else if (isOperator(c)) { // 操作符
                // 弹出栈中优先级更高或相等的运算符
                while (!operatorStack.isEmpty() && isOperator(operatorStack.peek()) &&
                       getPrecedence(c) <= getPrecedence(operatorStack.peek())) {
                    postfix.add(String.valueOf(operatorStack.pop()));
                }
                operatorStack.push(c); // 当前操作符入栈
            } else {
                throw new IllegalArgumentException("Invalid token: " + token);
            }
        }

        // 弹出栈中剩余所有操作符
        while (!operatorStack.isEmpty()) {
            if (operatorStack.peek() == '(') {
                throw new IllegalArgumentException("Mismatched parentheses");
            }
            postfix.add(String.valueOf(operatorStack.pop()));
        }
        return postfix;
    }

    // ... 后续方法

3. 后缀表达式求值 后缀表达式的求值相对简单，只需要一个栈。遇到数字就入栈，遇到操作符就弹出栈顶的两个数字进行运算，然后将结果再压入栈。

// ... 接上 Calculator 类

    // 后缀表达式求值
    public double evaluatePostfix(List postfixTokens) {
        Stack operandStack = new Stack<>();

        for (String token : postfixTokens) {
            if (Character.isDigit(token.charAt(0)) || (token.length() > 1 && token.charAt(0) == '-' && Character.isDigit(token.charAt(1)))) {
                // 处理负数情况，或者更严谨地判断是否是数字
                operandStack.push(Double.parseDouble(token));
            } else if (isOperator(token.charAt(0))) {
                if (operandStack.size() < 2) {
                    throw new IllegalArgumentException("Invalid expression: not enough operands for operator " + token);
                }
                double val2 = operandStack.pop();
                double val1 = operandStack.pop();
                double result;
                switch (token.charAt(0)) {
                    case '+': result = val1 + val2; break;
                    case '-': result = val1 - val2; break;
                    case '*': result = val1 * val2; break;
                    case '/':
                        if (val2 == 0) throw new ArithmeticException("Division by zero");
                        result = val1 / val2; break;
                    default: throw new IllegalArgumentException("Unknown operator: " + token);
                }
                operandStack.push(result);
            } else {
                throw new IllegalArgumentException("Invalid token in postfix expression: " + token);
            }
        }

        if (operandStack.size() != 1) {
            throw new IllegalArgumentException("Invalid expression: too many operands or operators left");
        }
        return operandStack.pop();
    }

    public static void main(String[] args) {
        Calculator calculator = new Calculator();
        String expression = "3 + 4 * (2 - 1) / 2"; // 示例表达式
        // String expression = " ( 1 + 2 ) * 3 ";

        try {
            List tokens = calculator.tokenize(expression);
            System.out.println("Tokens: " + tokens);

            List postfix = calculator.infixToPostfix(tokens);
            System.out.println("Postfix: " + postfix);

            double result = calculator.evaluatePostfix(postfix);
            System.out.println("Result: " + result); // 期望结果：3 + 4 * 1 / 2 = 3 + 2 = 5.0
        } catch (Exception e) {
            System.err.println("Error: " + e.getMessage());
        }
    }
}

为什么直接计算表达式会遇到困难？

你可能会发现，直接从左到右扫描一个像 3 + 4 * 2 这样的表达式，然后就地计算，结果往往是不对的。因为我们人脑在处理这种表达式时，会自动地遵守一个规则——“先乘除后加减”，也就是操作符的优先级。计算机可没这“常识”，它只会老老实实地按照你给它的指令来。

比方说，直接从左到右算 3 + 4 * 2：

1. 3 + 4 得到 7
2. 7 * 2 得到 14 这显然是错的，正确答案应该是 3 + (4 * 2) = 3 + 8 = 11。

另外，括号的存在又会进一步打乱这种简单的顺序。(3 + 4) * 2 意味着括号里的内容要优先计算。这种“优先级”和“结合性”（比如加法是从左到右结合，a - b - c 等同于 (a - b) - c）让中缀表达式对计算机来说变得异常复杂。它需要不断地“回溯”或者“预读”，来决定哪个操作先执行。这就是为什么我们需要一种更“扁平化”的表示形式，来消除这些歧义。

如何处理操作符优先级和括号？

处理操作符优先级和括号，正是“调度场算法”的精髓所在。这个算法是由Edsger Dijkstra提出的，它就像一个火车站的调度场，把“货车”（数字）直接送往目的地，而把“机车”（操作符）暂时停在不同的轨道上，根据它们的“型号”（优先级）和“方向”（结合性）来决定什么时候出发。

具体来说，当算法扫描中缀表达式时：

• 遇到数字： 简单，直接把它添加到输出列表（也就是后缀表达式）中。
• 遇到左括号 (： 把它压入操作符栈。它就像一个“高优先级”的信号，告诉我们括号里面的内容要先处理。
• 遇到右括号 )： 这就有点意思了。我们需要不断地从操作符栈中弹出操作符，并将它们添加到输出列表，直到遇到对应的左括号。找到左括号后，把这对括号都丢弃掉，因为它们在后缀表达式中已经没有存在的必要了。如果没找到左括号就遇到了栈底或者其他操作符，那说明括号不匹配，表达式就是非法的。
• *遇到操作符（如 +, -, `,/`）：** 这是最复杂的部分。我们需要比较当前操作符与操作符栈顶的操作符的优先级。
  • 如果栈顶的操作符优先级更高或相等（并且是左结合的，像加减乘除都是），那么栈顶的操作符应该先执行，所以把它弹出并添加到输出列表。这个过程会一直重复，直到栈为空，或者栈顶是左括号，或者栈顶的操作符优先级低于当前操作符。
  • 处理完之后，把当前操作符压入栈。

通过这种巧妙的规则，算法就能自动地将中缀表达式的优先级和括号信息“编码”到后缀表达式的顺序中，从而消除了计算时的歧义。

逆波兰表达式（RPN）的优势是什么，又如何进行求值？

逆波兰表达式，或者叫后缀表达式，它最大的优势在于消除了歧义。你不需要括号，也不用考虑操作符优先级，因为操作的顺序已经由词元的排列顺序明确定义了。这对于计算机来说，简直是福音！

你想想，在后缀表达式里，操作符总是出现在它要操作的数（操作数）之后。比如 3 4 + 意味着 3 和 4 相加，3 4 2 * + 意味着 3 加上 4 乘以 2 的结果。这种形式让求值过程变得异常简单，只需要一个栈就能搞定：

1. 遍历后缀表达式的每个词元。
2. 如果词元是数字： 把它压入一个“操作数栈”（operand stack）。
3. 如果词元是操作符： 从操作数栈中弹出最上面的两个数字（注意顺序，通常是先弹出的是第二个操作数，后弹出的是第一个操作数），执行这个操作符对应的运算，然后把运算结果再压回操作数栈。
4. 遍历结束后： 操作数栈中应该只剩下一个数字，那个就是整个表达式的最终结果。

这种求值方式，直观、高效，而且不容易出错。它完美地解决了中缀表达式带来的优先级和括号问题，让计算器的实现变得清晰而可靠。

到这里，我们也就讲完了《Java四则运算器实现教程详解》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于java,四则运算,栈,表达式,调度场算法的知识点！