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 .
The expression string contains only non-negative integers, +, -,
*, / operators , open ( and closing parentheses
) and empty spaces . The integer division should truncate toward
zero.
You may assume that the given expression is always valid. All intermediate results will be in
the range of [-2147483648, 2147483647].
Some examples:
"1 + 1" = 2 " 6-4 / 2 " = 4 "2*(5+5*2)/3+(6/2+8)" = 21 "(2+6* 3+5- (3*14/7+2)*5)+3"=-12
Note: Do not use the eval built-in library
function.