HDU 1237 简单计算器Java双栈实现及Windows本地测试方案

✅ 这是一道经典的 **中缀表达式求值** 问题（HDU 1237），要求支持 `+ - * /` 和**非负整数**，**空格分隔**，且**无括号** —— 关键点在于： > ✅ **乘除优先于加减**，需用栈（或双栈）模拟运算优先级。 ⚠️ 注意：题目明确「整数和运算符之间用一个空格分隔」，例如 `"1 + 2 * 3"`，不是 `"1+2*3"`，所以可直接 `split(" ")` 安全切分。 --- ### ✅ 解题思路（双栈法 · 推荐 · 清晰易懂） | 栈 | 作用 | |----|------| | `nums`（`Deque<Double>`） | 存储待参与运算的数字（注意：除法结果可能是小数） | | `ops`（`Deque<Character>`） | 存储待处理的运算符（只存 `+` 或 `-`；`*`/`/` 立即计算） | 🔹 **核心规则（处理每个 token）：** - 遇到数字 → 入 `nums` - 遇到 `+` 或 `-` → 入 `ops`（延迟计算） - 遇到 `*` 或 `/` → **立即取 `nums` 栈顶，与下一个数字运算，结果压回 `nums`** - 最后统一从左到右执行 `+`/`-`（即 `nums` 中剩余数字按 `ops` 中符号累加） ✅ 优势：无需处理负号（题目说“非负整数”，无负数输入），逻辑干净，不易错。 --- ### ✅ Java 实现（Windows 可直接编译运行 · 单文件 · 支持多组输入） ```java // ✅ Solution.java —— HDU 1237 简单计算器（双栈法） import java.util.*; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNextLine()) { String line = sc.nextLine().trim(); if (line.isEmpty()) break; // HDU 多组输入，空行结束（或 EOF） String[] tokens = line.split("\\s+"); // 按空白分割（兼容多个空格） if (tokens.length == 0) continue; // 🔹 双栈 Deque<Double> nums = new ArrayDeque<>(); Deque<Character> ops = new ArrayDeque<>(); // 🔹 第一个 token 必为数字 nums.push(Double.parseDouble(tokens[0])); // 🔹 从第 1 个 token 开始（即第一个运算符） for (int i = 1; i < tokens.length; i += 2) { // 每次跳 2：i→op, i+1→next num if (i >= tokens.length || i + 1 >= tokens.length) break; char op = tokens[i].charAt(0); double nextNum = Double.parseDouble(tokens[i + 1]); if (op == '+' || op == '-') { ops.push(op); nums.push(nextNum); } else if (op == '*') { nums.push(nums.pop() * nextNum); } else if (op == '/') { nums.push(nums.pop() / nextNum); } } // 🔹 计算最终结果：从底向上（但栈是后进先出）→ 我们把 nums 转成 list 从左到右算 // 更简单做法：用「符号数组」+「数字数组」模拟；但这里用栈逆序还原 List<Double> allNums = new ArrayList<>(); List<Character> allOps = new ArrayList<>(); while (!nums.isEmpty()) allNums.add(nums.pollLast()); // 从栈底到顶 → 正序数字 while (!ops.isEmpty()) allOps.add(ops.pollLast()); // 同理 double res = allNums.get(0); for (int i = 0; i < allOps.size(); i++) { char op = allOps.get(i); double b = allNums.get(i + 1); if (op == '+') res += b; else if (op == '-') res -= b; } System.out.printf("%.2f%n", res); } sc.close(); } } ``` --- ### ✅ 运行方式（Windows CMD） ```cmd javac Solution.java java Solution ``` 📌 **输入样例（手动输入或重定向）：** ``` 1 + 2 2 * 3 - 4 10 / 2 + 3 * 2 ``` ⌨️ 手动输入时，每行一个表达式，**按 Ctrl+Z 回车（Windows EOF）结束**；或使用： ```cmd echo 1 + 2 & echo 2 * 3 - 4 & echo 10 / 2 + 3 * 2 | java Solution ``` ✅ 输出： ``` 3.00 2.00 11.00 ``` --- ### ✅ 验证关键样例：`10 / 2 + 3 * 2` | 步骤 | tokens | nums栈（从底→顶） | ops栈 | 说明 | |------|--------|-------------------|--------|------| | 初始 | `["10"]` | `[10.0]` | `[]` | 读入第一个数 | | i=1 | `+` → `ops.push('+')`, `nums.push(2.0)` | `[10.0, 2.0]` | `['+']` | ❌ 错！应先算 `/`！ → **上面逻辑有缺陷？** ⚠️ ⚠️ ⚠️ **重大修正：上面实现未正确处理运算符优先级顺序！** 因为 `tokens = ["10", "/", "2", "+", "3", "*", "2"]`，按 `i+=2` 会依次处理： - i=1 → op='/'，next="2" → `10/2=5.0` → nums=[5.0] - i=3 → op='+'，next="3" → ops=['+'], nums=[5.0,3.0] - i=5 → op='*'，next="2" → `3*2=6` → nums=[5.0,6.0] → 最后 `5.0 + 6.0 = 11.00` ✅ 正确！ ✅ 所以原代码逻辑 **实际是正确的**（因为 `i` 每次跳 2，`tokens[i]` 总是运算符，`tokens[i+1]` 是其后数字，且 `*`/`/` 立即合并，`+`/`-` 延迟）—— 已覆盖优先级。 --- ### ✅ 更健壮版本（增强容错 · 推荐提交版） ```java import java.util.*; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNextLine()) { String line = sc.nextLine().trim(); if (line.isEmpty()) break; String[] tokens = line.split("\\s+"); if (tokens.length == 0) continue; // 使用 ArrayList 模拟栈（更直观索引） List<Double> nums = new ArrayList<>(); List<Character> ops = new ArrayList<>(); // 第一个必为数字 nums.add(Double.parseDouble(tokens[0])); // 处理后续 "op num" 对 for (int i = 1; i < tokens.length; i += 2) { if (i + 1 >= tokens.length) break; char op = tokens[i].charAt(0); double num = Double.parseDouble(tokens[i + 1]); if (op == '*' || op == '/') { double last = nums.remove(nums.size() - 1); nums.add(op == '*' ? last * num : last / num); } else if (op == '+' || op == '-') { ops.add(op); nums.add(num); } } // 计算最终结果：left-to-right with ops double res = nums.get(0); for (int i = 0; i < ops.size(); i++) { if (ops.get(i) == '+') res += nums.get(i + 1); else res -= nums.get(i + 1); } System.out.printf("%.2f%n", res); } sc.close(); } } ``` --- ### 📚 补充知识（为什么不用 `eval()`？） - Java **没有内置 `eval`**（安全限制）； - 本题考察 **栈+运算符优先级建模能力**，是经典算法面试题； - 时间复杂度：O(n)，空间 O(n)；稳定高效。 --- 需要我为你生成： - ✅ **支持括号的升级版（如 `(1+2)*3`）** - ✅ **转后缀表达式（逆波兰 RPN）解法（单栈）** - ✅ **可视化计算过程（打印每步 nums/ops 状态）** - ✅ **LeetCode 风格单元测试（JUnit 5 单文件版）** 欢迎继续提问！ 💻 ######[AI写代码神器 | 2140点数解答 | 2026-04-18 13:24:32]