题解 | #表达式求值#

#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <algorithm>
#include <stack>
using namespace std;

bool comp(string c1, string c2) {
	if (c1 == "*" || c1 == "/") return true;
	else if (c1 == "+" || c1 == "-") {
		if (c2 == "+" || c2 == "-") return true;
		else return false;
	}
	//还要考虑栈顶是(括号的情况
	return false;
}

int compute(int a, int b, string c) {
	if (c == "+") return a + b;
	else if (c == "-") return a - b;
	else if (c == "*") return a * b;
	else return a / b;
}

int resultCom(vector<string>& vec) {
	stack<int> st;
	for (int i = 0; i < vec.size(); ++i) {
		if (vec[i] == "+" || vec[i] == "-" || vec[i] == "*" || vec[i] == "/") {
			int b = st.top(); st.pop();
			int a = st.top(); st.pop();
			st.push(compute(a, b, vec[i]));
		}
		else {
			st.push(stoi(vec[i]));
		}
	}
	return st.top();
}

vector<string> transfer(vector<string>& result) {
	stack<string> st;
	//将转换后的结果放到新的vector当中
	vector<string> newResult;
	for (int i = 0; i < result.size(); ++i) {
		//如果是操作符的话
		if (result[i] == "+" || result[i] == "-" || result[i] == "*" || result[i] == "/") {
			while (!st.empty() && comp(st.top(), result[i])) {
				newResult.push_back(st.top()); st.pop();
			}
			st.push(result[i]);
		}
		//如果是左括号的话
		else if (result[i] == "(") st.push(result[i]);
		//如果是右括号的话，将一直出栈到左括号
		else if (result[i] == ")") {
			while (st.top() != "(") {
				newResult.push_back(st.top()); st.pop();
			}
			st.pop();
		}
		//否则就是数字，直接进来就行
		else {
			newResult.push_back(result[i]);
		}
	}
	while (!st.empty()) { newResult.push_back(st.top()); st.pop(); }
	return newResult;
}

int main() {
	//1.输入原始字符串
	string s;
	getline(cin, s);
	//2.将原始字符串封装好放到vec当中。每一项要么是数字字符串，要么是普通操作符或者括号
	string temp;
	vector<string> result;
	/*for (int i = 0; i < s.size(); ++i) {
		if (s[i] >= '0' && s[i] <= '9') temp += s[i];
		else {
			if(temp.size())
				result.push_back(temp);
			temp = "";
			temp += s[i];
			result.push_back(temp);
			temp = "";
		}
	}*/
	for (int i = 0; i < s.size(); ++i) {
		if (i == 0 && (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/')) temp += s[i];
		else if (s[i - 1] == '(' && (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/')) temp += s[i];
		else if (s[i] >= '0' && s[i] <= '9') temp += s[i];
		else {
			if (temp.size())
				result.push_back(temp);
			temp = "";
			temp += s[i];
			result.push_back(temp);
			temp = "";
		}
	}
	if (temp.size()) result.push_back(temp);
	//3.将result转为后缀表达式
	vector<string> newResult = transfer(result);
	//4.后缀表达式求解结果
	cout << resultCom(newResult) << endl;
	return 0;
}