227. Basic Calculator II

{2ND TRY}
Version #2 Iterative 1 pass
I don't know why do we need a stack...
Just iterate straightforwardly

93.93 %
class Solution {
    public int calculate(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int i = 0;
char curr;
int num = 0;
int prev = 0;
int result = 0;
char op = '+';
while (i < s.length()) {
curr = s.charAt(i);
if (Character.isDigit(curr)) {
num = curr - '0';
while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
num = num * 10 + (s.charAt(i + 1) - '0');
i++;
}
if (op == '+') {
result += num;
prev = num;
} else if (op == '-') {
result -= num;
prev = -num;
} else if (op == '/') {
result = result - prev + prev / num;
prev = prev / num;
} else if (op == '*') {
result = result - prev + prev * num;
prev = prev * num;
}
} else if (curr == '+' || curr == '-' || curr == '*' || curr == '/') {
op = curr;
}
i++;
}
return result;
}
}


{1ST TRY}
Version #1 Stack
这类问题的大体思路是把优先级不高的push进stack里面
优先级高的立刻计算

要时刻记住sign的意思是上一次看到的sign
每次当前看到的sign会触发上一次sign的运算

最后一个数字是一个edge case一般需要单独处理

还有对于非sign非digit的处理，可以直接continue


63.27 %

class Solution {
    // "3+2*2" = 7
    // " 3/2 " = 1
    // " 3+5 / 2 " = 5
    public int calculate(String s) {
        if (s == null) return 0;
        char[] chars = s.trim().toCharArray();
        int num = 0;
        char sign = '+';
        Stack<Integer> stack =  new Stack<>();
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            if (c == ' ') continue;
            if (Character.isDigit(c)) {
                num = num * 10 + Character.getNumericValue(c);
            }
            if (!Character.isDigit(c) || i == chars.length - 1) {
                // sign is the previous sign
                switch (sign) {
                    case '*':
                        num = stack.pop() * num;
                        stack.push(num);
                        break;
                    case '/':
                        num = stack.pop() / num;
                        stack.push(num);
                        break;
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-1 * num);
                        break;
                    default:
                        continue;
                }
                num = 0;
                sign = c;
            }
        }
        int result = 0;
     
        while (!stack.isEmpty()) {
            result += stack.pop();
        }
        return result;
    }
}