别被字符串骗了 — 从手撸计算器到一遍过的 Basic Calculator II

别被字符串骗了 — 从手撸计算器到一遍过的 Basic Calculator II

作者：Echo_Wish

先来一句实话：这道题看起来像字符串题，实际上考的是你对运算优先级、流式计算（streaming）和状态管理的理解。LeetCode 上的Basic Calculator II（只有+ - * /，没有括号）是刷题里经典的一道：既能考你写出正确的实现，也能让你在代码里体现工程思路 —— 安全、稳健、易读、可拓展。

今天咱不走过场，按“先讲直观原理 → 再讲常见思路 → 最后给出干净、高质量实现 + 解析”的路线把这题讲明白，代码里全注释，手把手教你为什么这么写。风格就像和老同学对面聊，一句话一句敲清楚。

题目回顾（一句话版）

给定一个只包含非负整数、+ - * /操作符和空格的字符串，计算并返回表达式的值。除法按截断向零（trunc toward zero）处理。保证表达式有效。

举个小例子："3+2*2"→7；" 3/2 "→1（整除截断）；" 3+5 / 2 "→5。

看起来简单，但坑在这儿：*和/优先级比+和-高。你需要在一次线性扫描里正确处理优先级，而不是先分割再暴力算。

直观思路（口语版）

把表达式想成一条流水线：你从左到右一口气读过去，遇到数字就收集，遇到操作符就根据上一个操作符决定怎么处理当前数字。

关键思想之一是：延后 + 和 - 的求和，但立即完成 * / 的计算。也就是说，当你看到*或/，你必须立刻把上一个“待加入总和”的值与当前数字做掉乘除，然后把结果继续作为“待加入总和”的值；但当你看到+或-时，可以把之前的待加入值放进最终和（或栈），然后把当前数字作为新的待加入值（记号由操作决定正负）。

两种常见实现：

1. 栈（stack）方案：遇到数字和操作符，通过栈保存中间的带符号数，*//立刻弹出栈顶与当前做运算并将结果推回；结束后把栈里所有数相加。直观但需 O(n) 额外空间（栈）。

2. 常量空间方案（lastNum 技巧）：不显式使用栈，而是维护lastNumber（相当于栈顶），result（当前总和不含lastNumber），sign（上一个操作符）。遇到+/-时把lastNumber加到result，并将lastNumber设为当前数字或其负数；遇到*//时直接修改lastNumber。遍历结束把lastNumber加到result即得答案。这个方案 O(1) 空间，直观高效。

我偏好第二种，因为更简洁、内存友好，同时逻辑也一清二楚：result固定保存那些已经“结算”的加项，lastNumber存储还没被加入result的那一项（可能被后续*//改写）。

一个示例把流程走一遍

表达式："3+2*2-4/3"

逐步（常量空间方案）：

• 初始：result = 0,last = 0,sign = '+'
• 读到3（num=3），下一个是+（sign=‘+’) → 遇到+：把last(0)加到result->result=0，把last = +3
• 读到2（num=2），下一个是*（sign=‘+’, 当前符号是上一个 ‘+’）→ 遇到*：不要把last加到result，而是更新last = last * num = 3*2 = 6
• 读到2（num=2），下一个是-（sign=‘*’) → 遇到-：把last(6)加到result->result=6，把last = -2
• 读到4（num=4），下一个是/（sign=‘-’) → 遇到/：更新last = last / num = -2 / 4截断向零，等于0（注意符号和截断），…
• 最终把last加回result得答案（示例用于说明，实际数值需按整数截断规则算清）。

注意截断向零的细节在 Python 中做整数除法要谨慎（负数除法需要用 int(a/b) 而不是 //，因为 // 是向下取整）。

代码实现（Python，含详细注释）

defcalculate(s:str)->int:""" 计算只包含非负整数和 + - * / 空格的表达式结果。 思路：一次遍历，维护三个变量： - result: 已经结算并加入总和的部分（不含 last_num） - last_num: 当前“待加入”的数字，这个数字会参与连续的 * / 运算 - sign: 上一个操作符（决定如何处理当前读到的数） 结束时返回 result + last_num。 注意：除法需按截断向零（trunc toward zero），在 Python 中需用 int(a / b) 来实现。 时间复杂度 O(n)，空间 O(1)（不计输入字符串）。 """s=s.strip()ifnots:return0result=0# 累积的和（已结算）last_num=0# 上一个待结算的数字（可能被 * / 连续修改）num=0# 当前读取的数字sign='+'# 初始化为 '+', 便于处理第一个数字i=0n=len(s)whilei<n:ch=s[i]ifch.isdigit():# 读取完整数字（可能多位）num=num*10+(ord(ch)-ord('0'))# 如果当前字符是运算符或者到达字符串末尾，需要基于上一个 sign 把 num 处理进 last_num 或 resultif(notch.isdigit()andch!=' ')ori==n-1:ifsign=='+':# 把之前的 last_num 结算进 result，新的 last_num 为当前 numresult+=last_num last_num=numelifsign=='-':result+=last_num last_num=-numelifsign=='*':last_num=last_num*numelifsign=='/':# 在 Python 中，负数除法 // 是向下取整，不是截断向零# 使用 int(a / b) 来实现截断向零行为# 注意：last_num 可能为负数last_num=int(last_num/num)# 重置 num，并更新 sign 为当前运算符num=0sign=ch i+=1returnresult+last_num# 简单测试print(calculate("3+2*2"))# 7print(calculate(" 3/2 "))# 1print(calculate(" 3+5 / 2 "))# 5

复杂度与边界说明

• 时间复杂度：O(n)，只遍历字符串一次（数字字符也只被读一次）。
• 空间复杂度：O(1)，只用常量级额外变量。
• 注意点：数字可能多位；字符串中有空格；必须对负数除法做截断向零（语言差异要处理）。

Echo_Wish 的一点感受（收个尾）

这类题好在它能逼着你把“算法思想”落地为“工程代码”：要考虑流式解析（stream parsing）、数字边界、符号优先级、语言语义细节（例如 Python 的除法行为），以及代码的可读性。刷题不仅是为了 AC，更是为了把“一套优雅可复用的思考方式”刻进脑子里：遇到字符串处理类的问题，先想状态机，然后把状态压缩成最小变量，这套套路以后能省你大把时间。