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;
}
}
代碼寫得略微長(zhǎng)了一點(diǎn)弄屡，但是整體邏輯應(yīng)該還是很清楚的好唯。
一開始做錯(cuò)了，從左往右掃描筒主，思路是：
如果碰到 (, +, - , 那么就 壓入棧关噪。
如果碰到數(shù)字，那么掃描完后乌妙，壓入棧
如果碰到 ), 那么就不斷pop棧使兔，拿出來(lái)值進(jìn)行計(jì)算。直到碰到藤韵， (
那就停止虐沥。將 ( 彈出。然后荠察，壓入 算出來(lái)的 總值置蜀。
導(dǎo)致的一個(gè)問(wèn)題是奈搜，
5 - 3 + 2
我會(huì) 先 3 + 2 = 5
然后 5 - 5 = 0
result = 0
我無(wú)法辨別這種情況悉盆。
所以后來(lái)改成了從右往左掃描，這種問(wèn)題就不會(huì)出現(xiàn)了馋吗。
然后所有的邏輯都顛倒一下焕盟，就好了。
看了下 Discuss ，最好的一個(gè)做法脚翘，是將 sign 位也插入棧中灼卢，這樣也可以處理那個(gè)問(wèn)題。
reference:
https://discuss.leetcode.com/topic/33044/java-easy-version-to-understand
Anyway, Good luck, Richardo! -- 08/25/2016
根據(jù) Basic Calculator II,
發(fā)現(xiàn)了一種更加直接的方法：
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 里面是保存這個(gè)數(shù)字的前一個(gè)運(yùn)算符来农。
I 里面是保存兩個(gè)東西：
1 . 括號(hào)內(nèi)部的 符號(hào)鞋真， +/-, 這些只用暫存，然后將括號(hào)內(nèi)算式的答案一下子算出來(lái)沃于。
2 . 括號(hào)外部的符號(hào)涩咖， +/-, 這些，不能被立刻使用繁莹，因?yàn)楹竺娓芏嗬ㄌ?hào)檩互，那么這個(gè)符號(hào)會(huì)被括號(hào)里面的符號(hào)覆蓋。所以先把他放入棧中暫存咨演。之后再?gòu)棾鰜?lái)闸昨。
差不多就這么個(gè)思想。
Anyway, Good luck, Richardo! -- 09/17/2016
