224. Basic Calculator 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.
给定一个字符串表达式，要求求解该表达式的值。 使用栈解决。我们通常看到的表达式称为中缀表达式，需要把它转换为后缀表达式，比如1+((2+3)×4)-5转换为1 2 3 + 4 × + 5 -。我们可以很容易用栈求解后缀表达式，只需要遍历后缀表达式，把遇到的操作数压栈，只要遇到运算符，就从栈中弹出两个操作数，进行运算，再把运算结果压栈。最后栈中只能得到一个值，就是整个表达式的值。 所以问题的关键就是怎样把中缀表达式转换为后缀表达式。 使用两个栈，一个栈保存操作数numbers，另一个栈保存运算符opers。遍历原字符串，按如下规则进行压栈和弹栈：
- 如果是操作数，直接压入numbers
- 如果是操作符op：
- 如果op为左括号“（”，则直接把op压入opers
- 如果op为右括号“）”，则把opers的运算符不断弹栈并压入numbers，直到栈顶为左括号“（”，此时将这一对括号丢弃
- 如果opers为空，或者opers栈顶为左括号“（”，则直接把op压入opers
- 此时，栈顶肯定不可能是括号了，如果op的优先级高于opers栈顶的优先级，则直接把op压入opers
- 否则，把opers栈顶的运算符不断弹栈并压入numbers，直到栈顶为左括号，或者op的优先级高于opers栈顶的优先级。把op压入opers
如果是操作符op，下面的1~5的判断规则是有先后顺序的，需要先判断是否为括号，再判断是否是一般的运算符。 运算符的优先级是，+-优先级相同，*/优先级相同，且+-的优先级低于*/。 得到中缀表达式的后缀表达式之后，再用开头提到的栈求解。后缀表达式的求值就非常简单了。 完整代码如下：
// 优先级
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);
}
};
本代码提交AC，用时92MS。
参考：http://blog.csdn.net/antineutrino/article/details/6763722
二刷。push函数实际上只有3个分支就可以了，上面的过于复杂，看下面：
unordered_map<string, int> priority = { {"+",1},{"-",1},{"*",2},{"/",2} };
class Solution {
private:
bool IsDigit(char c) {
return c >= '0'&&c <= '9';
}
vector<string> ParseString(const string &s) {
vector<string> vec;
int n = s.size();
int i = 0, j = 0;
while (i < n) {
while (i < n&&s[i] == ' ')++i;
if (i >= n)break;
if (!IsDigit(s[i])) {
vec.push_back(string(1, s[i]));
++i;
}
else {
j = i + 1;
while (j < n&&IsDigit(s[j]))++j;
vec.push_back(s.substr(i, j - i));
i = j;
}
}
return vec;
}
list<string> In2Post(const vector<string> &vec) {
stack<string> numbers, opers;
for (int i = 0; i < vec.size(); ++i) {
if (IsDigit(vec[i][0])) {
numbers.push(vec[i]);
}
else {
if (vec[i] == ")") { // 右括号
while (opers.top() != "(") {
numbers.push(opers.top());
opers.pop();
}
opers.pop();
}
else if (vec[i] == "(") { // 左括号
opers.push(vec[i]);
}
else { // 操作符
while (!opers.empty() && opers.top() != "("&&priority[vec[i]] <= priority[opers.top()]) {
numbers.push(opers.top());
opers.pop();
}
opers.push(vec[i]);
}
}
}
while (!opers.empty()) {
numbers.push(opers.top());
opers.pop();
}
list<string> lst;
while (!numbers.empty()) {
lst.push_front(numbers.top());
numbers.pop();
}
return lst;
}
int Evaluate(const list<string> &lst) {
stack<string> stk;
for (list<string>::const_iterator it = lst.begin(); it != lst.end(); ++it) {
if (IsDigit((*it)[0])) {
stk.push(*it);
}
else {
int b = atoi(stk.top().c_str());
stk.pop();
int a= atoi(stk.top().c_str());
stk.pop();
if (*it == "+") {
stk.push(to_string(a + b));
}
else if (*it == "-") {
stk.push(to_string(a - b));
}
}
}
return atoi(stk.top().c_str());
}
public:
int calculate(string s) {
vector<string> vec = ParseString(s);
list<string> lst = In2Post(vec);
return Evaluate(lst);
}
};
本代码提交AC，用时312MS。