题解 | #表达式求值#

先求后缀表达式，然后根据后缀表达式求值

class Solution {
	public:
	/**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
	int solve(string s) {
		// write code here
		return cal(getPostExp(s));
	}
	int getPriority(char ch) {
		if(ch == '+' || ch == '-') return 2; else if(ch == '(') return 1; else return 3;
	}
	std::vector<string> getPostExp(string str) {
		stack<char> s;
		vector<string> ret;
		string tmp_num;
		for (char ch : str) {
			if (ch >= '0' && ch <= '9')
			            tmp_num += ch; else if (ch == '+' || ch == '-' || ch == '*') {
				if (tmp_num.size()) {
					ret.push_back(tmp_num);
					tmp_num.clear();
				}
				while (s.size() && getPriority(s.top()) >= getPriority(ch)) {
					string tmp(1, s.top());
					ret.push_back(tmp);
					s.pop();
				}
				s.push(ch);
			} else {
				if (tmp_num.size()) {
					ret.push_back(tmp_num);
					tmp_num.clear();
				}
				if (ch == '(')
				                s.push(ch); else {
					while (!s.empty() && s.top() != '(') {
						string tmp(1,s.top());
						ret.push_back(tmp);
						s.pop();
					}
					if(!s.empty() && s.top() == '(')
					                    s.pop();
				}
			}
		}
		if (tmp_num.size()) {
			ret.push_back(tmp_num);
		}
		while (s.size()) {
			string tmp(1, s.top());
			ret.push_back(tmp);
			s.pop();
		}
		return ret;
	}
	int cal(vector<string> str) {
		stack<int> s;
		for (string ch : str) {
			if (ch != "+" && ch != "-" && ch != "*") {
				int tmp = atoi(ch.c_str());
				//cout << tmp << endl;
				s.push(tmp);
			} else {
				int tmp;
				int num2 = s.top();
				s.pop();
				int num1 = s.top();
				s.pop();
				if (ch == "*") {
					tmp = num1 * num2;
				} else if (ch == "-") {
					tmp = num1 - num2;
				} else {
					tmp = num1 + num2;
				}
				s.push(tmp);
			}
		}
		return s.top();
	}
};