224. Basic Calculator

Question

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 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 (i.e., "+1" and "+(2 + 3)" is invalid).
• '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
• There will be no two consecutive operators in the input.
• Every number and running calculation will fit in a signed 32-bit integer.

Algorithm

This question is pretty hard for me. I've tried some thoughts and failed due to handling the () especially multiple like(()). The point here is to solve this problem, how to handle the () layer and the calculating sequence with inner and outer results.

So according to standard solutions provided by the official Leetcode, they have two ways to solve the question. The first one is you reverse whole string and do the calculation by pop and push elements. (I think this is a little bit trick, or at least it cannot be found in a short period of time). So I turned to the second method:

1. Iterate the expression one character at a time
2. Concatenate the numbers in reverse order. if the character read is a digit we need to form the operand by multiplying 10 to the previously formed
3. Whenever there is + or -, we change the sign for next evaluation
4. If the char is (. We push the result we accumulated for far and the sign on to the stack. This symbol means we need to start new layer calculation
5. If we meet ), this mean current level or layer calculation is finished. We first calculate the expression to the left. Then we pop the sign and pre layer result and calculate withe current value to reduce a layer. (This sign is associated with the parenthesis that started then, thus when the expression ends or concludes, we pop the sign and multiply it with result of the expression. It is then just added to the next element on top of the stack.)

Code

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack();
        int operand = 0;
        int res = 0;
        int sign = 1;
        
        for (int i = 0; i < s.length(); i++) {
            Character ch = s.charAt(i);
            if (Character.isDigit(ch)) {
                operand = 10 * operand + (int)(ch - '0');
            } else if (ch == '+') {
                res += sign * operand;
                sign = 1;
                operand = 0;
            } else if (ch == '-') {
                res += sign * operand;
                sign = -1;
                operand = 0;
            } else if (ch == '(') {
                stack.push(res);
                stack.push(sign);
                res = 0;
                sign = 1;
            } else if (ch ==')') {
                res += sign * operand;
                res *= stack.pop();
                res += stack.pop();
                operand = 0;
                sign = 1;
            }
        }
        return res + (operand * sign);
    }
}