LeetCodee

224. Basic Calculator

Jump to Solution: Python Java C++ JavaScript C#

Problem 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 * 10^5
  • 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.

Solution

Python Solution

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        num = 0
        sign = 1
        result = 0
        
        for char in s:
            if char.isdigit():
                num = num * 10 + int(char)
            elif char in ['+', '-']:
                result += sign * num
                num = 0
                sign = 1 if char == '+' else -1
            elif char == '(':
                stack.append(result)
                stack.append(sign)
                result = 0
                sign = 1
            elif char == ')':
                result += sign * num
                num = 0
                result *= stack.pop()  # sign
                result += stack.pop()  # previous result
                
        return result + sign * num

Time Complexity: O(n)

We iterate through the string once, where n is the length of the input string.

Space Complexity: O(n)

The stack can grow up to O(n) in the worst case with nested parentheses.

Java Solution

class Solution {
    public int calculate(String s) {
        Stack stack = new Stack<>();
        int num = 0;
        int sign = 1;
        int result = 0;
        
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+' || c == '-') {
                result += sign * num;
                num = 0;
                sign = c == '+' ? 1 : -1;
            } else if (c == '(') {
                stack.push(result);
                stack.push(sign);
                result = 0;
                sign = 1;
            } else if (c == ')') {
                result += sign * num;
                num = 0;
                result *= stack.pop();  // sign
                result += stack.pop();  // previous result
            }
        }
        
        return result + sign * num;
    }
}

Time Complexity: O(n)

We iterate through the string once, where n is the length of the input string.

Space Complexity: O(n)

The stack can grow up to O(n) in the worst case with nested parentheses.

C++ Solution

class Solution {
public:
    int calculate(string s) {
        stack stk;
        int num = 0;
        int sign = 1;
        int result = 0;
        
        for (char c : s) {
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+' || c == '-') {
                result += sign * num;
                num = 0;
                sign = (c == '+') ? 1 : -1;
            } else if (c == '(') {
                stk.push(result);
                stk.push(sign);
                result = 0;
                sign = 1;
            } else if (c == ')') {
                result += sign * num;
                num = 0;
                result *= stk.top(); stk.pop();  // sign
                result += stk.top(); stk.pop();  // previous result
            }
        }
        
        return result + sign * num;
    }
};

Time Complexity: O(n)

We iterate through the string once, where n is the length of the input string.

Space Complexity: O(n)

The stack can grow up to O(n) in the worst case with nested parentheses.

JavaScript Solution

/**
 * @param {string} s
 * @return {number}
 */
var calculate = function(s) {
    const stack = [];
    let num = 0;
    let sign = 1;
    let result = 0;
    
    for (let char of s) {
        if (char >= '0' && char <= '9') {
            num = num * 10 + parseInt(char);
        } else if (char === '+' || char === '-') {
            result += sign * num;
            num = 0;
            sign = char === '+' ? 1 : -1;
        } else if (char === '(') {
            stack.push(result);
            stack.push(sign);
            result = 0;
            sign = 1;
        } else if (char === ')') {
            result += sign * num;
            num = 0;
            result *= stack.pop();  // sign
            result += stack.pop();  // previous result
        }
    }
    
    return result + sign * num;
};

Time Complexity: O(n)

We iterate through the string once, where n is the length of the input string.

Space Complexity: O(n)

The stack can grow up to O(n) in the worst case with nested parentheses.

C# Solution

public class Solution {
    public int Calculate(string s) {
        Stack stack = new Stack();
        int num = 0;
        int sign = 1;
        int result = 0;
        
        foreach (char c in s) {
            if (char.IsDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+' || c == '-') {
                result += sign * num;
                num = 0;
                sign = c == '+' ? 1 : -1;
            } else if (c == '(') {
                stack.Push(result);
                stack.Push(sign);
                result = 0;
                sign = 1;
            } else if (c == ')') {
                result += sign * num;
                num = 0;
                result *= stack.Pop();  // sign
                result += stack.Pop();  // previous result
            }
        }
        
        return result + sign * num;
    }
}

Time Complexity: O(n)

We iterate through the string once, where n is the length of the input string.

Space Complexity: O(n)

The stack can grow up to O(n) in the worst case with nested parentheses.

Approach Explanation

The solution uses a stack-based approach to handle parentheses and evaluate the expression. Here's how it works:

  1. We maintain four variables:
    • result: stores the ongoing result
    • num: builds the current number
    • sign: keeps track of whether to add or subtract
    • stack: stores previous results and signs for nested expressions
  2. For each character in the string:
    • If it's a digit, build the number
    • If it's '+' or '-', update result and reset num
    • If it's '(', save current state and start fresh
    • If it's ')', evaluate current expression and restore previous state
  3. Finally, add the last number with its sign to the result

The key insight is using the stack to maintain state when evaluating nested expressions within parentheses. This allows us to correctly handle expressions of any depth while keeping track of the signs and previous results.