image.png
这道题目的难度比我想象中的要高：
自己的做题思路：
op记录算子，-1表示最新的符号是减号，1表示最新的是加号。
遇到‘+’ 或者‘-’ 更新op.
遇到数字，循环读入，一直到字符不为‘0’~‘9’
res+=opres1,其中的res1是刚刚循环读入的数字。
遇到‘（’ ，我是用的递归的方法，将对应的‘）’ 数出来，再将里面的字符串扔到函数里，返回的值=op*res。
class Solution {
public int calculate(String s) {
if(s.length()==1) return s.charAt(0)-'0';
int op=1;
int res=0;
int flag=0;
int num=0;
for(int i=0;i<s.length();i++){
char temp =s.charAt(i);
if(temp>='0'&&temp<='9'){
int res1=0;
while(temp>='0'&&temp<='9'){
res1=res1*10+(temp-'0');
i++;
if(i==s.length()) break;
temp=s.charAt(i);
}
i--;
res+=op*res1;
continue;
}
else if (temp==' ') continue;
else if(temp=='+') op=1;
else if(temp=='-') op=-1;
if(temp=='('){
num=0;
int slow =i;
while(true) {
temp=s.charAt(i);
i++;
if(temp=='(') num++;
if(temp==')') num--;
if(num==0&&temp==')')break;
}
i--;
int fast =i;
res+=op*calculate(s.substring(slow+1,fast));
}
}
return res;
}
}
可是时间复杂度何空间复杂度都不是令人满意。
我看了下别人的写法：
class Solution {
public int calculate(String s) {
Stack<Integer> stack = new Stack<Integer>();
// sign 代表正负
int sign = 1, res = 0;
int length = s.length();
for (int i = 0; i < length; i++) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) {
int cur = ch - '0';
while (i + 1 < length && Character.isDigit(s.charAt(i + 1)))
cur = cur * 10 + s.charAt(++i) - '0';
res = res + sign * cur;
} else if (ch == '+') {
sign = 1;
} else if (ch == '-') {
sign = -1;
} else if (ch == '(') {
stack.push(res);
res = 0;
stack.push(sign);
sign = 1;
} else if (ch == ')') {
res = stack.pop() * res + stack.pop();
}
}
return res;
}
}
优点：
用了Character.isDigit(ch)的方法判断是否为数字，而我用的是 character-‘0’；
用了栈来记录之前的数字和sign，遇到‘）’直接弹出，这里节省了许多空间和时间，还避免了多次遍历。
