大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。
“给定一个字符串表达式,实现一个基本计算器来计算并返回它的值。”
题目链接:
来源:力扣(LeetCode)
给你一个字符串表达式 s
,请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数,比如 eval()
。
示例 1:
输入: s = "1 + 1"
输出: 2
示例 2:
输入: s = " 2-1 + 2 "
输出: 3
题意要求给定字符串表达式,实现基本计算器来计算并返回它的值。
这段字符串表达式,可能包含的元素有数字和括号、运算符加号和减号。
只有加减法,可以把括号全都展开来写,例如 2 - (1 - 3)展开成 2 - 1 + 3。
也就是,如果当前位置处于括号之内,则:
可以考虑维护一个栈ops,栈顶元素存入根据括号所判断的符号sign:
每当遇到左括号,则将当前的sign取值压入栈中。
每当遇到右括号,则从栈中弹出一个元素。
代码参考:
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;
}
}
时间复杂度:O(n)
其中n为字符串s的长度,需要遍历字符串s一次,计算表达式的值。
空间复杂度:O(n)
其中n为字符串s的长度,空间复杂度屈取决于栈的空间,栈中的元素数量不超过n。
本题基于栈这一数据结构可以演变出很多种解法。
比如使用双栈,一个栈存放所有的数字,一个栈存放所有数字意外的操作。
然后还是根据符号跟括号判断压入栈的元素。