Basic Calculator

Desicription

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 .

Example 1:

1
2
Input: "1 + 1"
Output: 2

Example 2:

1
2
Input: " 2-1 + 2 "
Output: 3

Example 3:

1
2
Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Note:

  • You may assume that the given expression is always valid.
  • Do not use the eval built-in library function.

Solution

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
class Solution {
public:
int calculate(string s) {
stack<int> sum_stack;
int result = 0;
int sign = 1;
for(int i = 0; s[i]; i++) {
if(s[i] >= '0' && s[i] <= '9') {
int number = s[i] - '0';
while(s[i+1] && s[i+1] >= '0' && s[i+1] <= '9') {
i++;
number = number * 10 + s[i] - '0';
}
result += number * sign;
} else if(s[i] == '+') {
sign = 1;
} else if(s[i] == '-') {
sign = -1;
} else if(s[i] == '(') {
sum_stack.push(result);
sum_stack.push(sign);
result = 0;
sign = 1;
} else if(s[i] == ')') {
auto current_sign = sum_stack.top();
sum_stack.pop();
auto current_result = sum_stack.top();
sum_stack.pop();
result = current_sign * result + current_result;
}
}
return result;
}
};