题解 | #四则运算#

多么美的代码啊！ 大问题化小问题，逐个求解

#include <string>
#include <vector>
#include <cctype>

#include <stack>
using namespace std;

void minBrackets(string& s) {
	for (int i = 0; i < s.size(); ++i) {
		if (s[i] == '[' || s[i] == '{') s[i] = '(';
		if (s[i] == ']' || s[i] == '}') s[i] = ')';
	}
}

vector<string> transformString(string s) {
	vector<string> result;
	string temp;
	for (int i = 0; i < s.size(); ++i) {
		//若初始是-
		if (s[i] == 0 && s[i] == '-') temp += s[i];
		else if (i > 1 && s[i - 1] == '(' && s[i] == '-') temp += s[i];
		else if (isdigit(s[i])) temp += s[i];
		else {
			if (temp.size())
				result.push_back(temp);
			temp = "0";
			temp[0] = s[i];
			result.push_back(temp);
			temp = "";
		}
	}
	if (temp.size()) result.push_back(temp);
	return result;
}

bool isPrior(string s1, string s2) {
	if (s1 == "*" || s1 == "/") return true;
	else if (s1 == "+" || s1 == "-") {
		if (s2 == "+" || s2 == "-") return true;
		else return false;
	}
	//如果有左括号，同样返回false
	return false;
}

vector<string> transformPost(vector<string>& vec) {
	vector<string> result;
	string temp;
	stack<string> st;
	for (int i = 0; i < vec.size(); ++i) {
		if (vec[i] == "+" || vec[i] == "-" || vec[i] == "*" || vec[i] == "/") {
			while (!st.empty() && isPrior(st.top(), vec[i])) {
				result.push_back(st.top()); st.pop();
			}
			st.push(vec[i]);
		}
		else if (vec[i] == "(") st.push(vec[i]);
		else if (vec[i] == ")") {
			while (st.top() != "(") {
				result.push_back(st.top()); st.pop();
			}
			st.pop();
		}
		else {
			result.push_back(vec[i]);
		}
	}
	//当退出的时候，栈中可能还有元素
	while(!st.empty()){ result.push_back(st.top()); st.pop(); }
	return result;
}

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

int computePostResult(vector<string>& vec) {
	int result = 0;
	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();
}

int main() {
	//1.输入字符，处理字符(所有括号都改为小括号)
	string s;
	getline(cin, s);
	
	minBrackets(s);

	//2.将字符串单个作为每一项放在vecString当中(如果有负号，要单独写)
	vector<string> vecString = transformString(s);

	//3.将字符串转为后缀表达式，存放到新的数组当中
	vector<string> newVecString = transformPost(vecString);

	//4.计算后缀表达式的结果
	int result = computePostResult(newVecString);
	cout << result << endl;

	return 0;
}