原题
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式可以包含左括号 (
,右括号 )
,加号 +
,减号 -
,非负整数和空格 。
示例1:
输入: "1 + 1"
输出: 2
示例2:
输入: " 2-1 + 2 "
输出: 3
示例 3:
输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23
说明:
- 你可以假设所给定的表达式都是有效的。
- 请不要使用内置的库函数
eval
。
解法
思想
操作数栈的思想
代码
原来以为递归会很取巧,结果遇到了很多细节问题。
class Solution {
public int calculate(String s) {
if(s.indexOf("(")==-1){
int num = 0;
int sum = 0;
boolean negative = false;
boolean hasNum = false;
for(char i:s.toCharArray()){
if(i==' ') continue;
if(i>='0'&&i<='9') {
hasNum = true;
if(negative==false) num=(num*10)+(i-48);
else num=(num*10)-(i-48);
}
if(i=='+'){
hasNum = false;
sum+=num;
num = 0;
negative = false;
}if(i=='-'){
if(hasNum == false) negative = !negative;
else negative = true;
hasNum = false;
sum+=num;
num = 0;
}
}
sum+=num;
return sum;
}
int lastLeft = s.lastIndexOf("(");
int right = s.substring(lastLeft,s.length()).indexOf(")")+lastLeft;
return calculate(s.substring(0,lastLeft)+calculate(s.substring(lastLeft+1,right))+s.substring(right+1));
}
}
栈的方法:
class Solution {
public int calculate(String s) {
Deque<Integer> signs = new ArrayDeque<>();
int num = 0;
int res = 0;
int sign = 1;
signs.push(sign);
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
} else if (c == '(') {
signs.push(sign);
} else if (c == ')') {
signs.pop();
} else if (c == '+' || c == '-') {
res += sign * num;
num = 0;
sign = signs.peek() * (c == '+' ? 1 : -1);
}
}
return res + sign * num;
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode224-%e5%9f%ba%e6%9c%ac%e8%ae%a1%e7%ae%97%e5%99%a8/