整体思路总览
一、需求拆解
- 手动实现栈（Stack）：底层用数组存储，提供入栈、出栈、查看栈顶、判空、获取大小基础方法，不使用 Java 自带
java.util.Stack。 - 实现四则运算计算器，分两步核心算法：
- 中缀表达式转后缀表达式（逆波兰表达式）：解决运算符优先级、括号问题
- 后缀表达式求值：借助自定义栈完成数值计算
- 支持：加减乘除
+ - * /、括号()、多位数、运算优先级* / > + -
二、栈设计思路
栈是后进先出 (LIFO)线性结构：
- 底层：动态扩容数组（简化版固定数组，方便理解）
- 指针
top：记录栈顶下标，top=-1代表空栈 - 核心方法：
push()：入栈，top++，存入元素pop()：出栈，取出栈顶元素，top--，栈空抛异常peek()：查看栈顶不弹出isEmpty()：判断栈是否为空size()：返回栈内元素个数
三、中缀转后缀表达式思路（核心规则）
中缀：1+2*(3-4)人看懂；后缀：1 2 3 4 - * +计算机方便栈计算
- 遍历表达式每一个字符：
- 数字：直接拼接到后缀结果字符串（处理多位数，连续数字合并）
- 左括号
(：直接压入运算符栈 - 右括号
)：循环弹出栈顶运算符到后缀，直到遇到左括号，弹出左括号丢弃 - 运算符
+-*/：- 栈不为空 且 栈顶不是左括号 且栈顶运算符优先级 ≥ 当前运算符
- 持续弹出栈顶运算符到后缀，最后把当前运算符入栈
- 遍历结束后，把栈中剩余所有运算符依次弹出追加到后缀末尾
优先级规则：* / = 2，+ - = 1，括号无优先级
四、后缀表达式求值思路（栈计算）
- 创建数值栈，遍历后缀表达式分割后的每一项：
- 数字：转为整数压入数值栈
- 运算符：弹出两个数（注意顺序：先弹右操作数，再弹左操作数）
- 例：
3 4 -，先出 4，再出 3，计算3-4 - 计算结果重新压回栈
- 例：
- 遍历完成，栈中仅剩一个元素，即为最终结果
完整 Java 代码
1. 自定义栈类（支持泛型，运算符、数字都能存）
java
运行
/** * 手动实现栈 LIFO * @param <T> 存储元素类型 */ public class MyStack<T> { // 底层数组存储 private Object[] arr; // 栈顶指针，-1代表空 private int top; // 初始容量 private static final int DEFAULT_CAPACITY = 10; public MyStack() { arr = new Object[DEFAULT_CAPACITY]; top = -1; } // 入栈 public void push(T val) { // 扩容判断 if (top == arr.length - 1) { grow(); } top++; arr[top] = val; } // 出栈，返回栈顶元素 @SuppressWarnings("unchecked") public T pop() { if (isEmpty()) { throw new RuntimeException("栈为空，无法出栈"); } T res = (T) arr[top]; arr[top] = null; // 清空引用 top--; return res; } // 查看栈顶，不弹出 @SuppressWarnings("unchecked") public T peek() { if (isEmpty()) { throw new RuntimeException("栈为空，无栈顶元素"); } return (T) arr[top]; } // 判断栈空 public boolean isEmpty() { return top == -1; } // 获取栈内元素数量 public int size() { return top + 1; } // 数组扩容 2倍 private void grow() { Object[] newArr = new Object[arr.length * 2]; System.arraycopy(arr, 0, newArr, 0, arr.length); arr = newArr; } }2. 计算器工具类（中缀转后缀 + 后缀求值）
java
运行
public class Calculator { public static void main(String[] args) { // 测试用例 String expr1 = "1+2*(3-4)"; String expr2 = "10+20*3/5"; String expr3 = "(100-20)/8+9"; calc(expr1); calc(expr2); calc(expr3); } /** * 统一计算入口 * @param infix 中缀表达式 */ public static void calc(String infix) { System.out.println("======================"); System.out.println("中缀表达式：" + infix); String suffix = infixToSuffix(infix); System.out.println("后缀表达式：" + suffix); int result = calcSuffix(suffix); System.out.println("计算结果：" + result); } // 1. 获取运算符优先级 private static int getPriority(char op) { return switch (op) { case '+', '-' -> 1; case '*', '/' -> 2; default -> 0; // 括号 }; } // 2. 中缀表达式 -> 后缀表达式 private static String infixToSuffix(String infix) { // 运算符栈 MyStack<Character> opStack = new MyStack<>(); // 存储后缀表达式 StringBuilder suffix = new StringBuilder(); for (int i = 0; i < infix.length(); i++) { char ch = infix.charAt(i); // 情况1：数字，处理多位数 if (Character.isDigit(ch)) { // 连续数字拼接 while (i < infix.length() && Character.isDigit(infix.charAt(i))) { suffix.append(infix.charAt(i)); i++; } i--; // 回退，抵消外层i++ suffix.append(" "); // 空格分隔数字与运算符 } // 情况2：左括号 直接入栈 else if (ch == '(') { opStack.push(ch); } // 情况3：右括号 else if (ch == ')') { // 弹出直到左括号 while (!opStack.isEmpty() && opStack.peek() != '(') { suffix.append(opStack.pop()).append(" "); } opStack.pop(); // 弹出左括号丢弃 } // 情况4：四则运算符 +-*/ else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') { // 栈顶优先级 >= 当前，持续弹出 while (!opStack.isEmpty() && opStack.peek() != '(' && getPriority(opStack.peek()) >= getPriority(ch)) { suffix.append(opStack.pop()).append(" "); } opStack.push(ch); } } // 遍历结束，弹出剩余所有运算符 while (!opStack.isEmpty()) { suffix.append(opStack.pop()).append(" "); } return suffix.toString().trim(); } // 3. 计算后缀表达式 private static int calcSuffix(String suffix) { MyStack<Integer> numStack = new MyStack<>(); // 按空格分割每一项 String[] items = suffix.split(" "); for (String item : items) { // 数字，入数值栈 if (item.length() == 1 && !Character.isDigit(item.charAt(0))) { // 运算符，弹出两个数计算 char op = item.charAt(0); int right = numStack.pop(); int left = numStack.pop(); int res = switch (op) { case '+' -> left + right; case '-' -> left - right; case '*' -> left * right; case '/' -> left / right; default -> throw new RuntimeException("非法运算符"); }; numStack.push(res); } else { // 数字转int入栈 int num = Integer.parseInt(item); numStack.push(num); } } return numStack.pop(); } }运行输出示例
plaintext
====================== 中缀表达式：1+2*(3-4) 后缀表达式：1 2 3 4 - * + 计算结果：-1 ====================== 中缀表达式：10+20*3/5 后缀表达式：10 20 3 * 5 / + 计算结果：22 ====================== 中缀表达式：(100-20)/8+9 后缀表达式：100 20 - 8 / 9 + 计算结果：19补充关键细节说明
1. 自定义栈关键点
- 使用泛型
MyStack<T>，既能存Character（运算符）又能存Integer（数字），复用一套栈逻辑 - 内置数组自动扩容，避免栈溢出，符合真实栈设计
- 边界校验：空栈 pop/peek 直接抛异常，防止数组下标越界
2. 多位数处理难点
普通单字符遍历无法识别10、100这类数字，遇到数字后循环向后读取连续数字，拼接完整数值，后缀中用空格分割数字和运算符，求值时方便分割。
3. 减法、除法顺序坑
后缀计算弹出顺序必须先右操作数，后左操作数： 比如5-3后缀5 3 -，先 pop 得到 3，再 pop 得到 5，5-3； 如果顺序颠倒会算出负数错误结果。
4. 括号处理逻辑
左括号只作为优先级分隔标记，遇到右括号持续出栈直到(，最后丢弃左括号，不会进入后缀表达式参与计算。
