Evaluate Parenthesized Sums with Unary Minus
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Evaluate a valid expression containing decimal numbers, plus, minus, parentheses and spaces. Unary minus is allowed; unary plus is not. Do not use eval or any other built-in string-expression evaluator. Return the integer value.
```cpp
int calculate(string s);
```
### Examples
```text
Input: s = "-(3-(2+5))+4"
Output: 8
```
```text
Input: s = " 9 - (6 + 1) "
Output: 2
```
### Constraints
- Length is between 1 and 300000.
- Characters are digits, `+`, `-`, `(`, `)`, and ASCII space.
- The expression is valid, no two operators are consecutive, and plus is not unary.
- Every number and running calculation fits signed 32-bit.
Overview: Evaluate parenthesized addition and subtraction with unary minus, explicit context stacks and widened sign arithmetic.
