Basic Calculator

LeetCode 224 | Difficulty: Hard

Hard

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.

Topics: Math, String, Stack, Recursion

---

Approach

Stack

Use a stack (LIFO) to track elements that need future processing. Process elements when a "trigger" condition is met (e.g., finding a smaller/larger element). Monotonic stack maintains elements in sorted order for next greater/smaller element problems.

When to use

Matching brackets, next greater element, evaluating expressions, backtracking history.

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 83 ms)

Metric	Value
Runtime	83 ms
Memory	36.9 MB
Date	2022-01-24

Solution

public class Solution {
    public int Calculate(string s) {
        Stack<int> st = new Stack<int>();
    int result = 0, sign = 1, current = 0;
    for (int i = 0; i < s.Length; i++)
    {
        char c = s[i];
        if(char.IsDigit(c))
        current = current*10 + (c-'0');
        else if(c == '+')
        {
            result += sign*current;
            current=0;
            sign=1;
        }
        else if(c == '-')
        {
            result += sign*current;
            current=0;
            sign = -1;
        }
        else if(c == '(')
        {
            st.Push(result);
            st.Push(sign);
            sign=1;
            result = 0;
        }
        else if(c== ')')
        {
            result += sign*current;
            current = 0;
            result = st.Pop() * result;
            result = st.Pop() + result;
        }
    }
    if(current != 0) result += sign*current;
    return result;
    }
}

📜 1 more C# submission(s)

Submission (2022-01-24) — 134 ms, 36.9 MB

public class Solution {
    public int Calculate(string s) {
        if(string.IsNullOrEmpty(s))
    return 0;
    
    int result = 0, sign = 1, num = 0;
    Stack<int> st = new Stack<int>();
    st.Push(sign);
    for (int i = 0; i < s.Length; i++)
    {
        char c = s[i];
        if(char.IsDigit(c))
        {
            num = num * 10 + (c-'0');
        }
        else if(c == '+' || c == '-')
        {
            result += sign * num;
            sign = st.Peek() * (c== '+' ? 1 : -1);
            num = 0;
        }
        else if(c == '(')
        {
            st.Push(sign);
        }
        else if(c== ')')
        {
            st.Pop();
        }
    }
    result += sign * num;
    return result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Stack	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Think about what triggers a pop: is it finding a match, or finding a smaller/larger element?