Question:

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

Thinking:

An efficient way to solve this problem is to use stack get last num for an operation. And in order to delay the operation after get the two numbers, we need a op variable to record the last op until find the second number. What’s more, accroding to their op, numbers push into the stack in different ways. Finnaly, we just need to get the element from stack and add them all.

Solution:

public int calculate(String s) {
    Stack<Long> stack = new Stack<Long>();

    int i = 0;
    char op = '+';
    long num = 0;

    while (i < s.length()) {
        if (Character.isDigit(s.charAt(i))) {
            while (i < s.length() && Character.isDigit(s.charAt(i)))
                num = num * 10 + s.charAt(i++) - '0';
        }
        else if (s.charAt(i) == ' ')
            i++;
        else {
            if (op == '+')
                stack.push(num);
            else if (op == '-')
                stack.push(-num);
            else if (op == '*')
                stack.push(stack.pop() * num);
            else if (op == '/')
                stack.push(stack.pop() / num);
            num = 0;
            op = s.charAt(i++);
        }
    }

    if (op == '+')
        stack.push(num);
    else if (op == '-')
        stack.push(-num);
    else if (op == '*')
        stack.push(stack.pop() * num);
    else if (op == '/')
        stack.push(stack.pop() / num);

    int res = 0;
    for (Long n: stack)
        res += n;

    return res;
}