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.


给定一个字符串表达式,要求求解该表达式的值。

使用栈解决。我们通常看到的表达式称为中缀表达式,需要把它转换为后缀表达式,比如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

One thought on “LeetCode Basic Calculator

  1. Pingback: LeetCode Basic Calculator II | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *