【表达式计算】双栈 : 表达式计算问题的通用解法
计算 问题 表达式 通用 解法 双栈
2023-06-13 09:14:22 时间
题目描述
这是 LeetCode 上的「224. 基本计算器」,难度为「困难」。
Tag : 「表达式计算」
给你一个字符串表达式 s
,请你实现一个基本计算器来计算并返回它的值。
示例 1:
输入:s = "1 + 1"
输出:2
示例 2:
输入:s = " 2-1 + 2 "
输出:3
示例 3:
输入:s = "(1+(4+5+2)-3)+(6+8)"
输出:23
提示:
s
由数字
、'+'
、'-'
、'('
、')'
、和' '
组成s
表示一个有效的表达式
双栈
我们可以使用两个栈 nums
和 ops
。
nums
:存放所有的数字ops
:存放所有的数字以外的操作,+/-
也看做是一种操作
然后从前往后做,对遍历到的字符做分情况讨论:
- 空格 : 跳过
(
: 直接加入ops
中,等待与之匹配的)
)
: 使用现有的nums
和ops
进行计算,直到遇到左边最近的一个左括号为止,计算结果放到nums
- 数字 : 从当前位置开始继续往后取,将整一个连续数字整体取出,加入
nums
+/-
: 需要将操作放入ops
中。「在放入之前先把栈内可以算的都算掉」,使用现有的nums
和ops
进行计算,直到没有操作或者遇到左括号,计算结果放到nums
一些细节:
- 由于第一个数可能是负数,为了减少边界判断。一个小技巧是先往
nums
添加一个 0 - 为防止 () 内出现的首个字符为运算符,将所有的空格去掉,并将
(-
替换为(0-
,(+
替换为(0+
(当然也可以不进行这样的预处理,将这个处理逻辑放到循环里去做)
Java 代码:
class Solution {
public int calculate(String s) {
// 存放所有的数字
Deque<Integer> nums = new ArrayDeque<>();
// 为了防止第一个数为负数,先往 nums 加个 0
nums.addLast(0);
// 将所有的空格去掉
s = s.replaceAll(" ", "");
// 存放所有的操作,包括 +/-
Deque<Character> ops = new ArrayDeque<>();
int n = s.length();
char[] cs = s.toCharArray();
for (int i = 0; i < n; i++) {
char c = cs[i];
if (c == '(') {
ops.addLast(c);
} else if (c == ')') {
// 计算到最近一个左括号为止
while (!ops.isEmpty()) {
char op = ops.peekLast();
if (op != '(') {
calc(nums, ops);
} else {
ops.pollLast();
break;
}
}
} else {
if (isNum(c)) {
int u = 0, j = i;
// 将从 i 位置开始后面的连续数字整体取出,加入 nums
while (j < n && isNum(cs[j])) u = u * 10 + (int)(cs[j++] - '0');
nums.addLast(u);
i = j - 1;
} else {
if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
nums.addLast(0);
}
// 有一个新操作要入栈时,先把栈内可以算的都算了
while (!ops.isEmpty() && ops.peekLast() != '(') calc(nums, ops);
ops.addLast(c);
}
}
}
while (!ops.isEmpty()) calc(nums, ops);
return nums.peekLast();
}
void calc(Deque<Integer> nums, Deque<Character> ops) {
if (nums.isEmpty() || nums.size() < 2) return;
if (ops.isEmpty()) return;
int b = nums.pollLast(), a = nums.pollLast();
char op = ops.pollLast();
nums.addLast(op == '+' ? a + b : a - b);
}
boolean isNum(char c) {
return Character.isDigit(c);
}
}
C++ 代码:
class Solution {
public:
void replace(string& s){
int pos = s.find(" ");
while (pos != -1) {
s.replace(pos, 1, "");
pos = s.find(" ");
}
}
int calculate(string s) {
// 存放所有的数字
stack<int> nums;
// 为了防止第一个数为负数,先往 nums 加个 0
nums.push(0);
// 将所有的空格去掉
replace(s);
// 存放所有的操作,包括 +/-
stack<char> ops;
int n = s.size();
for(int i = 0; i < n; i++) {
char c = s[i];
if(c == '(')
ops.push(c);
else if(c == ')') {
// 计算到最近一个左括号为止
while(!ops.empty()) {
char op = ops.top();
if(op != '(')
calc(nums, ops);
else {
ops.pop();
break;
}
}
}
else {
if(isdigit(c)) {
int cur_num = 0, j = i;
// 将从 i 位置开始后面的连续数字整体取出,加入 nums
while(j <n && isdigit(s[j]))
cur_num = cur_num*10 + (s[j++] - '0');
// 注意上面的计算一定要有括号,否则有可能会溢出
nums.push(cur_num);
i = j - 1;
}
else {
if (i > 0 && (s[i - 1] == '(' || s[i - 1] == '+' || s[i - 1] == '-')) {
nums.push(0);
}
// 有一个新操作要入栈时,先把栈内可以算的都算了
while(!ops.empty() && ops.top() != '(')
calc(nums, ops);
ops.push(c);
}
}
}
while(!ops.empty())
calc(nums, ops);
return nums.top();
}
void calc(stack<int> &nums, stack<char> &ops) {
if(nums.size() < 2 || ops.empty())
return;
int b = nums.top(); nums.pop();
int a = nums.top(); nums.pop();
char op = ops.top(); ops.pop();
nums.push(op == '+' ? a+b : a-b);
}
};
- 时间复杂度:
- 空间复杂度:
进阶
- 如果在此基础上,再考虑
*
和/
,需要增加什么考虑?如何维护运算符的优先级? - 在
的基础上,如果考虑支持自定义符号,例如 a / func(a, b) * (c + d)
,需要做出什么调整?
补充
- 对应进阶 1 的补充。
一个支持 + - * / ^ %
的「计算器」,基本逻辑是一样的,使用字典维护一个符号优先级:
class Solution {
Map<Character, Integer> map = new HashMap<>(){{
put('-', 1);
put('+', 1);
put('*', 2);
put('/', 2);
put('%', 2);
put('^', 3);
}};
public int calculate(String s) {
s = s.replaceAll(" ", "");
char[] cs = s.toCharArray();
int n = s.length();
Deque<Integer> nums = new ArrayDeque<>();
nums.addLast(0);
Deque<Character> ops = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
char c = cs[i];
if (c == '(') {
ops.addLast(c);
} else if (c == ')') {
while (!ops.isEmpty()) {
if (ops.peekLast() != '(') {
calc(nums, ops);
} else {
ops.pollLast();
break;
}
}
} else {
if (isNumber(c)) {
int u = 0;
int j = i;
while (j < n && isNumber(cs[j])) u = u * 10 + (cs[j++] - '0');
nums.addLast(u);
i = j - 1;
} else {
if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
nums.addLast(0);
}
while (!ops.isEmpty() && ops.peekLast() != '(') {
char prev = ops.peekLast();
if (map.get(prev) >= map.get(c)) {
calc(nums, ops);
} else {
break;
}
}
ops.addLast(c);
}
}
}
while (!ops.isEmpty() && ops.peekLast() != '(') calc(nums, ops);
return nums.peekLast();
}
void calc(Deque<Integer> nums, Deque<Character> ops) {
if (nums.isEmpty() || nums.size() < 2) return;
if (ops.isEmpty()) return;
int b = nums.pollLast(), a = nums.pollLast();
char op = ops.pollLast();
int ans = 0;
if (op == '+') {
ans = a + b;
} else if (op == '-') {
ans = a - b;
} else if (op == '*') {
ans = a * b;
} else if (op == '/') {
ans = a / b;
} else if (op == '^') {
ans = (int)Math.pow(a, b);
} else if (op == '%') {
ans = a % b;
}
nums.addLast(ans);
}
boolean isNumber(char c) {
return Character.isDigit(c);
}
}
- 关于进阶
,其实和进阶
一样,重点在于维护优先级。但还有一些编码细节:
对于非单个字符的运算符(例如 函数名function
),可以在处理前先将所有非单字符的运算符进行替换(将 function
替换为 @#
等)
然后对特殊运算符做特判,确保遍历过程中识别到特殊运算符之后,往后整体读入(如 function(a,b)
-> @(a, b)
,@(a, b)
作为整体处理)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.224
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
相关文章
- 运筹学单纯形法求解线性规划问题_运筹学单纯形法计算步骤
- “数智话”技术沙龙第二期—隐私计算介绍及安全高效的匿踪查询应用剖析,报名中!
- 考研竞赛每日一练 day 33 渐近线问题的讨论(实质极限的计算)
- 计算几何之线段相交问题(平面扫描)
- UDP协议:校验和的计算
- 哥几个,咱们来聊聊边缘计算的未来、应用落地与新格局
- 云计算顾问:关于企业策略的4个问题
- Power BI解决多指标批量展示问题:字段参数、计算组以及手工表
- python+PyQt5|文件传输测速和计算eta
- 5G和边缘计算如何为企业带来好处?
- 量子计算结果的真实性问题——量子计算验证协议
- 【Android 性能优化】应用启动优化 ( 启动白屏问题 | 应用启动时间测量 | 冷启动 | 热启动 | 应用启动时间计算源码分析 )
- 【计算理论】可判定性 ( 非确定性有限自动机的接受问题 | 证明 “非确定性有限自动机的接受问题“ 的可判定性 )
- 【计算理论】计算复杂性 ( NP 完全问题 - 布尔可满足性问题 ★ | 布尔可满足性问题是 NP 完全问题证明思路 ) ★
- 【计算理论】计算复杂性 ( 证明团问题是 NP 完全问题 )
- 【计算理论】计算复杂性 ( 无向图独立集问题 | 独立集问题是 NP 完全问题证明思路 | 证明独立集问题是 NP 完全问题 )
- 【计算理论】计算复杂性 ( NP 完全问题 | 顶点覆盖问题 | 哈密顿路径问题 | 旅行商问题 | 子集和问题 )
- WAIC 2021 | 百度量子计算段润尧:从理论到实践谈量子人工智能
- odoo 开发入门教程系列-计算的字段和变更(Computed Fields And Onchanges)
- 云计算运维kubernetes集群里集成Apollo配置中心
- 运算MySQL中浮点数计算的精确性问题(mysql的浮点数)
- Redis:快速、高效的计算方式(redis计算)
- 企业利用云计算平台Hadoop的10种方式
- 从SQLServer中计算出儒略日(sqlserver儒略日)
- MSSQL聚合统计技巧:快速计算记录个数(mssql 聚合统计个数)
- 用大白菜种植linux系统,开启新的计算生态!(大白菜做linux系统)
- 3亿数据瞬间落地Oracle计算史上最快记录(3亿条数据放oracle)
- 计算Oracle日期之间的差值(oracle 两日期之差)
- Redis实现超时计算的新技术(redis 超时计算)
- php时间计算问题小结
- C#中计算时间差中的小数问题解决