image.png
這道題目的難度比我想象中的要高：
自己的做題思路：
op記錄算子溺欧，-1表示最新的符號是減號朗兵，1表示最新的是加號寄猩。
遇到‘+’ 或者‘-’ 更新op.
遇到數(shù)字找岖，循環(huán)讀入陨倡，一直到字符不為‘0’~‘9’
res+=opres1,其中的res1是剛剛循環(huán)讀入的數(shù)字。
遇到‘（’ 许布，我是用的遞歸的方法兴革，將對應的‘）’ 數(shù)出來，再將里面的字符串扔到函數(shù)里蜜唾，返回的值=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;
}
}
優(yōu)點：
用了Character.isDigit(ch)的方法判斷是否為數(shù)字灵妨，而我用的是 character-‘0’解阅；
用了棧來記錄之前的數(shù)字和sign，遇到‘）’直接彈出泌霍，這里節(jié)省了許多空間和時間货抄，還避免了多次遍歷述召。
