0224. Basic Calculator

https://leetcode.com/problems/basic-calculator

Description

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

**Input:** s = "1 + 1"
**Output:** 2

Example 2:

**Input:** s = " 2-1 + 2 "
**Output:** 3

Example 3:

**Input:** s = "(1+(4+5+2)-3)+(6+8)"
**Output:** 23

Constraints:

• 1 <= s.length <= 3 * 105

• s consists of digits, '+', '-', '(', ')', and ' '.

• s represents a valid expression.

• '+' is not used as a unary operation.

• '-' could be used as a unary operation and in this case, it will not be used directly after a +ve or -ve signs (will be inside parentheses).

• There will be no two consecutive operators in the input.

• Every number and running calculation will fit in a signed 32-bit integer.

ac1： Deque + multiple passes

slow

class Solution {
    public int calculate(String s) {
        Deque<String> deque = new ArrayDeque<String>();

        // 1st pass, parentheses
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ' ') continue;
            if (c == '(' || c == '+' || c == '-') {
                if (sb.length() > 0) deque.offer(sb.toString());
                sb.setLength(0);
                deque.offer(String.valueOf(c));
            } else if (c == ')'){
                if (sb.length() > 0) deque.offer(sb.toString());
                sb.setLength(0);

                Deque<String> sub = new ArrayDeque<String>();
                while(!deque.peekLast().equals("(")) {
                    sub.offerFirst(deque.pollLast());
                }
                deque.pollLast();
                deque.offer(calDeque(sub));
            } else {
                sb.append(c);
            }
        }
        if (sb.length() > 0) deque.offer(sb.toString());

        // 2nd pass, get result
        return Integer.parseInt(calDeque(deque));
    }

    private String calDeque(Deque<String> d) {
        int val = Integer.parseInt(d.poll());
        while (!d.isEmpty()) {
            String operator = d.poll();
            int operand = Integer.parseInt(d.poll());
            if (operator.equals("+")) {
                val += operand;
            } else if (operator.equals("-")) {
                val -= operand;
            }
        }
        return "" + val;
    }
}
/**
Deque, 1st pass, handle parentheses
2nd pass, calculate
**/

ac2: stack

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        int res = 0;
        int num = 0;
        int sign = 1;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (int) (c - '0');
            } else if (c == '+') {
                res += sign * num;
                num = 0;
                sign = 1;
            } else if (c == '-') {
                res += sign * num;
                num = 0;
                sign = -1;
            } else if (c == '(') {
                stack.push(res);
                stack.push(sign);
                res = 0;
                sign = 1;
            } else if (c == ')') {
                res += sign * num;
                res = stack.pop() * res + stack.pop();
                num = 0;
                sign = 1;
            }
        }

        if (num != 0) res += sign * num;

        return res;
    }

}

ac3: 2 stack

more intuitive, generalize to complex problem like #227 #772

class Solution {
    public int calculate(String s) {
        Stack<Integer> nums = new Stack<>();
        Stack<Character> ops = new Stack<>();
        nums.push(0);
        ops.push('+');

        int n = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ' ') continue;

            if (Character.isDigit(c)) {
                n = n * 10 + c - '0';
            } else if (c == '(') {
                ops.push(c);
            } else if (c == '+' || c == '-') {
                if (ops.peek() != '(') {
                    n = operate(nums.pop(), ops.pop(), n);
                }
                nums.push(n);
                ops.push(c);
                n = 0;
            } else if (c == ')') {
                while (ops.peek() != '(') n = operate(nums.pop(), ops.pop(), n);
                ops.pop();
            }
        }

        while (!ops.isEmpty()) n = operate(nums.pop(), ops.pop(), n);

        return n;
    }

    private int operate(int val1, Character oper, int val2) {
        if (oper == '+') return val1 + val2;
        else return val1 - val2;
    }
}

ac4: stack, get rid of parenthesis

sign = stack.peek() * (c == '+' ? 1: -1); is to simulate the process of removing parenthesis.

class Solution {
    public int calculate(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        int prevVal = 0, currNum = 0;
        int sign = 1; // 1 for +, -1 for -.
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ' ') continue;
            if (Character.isDigit(c)) {
                currNum = currNum * 10 + (c - '0');
            } else if (c == '+' || c == '-') {
                prevVal += sign * currNum;
                // Reset
                sign = c == '+' ? 1 : -1;
                currNum = 0;
            } else if (c == '(') {
                // Store the sate: 
                stack.push(prevVal);
                stack.push(sign);
                // Reset
                prevVal = 0;
                sign = 1;
            } else if (c == ')') {
                currNum = prevVal + sign * currNum;
                // Retrieve what we stored
                sign = stack.pop();
                prevVal = stack.pop();
            }
        }
        
        return prevVal + sign * currNum;
    }
}
/* 
O(N) time, O(N) space
num1, op1, num2, {op2} ...
When we meet op2, update num1 = eval(num1, op1, num2). 
We keep state in (num1, op1), so push them to stack when meet new parenthesis. 
*/