Java计算器核心算法代码实现

请听我详细讲解“Java计算器核心算法代码实现”的完整攻略。

概述

在实现一个Java计算器时，核心的算法是计算表达式的值。本攻略将详细介绍如何使用栈和逆波兰表达式来实现计算器的核心算法。

栈的使用

栈是一种后进先出（LIFO）的数据结构。因为计算器中涉及到的算法通常都需要借助栈来实现。我们通过栈来计算表达式的值。

在Java中，Stack类是一个非常基础的数据结构，提供了压栈、弹栈等基本操作。我们可以通过它来实现栈的相关操作。

Stack<Integer> stack = new Stack<>();
stack.push(1); // 入栈
stack.push(2);
int top = stack.pop(); // 出栈

逆波兰表达式

逆波兰表达式是一种将运算符置于操作数之后的表达式。例如，将中缀表达式“1 + 2”转换为逆波兰表达式就是“1 2 +”。逆波兰表达式可以通过栈来实现计算表达式的值。

具体实现过程如下：

1. 遇到数字，直接输出；
2. 遇到运算符，首先判断栈是否为空。若为空，将该运算符入栈；若不为空，则将栈中比该运算符优先级高或相等的运算符输出，并将该运算符入栈；
3. 遇到左括号，将其入栈；
4. 遇到右括号，将栈中左括号上面的运算符输出，直到遇到左括号为止，并将左括号出栈。

将中缀表达式转换为逆波兰表达式的代码示例：

public static String infix2RPN(String infix) {
    StringBuilder sb = new StringBuilder();
    Stack<Character> stack = new Stack<>();

    for (char ch : infix.toCharArray()) {
        if (Character.isDigit(ch)) {
            sb.append(ch);
        } else {
            while (!stack.isEmpty() && priority(stack.peek()) >= priority(ch)) {
                sb.append(stack.pop());
            }
            stack.push(ch);
        }
    }

    while (!stack.isEmpty()) {
        sb.append(stack.pop());
    }

    return sb.toString();
}

// 判断运算符的优先级
static int priority(char ch) {
    if (ch == '+' || ch == '-') {
        return 1;
    } else if (ch == '*' || ch == '/') {
        return 2;
    } else {
        return 0;
    }
}

将逆波兰表达式计算的代码示例：

public static int evalRPN(String rpn) {
    Stack<Integer> stack = new Stack<>();

    for (char ch : rpn.toCharArray()) {
        if (Character.isDigit(ch)) {
            stack.push(ch - '0');
        } else {
            int b = stack.pop();
            int a = stack.pop();
            int res = 0;
            if (ch == '+') {
                res = a + b;
            } else if (ch == '-') {
                res = a - b;
            } else if (ch == '*') {
                res = a * b;
            } else if (ch == '/') {
                res = a / b;
            }
            stack.push(res);
        }
    }

    return stack.pop();
}

示例说明

下面通过两个示例来说明如何通过逆波兰表达式的方式来计算表达式的值。

示例一

假设有一个中缀表达式为“1 + 2 * (3 + 4) - 5”，我们可以按照如下方式来计算表达式的值：

1. 将中缀表达式转换为逆波兰表达式："1 2 3 4 + * + 5 -"
2. 计算逆波兰表达式的值，即为该表达式的结果。

String infix = "1 + 2 * (3 + 4) - 5";
String rpn = infix2RPN(infix);
int res = evalRPN(rpn);
// res = 8

示例二

假设有一个中缀表达式为“2 + 3 * 4”，我们可以按照如下方式来计算表达式的值：

1. 将中缀表达式转换为逆波兰表达式："2 3 4 * +"
2. 计算逆波兰表达式的值，即为该表达式的结果。

String infix = "2 + 3 * 4";
String rpn = infix2RPN(infix);
int res = evalRPN(rpn);
// res = 14

总结

通过栈和逆波兰表达式，我们可以很轻松地实现计算器的核心算法。使用逆波兰表达式可以避免使用括号和优先级带来的问题。同时，使用栈可以使得我们的代码更加简洁明了。