表达式计算模板

• 使用栈模拟表达式树的计算。

#include<bits/stdc++.h>
using namespace std;
const int MOD=10000; 
stack<int> nums;
stack<char> ops;
void cal()
{
	int b=nums.top();nums.pop(); //取出左子树
	int a=nums.top();nums.pop(); //取出右子树
	char c=ops.top();ops.pop(); //取出计算符
	if(c=='+') nums.push((a+b)%MOD); // 计算根节点
	else nums.push(a*b%MOD);
 } 
int main()
{
	string s;
	cin>>s;
	map<char,int> h={{'+',1},{'*',2}}; //符号优先级
	for(int i=0;i<s.size();i++)
	{
		if(isdigit(s[i]))  //取出一段数字
		{
			int j=i,x=0;
			while(j<s.size()&&isdigit(s[j]))
			{
				x=x*10+s[j]-'0';
				j++;
			}
			j--;
			nums.push(x%MOD); //当前数值
			i=j;
		}
		else
		{
			while(ops.size()&&h[ops.top()]>=h[s[i]]) cal(); //计算左子树
			ops.push(s[i]); //符号
		}
	}
	while(ops.size()) cal(); //计算剩余运算符
	cout<<nums.top()<<endl; //输出根节点
	return 0;
}