# LeetCode Basic Calculator II

LeetCode Basic Calculator II
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, `+`, `-`, `*`, `/` operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:

```"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
```

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

```// 优先级
unordered_map<string, int> priority = { {"+", 1},{"-", 1},{"*", 2},{"/", 2} };
class Solution {
private:
void push(stack<string> &numbers, stack<string> &opers, const string& numOrop) {
if (isdigit(numOrop[0])) {
numbers.push(numOrop);
}
else {
if (numOrop == ")") {
while (opers.top() != "(") {
numbers.push(opers.top());
opers.pop();
}
opers.pop();
}
else if (numOrop == "(") {
opers.push(numOrop);
}
else if (opers.empty() || opers.top() == "(") {
opers.push(numOrop);
}
else if (priority[numOrop] > priority[opers.top()]) {
opers.push(numOrop);
}
else {
while (!opers.empty() && opers.top() != "(" && priority[numOrop] <= priority[opers.top()]) {
numbers.push(opers.top());
opers.pop();
}
opers.push(numOrop);
}
}
}
// 中缀转后缀表达式
list<string> in2post(const string& s) {
stack<string> numbers, opers;
int start = 0, end = 1, n = s.size();
while (start < n) {
while (start < n&&s[start] == ' ')++start;
if (start >= n)break;
if (isdigit(s[start])) {
end = start + 1;
while (end < n&&isdigit(s[end]))++end;
string num = s.substr(start, end - start);
push(numbers, opers, num);
start = end;
}
else {
string op = string(1, s[start]);
push(numbers, opers, op);
++start;
}
}
while (!opers.empty()) {
numbers.push(opers.top());
opers.pop();
}
list<string> ans;
while(!numbers.empty()) {
ans.push_front(numbers.top());
numbers.pop();
}
return ans;
}
// 求值后缀表达式的值
int eval(list<string>& post) {
int ans = 0;
stack<int> numbers;
for (const auto& s : post) {
if (priority.find(s) != priority.end()) {
int num2 = numbers.top();
numbers.pop();
int num1 = numbers.top();
numbers.pop();
if (s == "+")numbers.push(num1 + num2);
else if (s == "-")numbers.push(num1 - num2);
else if (s == "*")numbers.push(num1*num2);
else numbers.push(num1 / num2);
}
else numbers.push(stoi(s));
}
return numbers.top();
}
public:
int calculate(string s) {
list<string> ans = in2post(s);
return eval(ans);
}
};
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.