HJ50. 四则运算
题目描述
计算给定四则运算表达式的值。表达式由数字、+、-、*、/、小括号()、中括号[]、大括号{} 组成，运算符之间没有空格。保证表达式合法、过程中无需使用实数、结果为整数。
输入格式
- 一行表达式字符串。
输出格式
- 计算结果（整数）。
示例
示例 1
输入：
3+2*{1+2*[-4/(8-6)+7]}
输出：
25
说明：
3 + 2 * {1 + 2 * [-4/(8-6) + 7]} = 3 + 2 * {1 + 2 * [-2 + 7]} = 3 + 2 * {1 + 10} = 3 + 22 = 25。
解题思路
第一步：理解问题本质
四则运算表达式求值，关键是处理运算优先级（乘除优先于加减）和括号。中括号、大括号与小括号等价。
第二步：暴力解法（eval 直接计算）
把中括号、大括号统一替换为小括号后直接用 eval。
问题：题目明确要求实现计算逻辑，eval 不安全且不符合题意；本题没有给出 eval 被禁止的限制，但标准解法是用递归下降。
第三步：优化解法（栈 + 运算符优先级）
用两个栈（操作数栈、运算符栈）配合优先级表，遇到右括号或低优先级运算符时出栈计算。
问题：需要处理一元负号、括号匹配、优先级比较等细节。
第四步：最优解法（递归下降法）
先把所有括号统一替换为小括号 ()，然后用递归下降法解析，文法如下：
expression → term (('+'|'-') term)*
term → factor (('*'|'/') factor)*
factor → 整数 | '(' expression ')'
三个函数相互递归，天然实现了运算优先级。除法用整数除法 //（题目保证结果均为整数）。
def parse_expr() -> int:
value = parse_term()
while i < n and expr[i] in '+-':
op = expr[i]
i += 1
rhs = parse_term()
value = value + rhs if op == '+' else value - rhs
return value
parse_factor 中处理一元负号：遇到 - 时 sign=-1 并跳过，再读连续数字。
完整代码实现
算法可视化 · 逐帧回放这道题的代码160 帧 · 录制输入 "3+2*{1+2*[-4/(8-6)+7]}"
import sys
def evaluate(expr: str) -> int:
"""递归下降求值"""
expr = expr.replace('{', '(').replace('}', ')').replace('[', '(').replace(']', ')')
n = len(expr)
i = 0
def parse_expr() -> int:
nonlocal i
value = parse_term()
while i < n and expr[i] in '+-':
op = expr[i]
i += 1
rhs = parse_term()
value = value + rhs if op == '+' else value - rhs
return value
def parse_term() -> int:
nonlocal i
value = parse_factor()
while i < n and expr[i] in '*/':
op = expr[i]
i += 1
rhs = parse_factor()
value = value * rhs if op == '*' else value // rhs
return value
def parse_factor() -> int:
nonlocal i
if expr[i] == '(': # 括号表达式
i += 1
val = parse_expr()
i += 1 # 跳过 ')'
return val
# 数字（可能带负号，负号作为一元处理）
sign = 1
if expr[i] == '-':
sign = -1
i += 1
start = i
while i < n and expr[i].isdigit():
i += 1
return sign * int(expr[start:i])
return parse_expr()
def solve() -> None:
"""主求解函数"""
expr = sys.stdin.readline().strip()
print(evaluate(expr))
if __name__ == "__main__":
solve()
示例推演
以 3+2*{1+2*[-4/(8-6)+7]} 为例：
统一括号： 3+2*(1+2*(-4/(8-6)+7))
递归求值：
parse_expr：读3，遇到+，读parse_term。parse_term：读2，遇到*，读parse_factor= 括号表达式。- 括号内
parse_expr：读1，遇到+，读parse_term=2 * (括号)parse_factor=(-4/(8-6)+7)，括号内parse_expr：parse_term：parse_factor=-4，遇到/，读parse_factor=(8-6)= 2，得-4//2 = -2- 遇到
+，读parse_term=7，得-2 + 7 = 5
- 所以
2 * 5 = 10
- 回到外层：
1 + 10 = 11
- 括号内
- 所以外层
2 * 11 = 22
- 回到最外层：
3 + 22 = 25
结果： 25。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| eval 直接计算 | O(L) | O(L) | 不安全，不符合题意 |
| 双栈 + 优先级 | O(L) | O(L) | 需处理一元负号等细节 |
| 递归下降 | O(L) | O(L) | 文法天然表达优先级 |
L 为表达式长度
易错点总结
1. 括号统一
中括号 []、大括号 {} 都要替换为小括号 ()，否则解析失败。
2. 一元负号
数字前的负号要单独处理（如 -4），在 parse_factor 中用 sign 标记，不能当作二元减法。
3. 除法用整数除法
题目保证结果为整数，用 //，注意 Python 的 // 对负数的整除语义，本题结果均为正。
4. 非 local 变量
递归函数中修改 i 要用 nonlocal i 声明，否则会报错或产生错误作用域。
5. 括号后跳过
遇到右括号 ) 读取完括号内表达式后，必须 i += 1 跳过 )。
扩展思考
- 递归下降是编译原理中表达式求值的经典方法，文法设计直接决定优先级。
- 也可用"调度场算法"（Shunting-yard）将中缀转后缀再用栈求值，是另一种通用解法。