Basic Calculator III

Hard · Stack & Monotonic Stack · about 30 minutes

Asked at Meta, ByteDance, DoorDash, Snap, Microsoft, Discord.

Evaluate an expression string containing non-negative integers, '+', '-', '*', '/', parentheses and spaces. Integer division truncates toward zero. The expression is valid and every intermediate result fits in a 32-bit signed integer. Don't use a built-in eval.