题意:写一个计算器,包括加减乘除
Input: s = “3+2*2”
Output: 7
链接
https://leetcode.com/problems/basic-calculator-iii/description/
https://leetcode.com/problems/basic-calculator-ii/description/
需要有一个operator stack以及一个num数字的stack,operator stack中的符号新来的优先级比后来的优先级要小的话那我就要计算
有个取数字的模版要记住:
if(isdigit(s[i])) {
int j = i;
while(j < s.size() && isdigit(s[j])) j++;
int x = stoi(s.substr(i, j-i));
num.push(x);
i = j - 1;
class Solution {
public:
int calculate(string s) {
stack<int> num;
stack<char> oper;
unordered_map<char, int> pr = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'(', 0}};
for(int i = 0; i < s.size(); i++) {
if(isdigit(s[i])) {
int j = i;
while(j < s.size() && isdigit(s[j])) j++;
int x = stoi(s.substr(i, j-i));
num.push(x);
i = j - 1;
} else if(pr.count(s[i])) {
while(oper.size() && pr[s[i]] <= pr[oper.top()]) {
get(num, oper);
}
oper.push(s[i]);
} else if(s[i] == ' ') {
continue;
} else if (s[i] == '(') {
oper.push(s[i]);
} else if (s[i] == ')') {
while(oper.top()!= '(') {
get(num, oper);
}
oper.pop();
}
}
while(oper.size()) {
get(num, oper);
}
return num.top();
}
void get(stack<int>& num, stack<char>& oper) {
int num1 = num.top();
num.pop();
int num2 = num.top();
num.pop();
char op = oper.top();
oper.pop();
int result = 0;
switch(op) {
case '*': result = num1 * num2; break;
case '+': result = num1 + num2; break;
case '-': result = num2 - num1; break;
case '/': result = num2 / num1; break;
}
num.push(result);
}
};