Expression Evaluation

Evaluate mathematical expressions with proper operator precedence and parentheses.

Language Selection

Choose your preferred programming language

Showing: Python

Expression Evaluation

Problem Statement

Given a string s representing a valid expression, evaluate this expression and return its value.

The expression may contain parentheses, the plus + or minus sign -, non-negative integers, and empty spaces.

Examples

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^4
s consists of digits, '+', '-', '(', ')', and ' '
s represents a valid expression
All intermediate results will be in the range [-2^31, 2^31 - 1]

Approach 1: Stack-Based Evaluation (Optimal)

Algorithm

Use a stack to handle operator precedence and parentheses.

Steps:

Use a stack to store intermediate results and signs
Process each character:
- If digit: build the number
- If operator: handle operator precedence
- If ‘(’: push current result and sign to stack
- If ‘)’: evaluate until ‘(’
Return the final result

Implementation

Python:

def calculate(s):
    """
    Evaluate expression using stack-based approach
    Time: O(n)
    Space: O(n)
    """
    stack = []
    num = 0
    sign = 1
    result = 0
    
    for char in s:
        if char.isdigit():
            num = num * 10 + int(char)
        elif char == '+':
            result += sign * num
            num = 0
            sign = 1
        elif char == '-':
            result += sign * num
            num = 0
            sign = -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

Java:

class Solution {
    public int calculate(String s) {
        Stack<Integer> 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 == '+') {
                result += sign * num;
                num = 0;
                sign = 1;
            } else if (c == '-') {
                result += sign * num;
                num = 0;
                sign = -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;
    }
}

Go:

func calculate(s string) int {
    stack := make([]int, 0)
    num := 0
    sign := 1
    result := 0
    
    for _, char := range s {
        if char >= '0' && char <= '9' {
            num = num*10 + int(char-'0')
        } else if char == '+' {
            result += sign * num
            num = 0
            sign = 1
        } else if char == '-' {
            result += sign * num
            num = 0
            sign = -1
        } else if char == '(' {
            stack = append(stack, result)
            stack = append(stack, sign)
            result = 0
            sign = 1
        } else if char == ')' {
            result += sign * num
            num = 0
            result *= stack[len(stack)-1] // sign
            stack = stack[:len(stack)-1]
            result += stack[len(stack)-1] // previous result
            stack = stack[:len(stack)-1]
        }
    }
    
    return result + sign*num
}

JavaScript:

function calculate(s) {
    const stack = [];
    let num = 0;
    let sign = 1;
    let result = 0;
    
    for (const char of s) {
        if (char >= '0' && char <= '9') {
            num = num * 10 + parseInt(char);
        } else if (char === '+') {
            result += sign * num;
            num = 0;
            sign = 1;
        } else if (char === '-') {
            result += sign * num;
            num = 0;
            sign = -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;
}

C#:

public class Solution {
    public int Calculate(string s) {
        var stack = new Stack<int>();
        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 == '+') {
                result += sign * num;
                num = 0;
                sign = 1;
            } else if (c == '-') {
                result += sign * num;
                num = 0;
                sign = -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;
    }
}

Complexity Analysis

Time Complexity: O(n) - Each character is processed once
Space Complexity: O(n) - For the stack

Key Insights

Stack-Based Evaluation: Use stack to handle operator precedence and parentheses
Sign Management: Track the sign for each number and operation
Parentheses Handling: Use stack to save state when encountering parentheses
Space Optimization: Single stack approach for better space efficiency

Edge Cases

Single Number: "5" → 5
Negative Numbers: "-5" → -5
Nested Parentheses: "((1+2))" → 3
Empty Spaces: " 1 + 2 " → 3
Complex Expression: "(1+(4+5+2)-3)+(6+8)" → 23

Follow-up Questions

Multiplication and Division: What if you need to handle * and /?
Different Operators: What if you have more operators like ^, %?
Floating Point: What if you need to handle floating point numbers?
Error Handling: How would you handle invalid expressions?

Common Mistakes

Sign Management: Not properly handling negative signs
Parentheses Order: Incorrect order of operations with parentheses
Number Building: Not properly building multi-digit numbers
Stack Management: Not properly managing stack operations

Interview Tips

Clarify Requirements: Ask about operator support and input format
Discuss Approaches: Mention both stack and recursive approaches
Handle Edge Cases: Discuss negative numbers and nested parentheses
Explain Algorithm: Walk through the stack-based evaluation process
Consider Optimizations: Discuss space and time optimizations