My code:
public class Solution {
// assume: -1 means +, -2 means -, -3 means )
public int calculate(String s) {
if (s == null || s.length() == 0) {
return 0;
}
// scan from right to left
Stack<Integer> st = new Stack<Integer>();
int i = s.length() - 1;
while (i >= 0) {
char curr = s.charAt(i);
if (curr == ' ') {
i--;
continue;
}
else if (curr == ')') {
i--;
st.push(-3);
}
else if (curr == '+') {
i--;
st.push(-1);
}
else if (curr == '-') {
i--;
st.push(-2);
}
else if (curr == '(') {
int left = st.pop();
while (st.peek() != -3) {
int op = st.pop();
int right = st.pop();
switch (op) {
case -1:
left = left + right;
break;
case -2:
left = left - right;
break;
default:
break;
}
}
st.pop();
st.push(left);
i--;
}
else {
int[] result = parseInteger(s, i);
st.push(result[0]);
i = result[1];
}
}
int left = st.pop();
while (!st.isEmpty()) {
int op = st.pop();
int right = st.pop();
switch (op) {
case -1:
left = left + right;
break;
case -2:
left = left - right;
break;
default:
break;
}
}
return left;
}
private int[] parseInteger(String s, int end) {
StringBuilder ret = new StringBuilder();
int i = end;
for (; i >= 0; i--) {
char curr = s.charAt(i);
if (curr < '0' || curr > '9') {
break;
}
else {
ret = ret.append(curr);
}
}
int[] result = new int[2];
result[0] = Integer.parseInt(ret.reverse().toString());
result[1] = i;
return result;
}
}
代码写得略微长了一点，但是整体逻辑应该还是很清楚的。
一开始做错了，从左往右扫描，思路是：
如果碰到 (, +, - , 那么就 压入栈。
如果碰到数字，那么扫描完后，压入栈
如果碰到 ), 那么就不断pop栈，拿出来值进行计算。直到碰到， (
那就停止。将 ( 弹出。然后，压入 算出来的 总值。
导致的一个问题是，
5 - 3 + 2
我会 先 3 + 2 = 5
然后 5 - 5 = 0
result = 0
我无法辨别这种情况。
所以后来改成了从右往左扫描，这种问题就不会出现了。
然后所有的逻辑都颠倒一下，就好了。
看了下 Discuss ，最好的一个做法，是将 sign 位也插入栈中，这样也可以处理那个问题。
reference:
https://discuss.leetcode.com/topic/33044/java-easy-version-to-understand
Anyway, Good luck, Richardo! -- 08/25/2016
根据 Basic Calculator II,
发现了一种更加直接的方法：
My code:
public class Solution {
public int calculate(String s) {
if (s == null || s.length() == 0) {
return -1;
}
int sign = 1;
int result = 0;
Stack<Integer> st = new Stack<Integer>();
int i = 0;
while (i < s.length()) {
char curr = s.charAt(i);
if (curr == ' ') {
i++;
continue;
}
else if (Character.isDigit(curr)) {
int temp = 0;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
temp = 10 * temp + (s.charAt(i) - '0');
i++;
}
result += sign * temp;
}
else if (curr == '+') {
i++;
sign = 1;
}
else if (curr == '-') {
i++;
sign = -1;
}
else if (curr == '(') {
i++;
st.push(result);
st.push(sign);
result = 0;
sign = 1;
}
else {
i++;
int temp_sign = st.pop();
result = st.pop() + temp_sign * result;
}
}
return result;
}
}
reference:
https://discuss.leetcode.com/topic/33044/java-easy-version-to-understand
II 里面是保存这个数字的前一个运算符。
I 里面是保存两个东西：
1 . 括号内部的 符号， +/-, 这些只用暂存，然后将括号内算式的答案一下子算出来。
2 . 括号外部的符号， +/-, 这些，不能被立刻使用，因为后面跟着很多括号，那么这个符号会被括号里面的符号覆盖。所以先把他放入栈中暂存。之后再弹出来。
差不多就这么个思想。
Anyway, Good luck, Richardo! -- 09/17/2016
