中缀表达式 C++ 蓝桥杯 栈

表达式求值

#include<iostream>
#include<stack>
using namespace std;
int main() {
	stack<int>stk;
	//   2  +10*2   +23*100   +43   +1
	int x; cin >> x;//可以把表达式归纳为除了第一个值直接入栈，其他满足运算符，再输入一个数值
	stk.push(x%10000);//最后求后四位，为了防止数据过大，所以运用模运算的性质，(m1+m2)%10000等价于m1%10000+m2%10000)%10000

	int sum = 0;

	char s; 
	while (cin >> s >> x) {//传入运算符号，再传值
		if (s == '+') {//遇到加号，后面数字就入栈
			stk.push(x % 10000);
		}
		else if (s == '*') {//遇到乘号，栈顶元素直接乘上后面的数字
			stk.top() *= x % 10000;
			stk.top() %= 10000;
		}
	}

	//  将栈里面所有的元素相加
	while (!stk.empty()) {
		sum += stk.top() % 10000;
		sum %= 10000;
		stk.pop();
	}

	cout << sum;

	return 0;
}

思路来源： 中缀表达式，首先考虑到用栈，因为在设计运算符有优先级，乘法在加法之前（争对这个题），所以在遇到乘号的时候，直接优先算。所以可以联系到栈来解决。

如下图：

思路——具体细节：先创建一个int变量，把值压入栈中，（假设这个值前面有一个加号），之后就是规律，一个运算符一个数值，要通过if条件分子判断，如果字符是‘+’，那么将后面的值入栈，如果字符是'*'乘号，将后面的值乘在栈顶元素上。最后将栈里的元素全部相加，就是这个表达式的值。

注意：这个要求表达式后四位，也就是最后要模上10000，求值的后四位，这个过程，求和肯定会爆数据类型，所以运用模运算性质，在每一步上对10000取模。

比如：加法模运算性质  ( a1+a2+a3)%10000=((a1%10000+a2%10000)%10000+a3%10000)%10000       规律即是，加上a%10000，再总体对10000取模。

比如：乘法模运算性质  ( a1*a2*a3)%10000=

((a1%10000*a2%10000)%10000*a3%10000)%10000    规律即是，乘上这个数对10000取模，再整体对10000取模。

思路——栈元素求和：while循环，当栈非空，让栈顶元素对10000取模之后加到sum里，再让sum对10000取模，栈顶元素弹出。最后输出sum。即是表达式值后四位。

完结！！！՞⸝⸝. .⸝⸝՞˳ഒ