1. 表达式求值与字符删除问题概述
在编程面试和算法竞赛中，表达式求值和字符串操作是两类经典的基础题型。"83.表达式求值"考察的是对数学表达式解析和计算的能力，而"84.删除字符"则测试对字符串处理的熟练程度。这两个问题看似简单，但实际包含了栈结构应用、运算符优先级处理、字符串遍历技巧等核心知识点。
我曾在多次技术面试中遇到这两个问题的变种，也见过不少候选人因为忽略边界条件而翻车。本文将结合我的实战经验，从问题分析、算法设计到代码实现，完整拆解这两个问题的解决思路。无论你是准备面试的新手，还是想巩固基础的开发者，都能从中获得可直接复用的解题模板。
2. 表达式求值问题详解
2.1 问题描述与核心难点
表达式求值要求实现一个能计算包含加减乘除和括号的数学表达式的程序。给定如"3+2*2/(1+1)"的字符串，程序需要正确输出计算结果4。这个问题的核心难点在于：
- 运算符优先级处理：乘除优先于加减
- 括号改变运算顺序：括号内要先计算
- 数字可能是多位数：不能简单按字符处理
- 空格干扰：需要正确处理表达式中的空格
2.2 双栈解法原理
最经典的解决方案是使用双栈（数字栈和运算符栈）的算法：
python复制def calculate(s: str) -> int:
num_stack = []
op_stack = []
i = 0
n = len(s)
while i < n:
# 处理逻辑...
# 剩余运算...
return num_stack[0]
算法流程分为四个关键步骤：
- 遇到数字时完整读取整个数字
- 遇到运算符时比较优先级决定是否先计算
- 遇到左括号直接入栈
- 遇到右括号则计算到左括号为止
2.3 完整实现与关键代码
以下是Python的完整实现，包含详细注释：
python复制def calculate(s: str) -> int:
def compute(num1, num2, op):
if op == '+': return num1 + num2
if op == '-': return num1 - num2
if op == '*': return num1 * num2
if op == '/': return num1 // num2
# 定义运算符优先级
priority = {'+':1, '-':1, '*':2, '/':2}
num_stack = []
op_stack = []
i = 0
n = len(s)
while i < n:
if s[i] == ' ':
i += 1
continue
if s[i].isdigit():
# 读取完整数字
num = 0
while i < n and s[i].isdigit():
num = num * 10 + int(s[i])
i += 1
num_stack.append(num)
elif s[i] == '(':
op_stack.append(s[i])
i += 1
elif s[i] == ')':
# 计算到左括号
while op_stack[-1] != '(':
num2 = num_stack.pop()
num1 = num_stack.pop()
op = op_stack.pop()
num_stack.append(compute(num1, num2, op))
op_stack.pop() # 弹出左括号
i += 1
else:
# 运算符：比较优先级
while op_stack and op_stack[-1] != '(' and \
priority[op_stack[-1]] >= priority[s[i]]:
num2 = num_stack.pop()
num1 = num_stack.pop()
op = op_stack.pop()
num_stack.append(compute(num1, num2, op))
op_stack.append(s[i])
i += 1
# 处理剩余运算
while op_stack:
num2 = num_stack.pop()
num1 = num_stack.pop()
op = op_stack.pop()
num_stack.append(compute(num1, num2, op))
return num_stack[0]
2.4 边界条件与测试用例
表达式求值容易出错的边界情况包括：
- 开头有负号："-1+2"
- 连续运算符："3+-2"
- 空表达式：""
- 只有数字："42"
- 多层嵌套括号："1+(2*(3+4)-5)"
完整的测试集应该包含这些情况：
python复制test_cases = [
("3+2*2", 7),
(" 3/2 ", 1),
(" 3+5 / 2 ", 5),
("1 + 1", 2),
("(1+(4+5+2)-3)+(6+8)", 23),
("-1+2", 1),
("1-( -2)", 3)
]
3. 删除字符问题详解
3.1 问题描述与变种
"84.删除字符"问题的典型描述是：给定一个字符串s和一个整数k，需要删除k个字符后使剩下的字符串字典序最小。例如：
- 输入：s = "1432219", k = 3
- 输出："1219"
这个问题有多个变种：
- 删除k个字符使字典序最小
- 删除k个字符使字典序最大
- 删除重复字符使字符串唯一
- 删除特定模式的字符
3.2 单调栈解法
使用单调栈可以在O(n)时间内解决问题：
python复制def removeKdigits(num: str, k: int) -> str:
stack = []
remain = len(num) - k
for digit in num:
while k and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# 处理前导零和剩余k
return ''.join(stack[:remain]).lstrip('0') or '0'
算法核心思想：
- 维护一个单调递增的栈
- 当遇到比栈顶小的数字时，删除栈顶元素（因为保留当前数字能得到更小的字典序）
- 最终取前n-k个字符作为结果
3.3 完整实现与优化
考虑前导零和剩余k的完整实现：
python复制def removeKdigits(num: str, k: int) -> str:
stack = []
n = len(num)
remain = n - k
for digit in num:
while k > 0 and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# 如果还有剩余的k，从末尾删除
if k > 0:
stack = stack[:-k]
# 构建结果并处理前导零
result = ''.join(stack[:remain]).lstrip('0')
return result if result else '0'
3.4 常见错误与测试用例
容易出错的场景：
- 全部删除的情况：num = "10", k = 2
- 前导零处理：num = "10200", k = 1 → "200"
- 连续相同数字：num = "112", k = 1 → "11"
- k=0的情况：num = "123", k = 0 → "123"
完整测试集：
python复制test_cases = [
("1432219", 3, "1219"),
("10200", 1, "200"),
("10", 2, "0"),
("9", 1, "0"),
("123456", 3, "123"),
("111111", 3, "111")
]
4. 问题对比与综合应用
4.1 算法思想对比
虽然两个问题看似不同，但都使用了栈这一数据结构：
- 表达式求值：双栈处理运算符优先级
- 删除字符：单调栈维护字典序
它们的共同特点是都需要在遍历过程中根据特定条件（运算符优先级/字典序）进行回溯处理。
4.2 复杂度分析
表达式求值：
- 时间复杂度：O(n)，每个元素最多入栈出栈一次
- 空间复杂度：O(n)，最坏情况下栈深度为n
删除字符：
- 时间复杂度：O(n)，每个字符最多被处理两次（入栈和出栈）
- 空间复杂度：O(n)，栈的大小最多为n
4.3 实际应用场景
这两个算法在实际工程中有广泛应用：
-
表达式求值：
- 计算器应用开发
- 公式解析引擎
- 数据库查询优化
- 电子表格计算
-
删除字符：
- 数据压缩算法
- 日志信息精简
- 用户输入清理
- 序列号生成优化
5. 扩展练习与进阶方向
5.1 表达式求值变种
- 添加指数运算符："2^3" → 8
- 支持变量代入："x+2"，当x=3时输出5
- 处理浮点数计算："3.14*2"
- 添加数学函数："sin(0)+max(1,2)"
5.2 删除字符变种
- 删除字符使字符串成为回文
- 删除字符使相邻字符不相同
- 删除字符使满足特定模式
- 在删除限制下求最大/小子序列
5.3 推荐练习题
为了巩固这两个问题的解法，建议尝试以下LeetCode题目：
- 基本型：224. Basic Calculator, 402. Remove K Digits
- 进阶型：772. Basic Calculator III, 321. Create Maximum Number
- 综合型：1096. Brace Expansion II, 1673. Find the Most Competitive Subsequence
6. 面试技巧与注意事项
6.1 表达式求值常见失误
- 忽略空格处理：没有跳过空格导致数字解析错误
- 运算符优先级颠倒：先处理加减后处理乘除
- 括号匹配错误：没有正确处理嵌套括号
- 数字拼接错误：多位数被拆分成单个数字
- 栈操作顺序错误：num1和num2弹出顺序影响减法和除法
6.2 删除字符常见陷阱
- 前导零处理不当：结果出现前导零或空结果未返回"0"
- 剩余k处理遗漏：遍历结束后k仍大于0的情况
- 字典序理解错误：误以为直接删除最大数字
- 相等数字处理：遇到相同数字时是否弹出
- 边界条件忽略：k=0或k=len(num)的情况
6.3 面试回答策略
当面试官提出这些问题时，建议的回答框架：
- 明确问题：确认输入输出要求和边界条件
- 举例说明：用具体例子解释算法思路
- 复杂度分析：说明时间空间复杂度
- 代码实现：写出清晰有注释的代码
- 测试验证：用边缘案例测试代码正确性
我在面试候选人时，最看重的是对边界条件的考虑和代码的可读性。一个能主动讨论各种边界情况的候选人，通常在实际工作中也会更严谨。