LeetCode Q224: Basic Calculator (hard)

Implement a basic calculator to evaluate a simple expression string.

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

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Solution:
Using stack. Following is my solution which although right but didn't pass all the test due to LTE. However, the theoretical bound of time complexity is till O(n) though.



Solutoin 2: Basically, the idea is very similar to my solution, but using less stack operation which I think is the reason that makes my problem slow.