-
Notifications
You must be signed in to change notification settings - Fork 0
/
BasicCalculator.cpp
96 lines (80 loc) · 2.66 KB
/
BasicCalculator.cpp
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/*
224. Basic Calculator
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:
Input: "1 + 1"
Output: 2
Example 2:
Input: " 2-1 + 2 "
Output: 3
Example 3:
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.
From <https://leetcode.com/problems/basic-calculator/description/>
*/
class Solution {
public:
int precedence(char s) {
if(s == '+' || s == '-') {
return 1;
} else if(s == '*' || s == '/') {
return 2;
} else {
return 0;
}
}
int applyOperator(int a, int b, char op) {
switch(op) {
case '+' : return a+b;
case '-' : return a-b;
case '*' : return a*b;
case '/' : return a/b;
}
}
int calculate(string s) {
stack<int> numbers;
stack<char> operators;
for(int i = 0; i < s.length(); i++) {
if(s[i] == ' ') {
continue;
} else if(s[i] == '(') {
operators.push(s[i]);
} else if(s[i] == ')') {
while(!operators.empty() && operators.top() != '(') {
int val2 = numbers.top(); numbers.pop();
int val1 = numbers.top(); numbers.pop();
char op = operators.top(); operators.pop();
numbers.push(applyOperator(val1,val2,op));
}
operators.pop();
} else if(isdigit(s[i])) {
int num = 0;
while(i < s.length() && isdigit(s[i])) {
num = num * 10 + s[i] - '0';
i++;
}
i--;
numbers.push(num);
} else {
while(!operators.empty() && precedence(operators.top()) >= precedence(s[i])) {
int val2 = numbers.top(); numbers.pop();
int val1 = numbers.top(); numbers.pop();
char op = operators.top(); operators.pop();
numbers.push(applyOperator(val1,val2,op));
}
operators.push(s[i]);
}
}
while(!operators.empty()) {
int val2 = numbers.top(); numbers.pop();
int val1 = numbers.top(); numbers.pop();
char op = operators.top(); operators.pop();
numbers.push(applyOperator(val1,val2,op));
}
return numbers.top();
}
};