Tuesday, October 4, 2016

Basic calculator II

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.

The idea is similar to the first one. However, here we don't have to consider parentheses but we need to consider the priority of operations, i.e., * and / are prior to + and -. We still use a stack, but this time to store numbers. Every time we see + or -, we push the number (or its negative) to the stack. Every time we see * or /, we pop one number and do operations and push the result back in. Note we always operate on the previous operator we see and then update current sign to our sign tracker, thus we can get both numbers for operations. For the last number we see, we also need to do operations and push back to stack.

public int calculate(String s) {
        int len = s.length();
        if (len == 0) {
            return 0;
        }
        Stack numbers = new Stack<>();
        char sign = '+';
        int rst = 0;
        int curr = 0;
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                curr = curr * 10  + c - '0';
            }
            if ("+-*/".indexOf(c) >= 0 || i == len - 1) {
                if (sign == '+') {
                    numbers.push(curr);
                } else if (sign == '-') {
                    numbers.push(-curr);
                } else if (sign == '*' || sign == '/'){
                    int last = numbers.pop();
                    numbers.push(sign == '*' ? last * curr : last / curr);
                }
                sign = c;
                curr = 0;
            }
        }
        while (!numbers.isEmpty()) {
            rst += numbers.pop();
        }
        return rst;
    }


No comments:

Post a Comment