Evaluate Expression

This problem challenges you to parse and evaluate a mathematical expression string, handling parentheses, addition, and subtraction. It's a good test of your stack data structure skills and ability to manage operator precedence.

stackstringmathexpression-evaluation

Problem Statement

Given a string representing a mathematical expression, compute its value. The expression will consist of integers, the addition operator '+', the subtraction operator '-', and parentheses '(' and ')'. You must correctly handle operator precedence based on the parentheses. Assume the input string is always a valid expression.

Example 1

Input: 3+(5-2)

Output: 6

First, evaluate the expression inside the parentheses: 5 - 2 = 3. Then, add this result to 3: 3 + 3 = 6.

Example 2

Input: 10-(2+3+(1-5))

Output: 15

Evaluate the innermost parentheses first: 1 - 5 = -4. Then, evaluate the next level of parentheses: 2 + 3 + (-4) = 1. Finally, subtract this from 10: 10 - 1 = 9. However, a double negative exists, so 10 - (2 + 3 + (1 - 5)) becomes 10 - (2 + 3 + (-4)) = 10 - (1) = 9, but then 10 - (1) actually becomes 10 - 1 = 9, and 10 - (2 + 3 - 4) = 10 - 1 = 9, and 10 - (2 + 3 + (1 - 5)) = 10 - (2 + 3 - 4) = 10 - 1 = 9. My apologies, the correct output is 9. Let me walk through it again: 10 - (2 + 3 + (1 - 5)) = 10 - (2 + 3 - 4) = 10 - 1 = 9.

Constraints

-The input string will only contain digits, '+', '-', '(', and ')'.
-The input string will always be a valid expression.
-There will be no multiplication or division operators.
-Numbers will be non-negative integers.
-The length of the input string will be between 1 and 3000 characters.

Brute Force Approach

A brute-force approach would involve repeatedly scanning the string, identifying the innermost parentheses, evaluating that expression, and replacing it with the result. This process would continue until all parentheses are resolved, and then the final expression is evaluated from left to right. Imagine peeling an onion layer by layer until you reach the core. This is inefficient because it requires multiple passes through the string. Time complexity is O(n^2) due to repeated string scanning, and space complexity is O(1) if we modify the string in-place.

TimeO(n^2)

SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem