leetcode 772 - Basic Calculator III

https://leetcode.com/problems/basic-calculator-iii/

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- (314/7+2)5)+3”=-12

Note: Do not use the eval built-in library function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
int calculate(string s) {
int i = 0;

return recursive(s, i);
}

long recursive(string &s, int &i) {
stack<int> stk;
int size = s.size();
long result = 0;
char prev = '+';

for (; i < size && prev != ')'; i++) {
if (s[i] == ' ') continue;

long num;
if (s[i] == '(')
num = recursive(s, ++i);
else
num = get_number(s, i);

if (prev == '+')
stk.push(num);
else if (prev == '-')
stk.push(-num);
else if (prev == '*') {
int n = stk.top(); stk.pop();
stk.push(n * num);
} else if (prev == '/') {
int n = stk.top(); stk.pop();
stk.push(n / num);
}

prev = s[i];
}

while (!stk.empty()) {
result += stk.top();
stk.pop();
}

return result;
}

long get_number(string &s, int &i) {
long num = 0;
int size = s.size();

while (i < size && isdigit(s[i])) {
num = num * 10 + (s[i] - '0');
i++;
}

return num;
}
};