题解 | #正则表达式匹配#递归+栈
表达式求值
http://www.nowcoder.com/practice/c215ba61c8b1443b996351df929dc4d4
用递归结合没有括号的做法
public int solve(String s) {
if (s == null || s.length() == 0) return 0;
return calc(s.toCharArray(), 0)[0];
}
//计算idx到)或者结尾的表达式的值，返回值中0:表达式的值，1:接着从哪个下标开始
public int[] calc(char[] strs, int idx) {
Stack<Integer> stack = new Stack<>();
//每次处理一对值，+3，-2，这样一对一对的处理，保证栈里只有值，而且之后栈中的值只做加法，妙啊
int N = strs.length;
int i = idx;
int num = 0;
char preSign = '+';
//考虑(1+2)，以)结尾这种情况怎么处理？
//考虑1+5,这最后一个数怎么收集？
//将处理一对的逻辑抽离成方法，这个方法由出现新运算符和结尾进行触发
for (; i < N && strs[i] != ')'; i++) {
if (Character.isDigit(strs[i])) {
num = num * 10 + (strs[i] - '0');
} else if (strs[i] == '(') {
//一对一对，处理，所以，碰到下一个非数字的时候处理前一对，此时num是第二个运算数
//就算是+3这种情况，也就是此时第一个+进行结算的时候其实前面没有数的，将num=0压入也不会影响结果
//这相当于如果表达式开头是运算符，那么就给它添个0，比如-3+5-->0-3+5，结果依然正确
int[] inRes = calc(strs, i + 1);
i = inRes[1];
num = inRes[0];
} else {
resolvePair(stack, preSign, num);
num = 0;
preSign = strs[i];
}
}
resolvePair(stack, preSign, num);//收集最后一个数
int res = 0;
while (!stack.isEmpty()) {//栈中剩下都是做加法了
res += stack.pop();
}
return new int[]{res, i};
}
public void resolvePair(Stack<Integer> stack, char preSign, int num) {
switch (preSign) {
case '+':
stack.push(num);
break;
case '-':
stack.push(-num);
break;
default:
stack.push(stack.pop() * num);
}
}
