# LeetCode Basic Calculator

LeetCode 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 .

You may assume that the given expression is always valid.

Some examples:

```"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23
```

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

• 如果是操作数，直接压入numbers
• 如果是操作符op：
1. 如果op为左括号“（”，则直接把op压入opers
2. 如果op为右括号“）”，则把opers的运算符不断弹栈并压入numbers，直到栈顶为左括号“（”，此时将这一对括号丢弃
3. 如果opers为空，或者opers栈顶为左括号“（”，则直接把op压入opers
4. 此时，栈顶肯定不可能是括号了，如果op的优先级高于opers栈顶的优先级，则直接把op压入opers
5. 否则，把opers栈顶的运算符不断弹栈并压入numbers，直到栈顶为左括号，或者op的优先级高于opers栈顶的优先级。把op压入opers

```// 优先级
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);
}
};
```