Implement a basic arithmetic expression evaluator.
You are given a string s representing a mathematical expression containing non-negative integers and the operators '+', '-', '*', and '/'.
Compute and return the value of the expression.
'+'
,
'-'
,
'*'
,
'/'
' '
(which should be ignored)
'*'
and division
'/'
have higher precedence than addition
'+'
and subtraction
'-'
.
You may implement a function in the language of your choice, for example:
int calculate(String s)
and return the evaluated integer result.
Example 1
"3+2*2"
7
2*2 = 4
, then
3 + 4 = 7
.
Example 2
" 14-3/2 "
13
3/2
truncates toward zero and becomes
1
, so
14 - 1 = 13
.
Example 3
"100/10*3+5"
35
100/10 = 10
,
10*3 = 30
, then
30 + 5 = 35
.
1 <= s.length <= 100000
O(n)
where
n
is the length of
s
.
O(1)
or
O(n)
(excluding the input string).