# Basic Calculator
**Difficulty:** HARD
[External](https://leetcode.com/problems/basic-calculator)
Canonical: https://scaleengineer.com/dsa/problems/basic-calculator
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
**Data structures:** String, Stack
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [DoorDash](https://scaleengineer.com/companies/doordash), [Oracle](https://scaleengineer.com/companies/oracle), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [Snowflake](https://scaleengineer.com/companies/snowflake), [Coupang](https://scaleengineer.com/companies/coupang), [Tesla](https://scaleengineer.com/companies/tesla), [Citadel](https://scaleengineer.com/companies/citadel), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Anduril](https://scaleengineer.com/companies/anduril), [Ripple](https://scaleengineer.com/companies/ripple), [Rokt](https://scaleengineer.com/companies/rokt)
---
## Problem
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 (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.

# Approaches
## Stack-based Approach with Two Stacks
We can solve this problem using two stacks - one for numbers and one for operators. We process the expression character by character and handle parentheses by evaluating sub-expressions.
**Time:** O(n) where n is the length of the input string. We process each character once. · **Space:** O(n) where n is the length of the input string. In worst case, we might need to store all numbers and operators in the stacks.
**Pros:** Easy to understand and implement; Can handle nested parentheses; Straightforward approach for basic calculator operations
**Cons:** Uses extra space for two stacks; Requires multiple stack operations; Not as efficient as single pass solutions
### Explanation
This approach uses two stacks to evaluate the expression:
1. First, we initialize two stacks - nums for numbers and ops for operators
2. We iterate through each character in the string:
   - Skip spaces
   - If we find a digit, parse the complete number
   - If we find an opening parenthesis '(', push it to ops stack
   - If we find a closing parenthesis ')', evaluate everything until matching '('
   - If we find an operator (+/-), evaluate all higher or equal precedence operations before pushing

Here's the implementation:

```java
public int calculate(String s) {
    Stack<Integer> nums = new Stack<>();
    Stack<Character> ops = new Stack<>();
    
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == ' ') continue;
        
        if (Character.isDigit(c)) {
            int num = c - '0';
            while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
                num = num * 10 + (s.charAt(i + 1) - '0');
                i++;
            }
            nums.push(num);
        } else if (c == '(') {
            ops.push(c);
        } else if (c == ')') {
            while (!ops.isEmpty() && ops.peek() != '(') {
                nums.push(applyOp(ops.pop(), nums.pop(), nums.pop()));
            }
            ops.pop(); // Remove '('
        } else if (c == '+' || c == '-') {
            while (!ops.isEmpty() && ops.peek() != '(') {
                nums.push(applyOp(ops.pop(), nums.pop(), nums.pop()));
            }
            ops.push(c);
        }
    }
    
    while (!ops.isEmpty()) {
        nums.push(applyOp(ops.pop(), nums.pop(), nums.pop()));
    }
    
    return nums.pop();
}

private int applyOp(char op, int b, int a) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        default: return 0;
    }
}
```
### Algorithm
1. Initialize two stacks: nums for numbers and ops for operators
2. Iterate through each character in the string:
   - Skip spaces
   - Parse complete numbers when digits are found
   - Handle opening parenthesis by pushing to ops stack
   - Handle closing parenthesis by evaluating sub-expression
   - Handle operators by evaluating previous operations
3. Process remaining operations in the stack
4. Return final result

## Single Stack with Sign Tracking
We can optimize the solution by using a single stack and keeping track of signs. This approach is more efficient as it reduces the space complexity and number of operations.
**Time:** O(n) where n is the length of the input string. We process each character exactly once. · **Space:** O(k) where k is the maximum depth of parentheses in the expression.
**Pros:** More efficient than two-stack approach; Uses less memory; Handles parentheses elegantly; Single pass through the input
**Cons:** Slightly more complex logic; Still requires a stack for parentheses handling; Needs careful handling of edge cases
### Explanation
This approach uses a single stack and tracks the current sign:
1. We use a stack to store intermediate results
2. We maintain a currentNumber and sign variable
3. When we encounter operators or parentheses, we process accordingly
4. For parentheses, we push the current result and sign onto stack

Here's the implementation:

```java
public int calculate(String s) {
    Stack<Integer> stack = new Stack<>();
    int result = 0;
    int number = 0;
    int sign = 1;
    
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        
        if (Character.isDigit(c)) {
            number = number * 10 + (c - '0');
        } else if (c == '+') {
            result += sign * number;
            number = 0;
            sign = 1;
        } else if (c == '-') {
            result += sign * number;
            number = 0;
            sign = -1;
        } else if (c == '(') {
            stack.push(result);
            stack.push(sign);
            result = 0;
            sign = 1;
        } else if (c == ')') {
            result += sign * number;
            number = 0;
            result *= stack.pop();    // sign
            result += stack.pop();    // previous result
        }
    }
    
    if (number != 0) {
        result += sign * number;
    }
    
    return result;
}
```
### Algorithm
1. Initialize variables for result, current number, and sign
2. Iterate through each character:
   - Build number for consecutive digits
   - Process operators by updating result and sign
   - For opening parenthesis, push current result and sign
   - For closing parenthesis, evaluate sub-expression
3. Handle final number if exists
4. Return final result

# Solutions
### CSharp

```csharp
public class Solution {
    public int Calculate(string s) {
        var stk = new Stack < int > ();
        int sign = 1;
        int n = s.Length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == ' ') {
                continue;
            }
            if (s[i] == '+') {
                sign = 1;
            } else if (s[i] == '-') {
                sign = -1;
            } else if (s[i] == '(') {
                stk.Push(ans);
                stk.Push(sign);
                ans = 0;
                sign = 1;
            } else if (s[i] == ')') {
                ans *= stk.Pop();
                ans += stk.Pop();
            } else {
                int num = 0;
                while (i < n && char.IsDigit(s[i])) {
                    num = num * 10 + s[i] - '0';
                    ++i;
                }--i;
                ans += sign * num;
            }
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  int calculate(String s) {
    Deque<Integer> stk = new ArrayDeque<>();
    int sign = 1;
    int ans = 0;
    int n = s.length();
    for (int i = 0; i < n; ++i) {
      char c = s.charAt(i);
      if (Character.isDigit(c)) {
        int j = i;
        int x = 0;
        while (j < n && Character.isDigit(s.charAt(j))) {
          x = x * 10 + s.charAt(j) - '0';
          j++;
        }
        ans += sign * x;
        i = j - 1;
      } else if (c == '+') {
        sign = 1;
      } else if (c == '-') {
        sign = -1;
      } else if (c == '(') {
        stk.push(ans);
        stk.push(sign);
        ans = 0;
        sign = 1;
      } else if (c == ')') {
        ans = stk.pop() * ans + stk.pop();
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int calculate(string s) {
    stack<int> stk;
    int ans = 0, sign = 1;
    int n = s.size();
    for (int i = 0; i < n; ++i) {
      if (isdigit(s[i])) {
        int x = 0;
        int j = i;
        while (j < n && isdigit(s[j])) {
          x = x * 10 + (s[j] - '0');
          ++j;
        }
        ans += sign * x;
        i = j - 1;
      } else if (s[i] == '+') {
        sign = 1;
      } else if (s[i] == '-') {
        sign = -1;
      } else if (s[i] == '(') {
        stk.push(ans);
        stk.push(sign);
        ans = 0;
        sign = 1;
      } else if (s[i] == ')') {
        ans *= stk.top();
        stk.pop();
        ans += stk.top();
        stk.pop();
      }
    }
    return ans;
  }
};

```

### Python

```python
# only + and - , no * , no / class Solution : def calculate ( self , s : str ) -> int : stk = [] ans , sign = 0 , 1 i , n = 0 , len ( s ) while i < n : if s [ i ]. isdigit (): x = 0 j = i # with this while, no need to do final calculation like below solution while j < n and s [ j ]. isdigit (): x = x * 10 + int ( s [ j ]) j += 1 ans += sign * x i = j - 1 elif s [ i ] == "+" : sign = 1 elif s [ i ] == "-" : sign = - 1 elif s [ i ] == "(" : stk . append ( ans ) stk . append ( sign ) ans , sign = 0 , 1 elif s [ i ] == ")" : ans = stk . pop () * ans + stk . pop () i += 1 return ans ############# class Solution : def calculate ( self , s : str ) -> int : ans = 0 num = 0 sign = 1 stack = [ sign ] # stack[-1]: current env's sign for c in s : if c . isdigit (): num = num * 10 + int ( c ) # num = num * 10 + (ord(c) - ord('0')) => also works elif c == '(' : stack . append ( sign ) elif c == ')' : stack . pop () # pop pairing sign for this () pair elif c == '+' or c == '-' : ans += sign * num sign = ( 1 if c == '+' else - 1 ) * stack [ - 1 ] # after all + or -, the sign for current num num = 0 return ans + sign * num # final calculation
```