☆打卡算法☆LeetCode 224. 基本计算器 算法解析
☆打卡算法☆LeetCode 224. 基本计算器 算法解析
恬静的小魔龙
发布于 2022-09-27 09:45:05
发布于 2022-09-27 09:45:05
大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个字符串表达式，实现一个基本计算器来计算并返回它的值。”
题目链接：
来源：力扣（LeetCode）
2、题目描述
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1：
输入： s = "1 + 1"
输出： 2示例 2：
输入： s = " 2-1 + 2 "
输出： 3二、解题
1、思路分析
题意要求给定字符串表达式，实现基本计算器来计算并返回它的值。
这段字符串表达式，可能包含的元素有数字和括号、运算符加号和减号。
只有加减法，可以把括号全都展开来写，例如 2 - （1 - 3）展开成 2 - 1 + 3。
也就是，如果当前位置处于括号之内，则：
- 遇到以 - 号开头的括号，此后的符号都要被翻转
- 遇到以 + 号开头的括号，不变
可以考虑维护一个栈ops，栈顶元素存入根据括号所判断的符号sign：
- 如果遇到+号，则更新sign ← ops.top()
- 如果遇到-号，则更新sign ← -ops.top()
每当遇到左括号，则将当前的sign取值压入栈中。
每当遇到右括号，则从栈中弹出一个元素。
2、代码实现
代码参考：
class Solution {
public int calculate(String s) {
Deque<Integer> ops = new LinkedList<Integer>();
ops.push(1);
int sign = 1;
int ret = 0;
int n = s.length();
int i = 0;
while (i < n) {
if (s.charAt(i) == ' ') {
i++;
} else if (s.charAt(i) == '+') {
sign = ops.peek();
i++;
} else if (s.charAt(i) == '-') {
sign = -ops.peek();
i++;
} else if (s.charAt(i) == '(') {
ops.push(sign);
i++;
} else if (s.charAt(i) == ')') {
ops.pop();
i++;
} else {
long num = 0;
while (i < n && Character.isDigit(s.charAt(i))) {
num = num * 10 + s.charAt(i) - '0';
i++;
}
ret += sign * num;
}
}
return ret;
}
}
image.png
3、时间复杂度
时间复杂度：O(n)
其中n为字符串s的长度，需要遍历字符串s一次，计算表达式的值。
空间复杂度：O(n)
其中n为字符串s的长度，空间复杂度屈取决于栈的空间，栈中的元素数量不超过n。
三、总结
本题基于栈这一数据结构可以演变出很多种解法。
比如使用双栈，一个栈存放所有的数字，一个栈存放所有数字意外的操作。
然后还是根据符号跟括号判断压入栈的元素。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2022-08-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录