整体思路总览一、需求拆解手动实现栈Stack底层用数组存储提供入栈、出栈、查看栈顶、判空、获取大小基础方法不使用 Java 自带java.util.Stack。实现四则运算计算器分两步核心算法中缀表达式转后缀表达式逆波兰表达式解决运算符优先级、括号问题后缀表达式求值借助自定义栈完成数值计算支持加减乘除 - * /、括号()、多位数、运算优先级* / -二、栈设计思路栈是后进先出 (LIFO)线性结构底层动态扩容数组简化版固定数组方便理解指针top记录栈顶下标top-1代表空栈核心方法push()入栈top存入元素pop()出栈取出栈顶元素top--栈空抛异常peek()查看栈顶不弹出isEmpty()判断栈是否为空size()返回栈内元素个数三、中缀转后缀表达式思路核心规则中缀12*(3-4)人看懂后缀1 2 3 4 - * 计算机方便栈计算遍历表达式每一个字符数字直接拼接到后缀结果字符串处理多位数连续数字合并左括号(直接压入运算符栈右括号)循环弹出栈顶运算符到后缀直到遇到左括号弹出左括号丢弃运算符-*/栈不为空 且 栈顶不是左括号 且栈顶运算符优先级 ≥ 当前运算符持续弹出栈顶运算符到后缀最后把当前运算符入栈遍历结束后把栈中剩余所有运算符依次弹出追加到后缀末尾优先级规则* / 2 - 1括号无优先级四、后缀表达式求值思路栈计算创建数值栈遍历后缀表达式分割后的每一项数字转为整数压入数值栈运算符弹出两个数注意顺序先弹右操作数再弹左操作数例3 4 -先出 4再出 3计算3-4计算结果重新压回栈遍历完成栈中仅剩一个元素即为最终结果完整 Java 代码1. 自定义栈类支持泛型运算符、数字都能存java运行/** * 手动实现栈 LIFO * param T 存储元素类型 */ public class MyStackT { // 底层数组存储 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 12*(3-4); String expr2 1020*3/5; String expr3 (100-20)/89; 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) { // 运算符栈 MyStackCharacter 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) { MyStackInteger 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 中缀表达式12*(3-4) 后缀表达式1 2 3 4 - * 计算结果-1 中缀表达式1020*3/5 后缀表达式10 20 3 * 5 / 计算结果22 中缀表达式(100-20)/89 后缀表达式100 20 - 8 / 9 计算结果19补充关键细节说明1. 自定义栈关键点使用泛型MyStackT既能存Character运算符又能存Integer数字复用一套栈逻辑内置数组自动扩容避免栈溢出符合真实栈设计边界校验空栈 pop/peek 直接抛异常防止数组下标越界2. 多位数处理难点普通单字符遍历无法识别10、100这类数字遇到数字后循环向后读取连续数字拼接完整数值后缀中用空格分割数字和运算符求值时方便分割。3. 减法、除法顺序坑后缀计算弹出顺序必须先右操作数后左操作数 比如5-3后缀5 3 -先 pop 得到 3再 pop 得到 55-3 如果顺序颠倒会算出负数错误结果。4. 括号处理逻辑左括号只作为优先级分隔标记遇到右括号持续出栈直到(最后丢弃左括号不会进入后缀表达式参与计算。
原理、配置与故障排查实战指南)
