题目连接
https://leetcode.com/problems/basic-calculator/
Basic Calculator
Description
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.
表达式计算。。
class ExpCalc {
private:
string ret;
stack<char> op;
stack<int> num;
inline void erase() {
ret = "";
while (!op.empty()) op.pop();
while (!num.empty()) num.pop();
}
inline int calc(int d1, int d2, char ch) {
int val = 0;
switch (ch) {
case '+': val = d1 + d2;
break;
case '-': val = d2 - d1;
break;
}
return val;
}
public:
ExpCalc() { erase(); }
~ExpCalc() { erase(); }
inline void InfixToPostfix(const string src) {
int n = src.length();
for (int i = 0; i < n;) {
if (' ' == src[i] || '=' == src[i]) { i++; continue; }
if ('(' == src[i]) op.push(src[i++]);
if (')' == src[i]) {
while (op.top() != '(') {
ret += op.top(); ret += ' ';
op.pop();
}
op.pop(); i++;
} else if ('-' == src[i] || '+' == src[i]) {
while (!op.empty() && ('-' == op.top() || '+' == op.top())) {
ret += op.top(); ret += ' ';
op.pop();
}
op.push(src[i++]);
} else {
while (isdigit(src[i])) {
ret += src[i++];
}
ret += ' ';
}
}
while (!op.empty()) {
ret += op.top(); ret += ' ';
op.pop();
}
ret += '=';
}
inline int PostfixCalc() {
int n = ret.length();
for (int i = 0; i < n;) {
if (' ' == ret[i] || '=' == ret[i]) { i++; continue; }
if ('-' == ret[i] || '+' == ret[i]) {
int d1 = num.top(); num.pop();
int d2 = num.top(); num.pop();
num.push(calc(d1, d2, ret[i++]));
} else if (isdigit(ret[i])) {
int x = 0;
while (isdigit(ret[i])) {
x = x * 10 + ret[i++] - '0';
}
num.push(x);
}
}
return num.top();
}
};
class Solution {
public:
int calculate(string s) {
if (s.empty()) return 0;
calc = new ExpCalc;
calc->InfixToPostfix(s);
int ans = calc->PostfixCalc();
return ans;
}
private:
ExpCalc *calc;
};