Basic Calculator

Hard · Stack & Monotonic Stack · about 30 minutes

Asked at Google, Meta, Amazon, Microsoft, Bloomberg, Uber, Goldman Sachs, D. E. Shaw.

Given a string s holding a valid expression with non-negative integers, '+', '-', parentheses and spaces, evaluate it and return the result. '-' may also be unary (as in "-(2 + 3)" or "1 - (-2)"). Don't use a built-in eval.