[LeetCode] 772. Basic Calculator III 基本计算器之三
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open (
and closing parentheses )
, the plus +
or minus sign -
, non-negative integers and empty spaces .
The expression string contains only non-negative integers, +
, -
, *
, /
operators , open (
and closing parentheses )
and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647]
.
Some examples:
"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12
Note: Do not use the eval
built-in library function.
这道题是基本计算器系列的第三道,前两道分别为 Basic Calculator 和 Basic Calculator II,区别是,第一道只有加减法跟括号,第二道只有加减乘除法,而这第三道既有加减乘除法又有括号运算。其实做过前两道题的话,那么这道题也就没什么问题,因为把前两道题的解法综合一下就是这道题的解法啦。由于此题既有括号,又有乘除法,我们知道括号是优先级最高的,但是好就好在我们可以将括号里的内容当作一个整体调用递归函数来处理。而其他部分,就跟第二道一模一样了。我们还是分情况来处理遍历,我们需要几个变量,num 表示当前的数字,curRes 表示当前的结果,res 为最终的结果,op 为操作符号,初始化为 '+'。当遇到数字的时候,我们将 num 自乘以 10 并加上这个数字,这是由于可能遇到多位数,所以每次要乘以 10。当遇到括号的时候,这里就有一个小 trick,由于表示可能会有括号嵌套括号,所以我们如果搜索右括号的话,就有可能使得括号没有正确的匹配上,所以我们用一个变量 cnt,遇到左括号自增1,遇到右括号自减1,当 cnt 为0的时候,说明括号正好完全匹配,这个 trick 在验证括号是否 valid 的时候经常使用到。然后我们就是根据左右括号的位置提取出中间的子字符串调用递归函数,返回值赋给 num。如果遇到符号,或者是最后一个位置的字符时,我们根据 op 的值对 num 进行分别的加减乘除的处理,结果保存到 curRes 中。然后再次判读如果 op 是加或减,或者是最后一个位置的字符时,将 curRes 加到结果 res 中,并且 curRes 重置为0。最后将当前字符c赋值给 op(注意这里只有当时最后一个位置的字符时,才有可能不是运算符号,不过也不要紧了,因为遍历已经结束了),num 也要重置为0,参见代码如下:
class Solution {
public:
int calculate(string s) {
int n = s.size(), num = , curRes = , res = ;
char op = '+';
for (int i = ; i < n; ++i) {
char c = s[i];
if (c >= '' && c <= '') {
num = num * + c - '';
} else if (c == '(') {
int j = i, cnt = ;
for (; i < n; ++i) {
if (s[i] == '(') ++cnt;
if (s[i] == ')') --cnt;
if (cnt == ) break;
}
num = calculate(s.substr(j + , i - j - ));
}
if (c == '+' || c == '-' || c == '*' || c == '/' || i == n - ) {
switch (op) {
case '+': curRes += num; break;
case '-': curRes -= num; break;
case '*': curRes *= num; break;
case '/': curRes /= num; break;
}
if (c == '+' || c == '-' || i == n - ) {
res += curRes;
curRes = ;
}
op = c;
num = ;
}
}
return res;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/772
类似题目:
参考资料:
https://leetcode.com/problems/basic-calculator-iii/
https://leetcode.com/problems/basic-calculator-iii/discuss/113597/C++-recursive
https://leetcode.com/problems/basic-calculator-iii/discuss/113593/C++-Consise-Solution
LeetCode All in One 题目讲解汇总(持续更新中...)
最新文章
- Raspberry Pi UART with PySerial
- Hello, Android 快速入门
- JAVA 5.17习题
- Wcf for wp8 上传图片到服务器,将图片名字插入数据库字段(五)
- windows下svn自动更新
- poj1651 区间dp
- 51nod 1021 石头归并
- JSF 2 graphicImage example
- iLearning D3.js 2.0 released
- QT5新手上路(1)安装
- .net嵌入c#代码(投票练习)
- 解决后端动态生成css时无法调用
- Struts第八篇【资源国际化、对比JSP的资源国际化】
- PHP金钱数字转金钱大写
- org.apache.ibatis.exceptions.PersistenceException: ### Error querying database. Cause: com.mysql.jdbc.exceptions.jdbc4.CommunicationsException: Communications link failure The last packet sent succ
- MySQL大数据量分页性能优化
- HDU 5402 Travelling Salesman Problem(棋盘染色 构造 多校啊)
- C# 键盘中的按键对应KeyValue
- python如何获取公众号下面粉丝的openid
- 关于数组中加入相同的view的试验
热门文章
- 【MySQL】GTID小结
- Focal Loss tensorflow 实现
- 【MySQL配置参数】sync_binlog和innodb_flush_log_at_trx_commit
- Effective Python 编写高质量Python代码的59个有效方法
- Java生鲜电商平台-高并发的设计与架构
- 记录vue用 html5+做移动APP 用barcode做扫一扫功能时安卓 的bug(黑屏、错位等等)和解决方法
- 通过优化Gunicorn配置获得更好的性能
- ZAP 代理 Chrome 系统 win10
- centos7 下面显卡驱动安装
- 团队项目-Alpha2版本发布