227. Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string contains onlynon-negativeintegers,+,-,*,/operators and empty spaces. The integer division should truncate toward zero.

Example 1:

Input: 
"3+2*2"

Output: 7

Example 2:

Input: " 3/2 "

Output:1

Example 3:

Input:" 3+5 / 2 "

Output: 5

Note:

• You may assume that the given expression is always valid.

• Do not use the evalbuilt-in library function.

Thoughts: need to look back to know what is the operand value when encountered an operator. Hence need two variable: operator and operand.

1. With stack: using a stack to keep track of numbers and do the operation based on operators.

2. Without stack: only add current operand to the accumulative sum when encountered '+' or '-' since '*' and '/' has prioirty

Code: with a stack

class Solution {
    public int calculate(String s) {
        if(s == null || s.length() ==0) return 0;
        int len = s.length();
        Stack<Integer> stack = new Stack<Integer>();
        int num = 0;
        char sign= '+'; // equivalent to concatenate a '+' in front of s
        for(int i = 0;  i < len ; i++){
            // operand
            if (Character.isDigit(s.charAt(i)))
                num = 10 * num + s.charAt(i) - '0';
            if ((!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ') || i == len - 1){
                if(sign == '-'){
                    stack.push(-num);
                }
                if(sign == '+'){
                    stack.push(num);
                }
                if(sign == '*'){
                     stack.push(stack.pop()*num);
                }
                if(sign == '/'){
                     stack.push(stack.pop()/num);
                }
                sign = s.charAt(i);
                num = 0;
            }
        }

        int ans = 0;
        for (int i: stack) ans += i;
        return ans;
    }
}

Code: without a stack

class Solution {
public:
    int calculate(string s) {
        istringstream in('+' + s + '+');
        long long total = 0, term = 0, n;
        char op;
        while (in >> op) {
            if (op == '+' or op == '-') {
                total += term;
                in >> term;
                term *= op == '+' ? 1 : -1;
            } else {
                in >> n;
                if (op == '*')
                    term *= n;
                else
                    term /= n;
            }
        }
        return total;
    }   
};