LeetCode Basic Calculator II

LeetCode Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

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


本题是LeetCode Basic Calculator的简化版,去掉了括号,增加了乘除法。但是算法都是一模一样的,先把中缀转换为后缀,然后用栈求值。

代码如下:

// 优先级
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,用时85MS。

Leave a Reply

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