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：
  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

如果是操作符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。