Two Java solutions O(n) or O(1) space


  • 0
    Y

    This problem is a classic use case for stack. And the implementation is very straightforward. You save the number along the way, yet when you see a sign, save the prev number in stack. If the sign is * or /, you want to pop the last element in stack and push in the result after calculation. In the end, just iterate the stack and sum it all up for the final result. Yet this uses O(n) space and we can do better if you carefully save the intermediate result.

    A small trick is used here. I used a sentinel value 0, it can be anything other than a digit or operators to make sure the last number is calculated. Of course, if you want to calculate at the end, it is also ok.

    public int calculate(String s) {
        int n;
        if(s == null || (n = s.length()) == 0) {
            return 0;
        }
        int num = 0;
        Stack<Integer> stack = new Stack<>();
        char sign = '+';
        for(int i = 0; i <= n; i++) {
            char c = i == n ? 0 : s.charAt(i);
            if(Character.isDigit(c)) {
                num = num * 10 + c - '0';
            }
            if(!Character.isDigit(c) && c != ' ') {
                if(sign == '+') {
                    stack.push(num);
                } else if(sign == '-') {
                    stack.push(-num);
                } else if(sign == '*') {
                    stack.push(stack.pop() * num);
                } else if(sign == '/') {
                    stack.push(stack.pop() / num);
                }
                num = 0;
                sign = c;
            }
        }
        int res = 0;
        for(int i : stack) {
            res += i;
        }
        return res;
    }
    

    The second solution is constant space and no stack used. The idea is still straight-forward, yet a few things to pay attention to during implementation:
    First, prev is saving the result so far, and the default calculation is prev = opt == '*' ? prev * num : prev / num; to make sure the '*' or '/' operation is carried out. And since prev is set to 1 every time prev is saved in the result, even if there is no * operation, the result is not affected.
    Second, the prev is only saved in the result when we see the next '+' or '-'.

    public int calculate(String s) {
        int n;
        if(s == null || (n = s.length()) == 0) {
            return 0;
        }
        char sign = '+';
        char opt = '*';
        int res = 0;
        int prev = 1;
        int num = 0;
    
        for(int i = 0; i <= n; i++) {
            char c = i == n ? 0 : s.charAt(i);
            if(c == ' ') {
                continue;
            }
            if(c >= '0' && c <= '9') {
                num = num * 10 + (c - '0');
                continue;
            }
            if(c == 0 || "+-*/".indexOf(c) >= 0) {
                prev = opt == '*' ? prev * num : prev / num;
                num = 0;
                if(c == '+' || c == '-' || c == 0) {
                    res += sign == '+' ? prev : -prev;
                    prev = 1;
                    sign = c;
                    opt = '*';
                } else {
                    opt = c;
                }
            }
        }
        return res;
    }

  • 1
    A

    Thanks for sharing. For the second solution logic in the loop can be simplified a little bit. I wrote it in C#.

    public int Calculate(string s) {
            if (s==null||s.Length==0) { return 0; }
            int pre = 1, num = 0, res = 0, len=s.Length;
            char sign = '+', opt = '*';
            for (int i=0; i<len; i++){
                if (char.IsDigit(s[i])) {
                    num = num*10+s[i]-'0';
                }
                if (i==len-1 || !char.IsDigit(s[i]) && s[i]!=' '){  // +-*/ or last index
                    pre = opt=='*'?pre*num:pre/num;
                    num = 0;
                    if (i==len-1 || s[i]=='+' || s[i]=='-'){  // + - or last
                        res += sign=='+'?pre:-pre;
                        pre = 1;
                        opt = '*';
                        sign = s[i];
                    }
                    else { opt = s[i]; }  // * or /
                }
            }
            return res;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.