+-*/运算符优先级计算模板

acwing3302

知识点一：有关unordered_map的优先级

头文件<unordered_map>,然后进行符号优先级定义

定义方式unordered_map<char,int>pr{ {'+',1},{'-',1},{'*',2},{'/',2}};其余没定义的默认为0

知识点二：头文件<cctype>中的isdigit()是判断是否是数字的函数是则返回true

#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
#include<unordered_map>
using namespace std;
stack<int>num;
stack<int>op;
void eval(){
	auto b=num.top();num.pop();//第二个操作的数 
	auto a=num.top();num.pop();//第一个操作的数 
	auto c=op.top();op.pop();//运算符 
	int x;
	if(c=='+')x=a+b;
	else if(c=='-')x=a-b;
	else if(c=='*')x=a*b;
	else x=a/b;
	num.push(x);//结果 
}
int main(){
	unordered_map<char,int>pr{
  
  {'+',1},{'-',1},{'*',2},{'/',2}};
	string str;
	cin>>str;//读入表达式 
	for(int i=0;i<str.size();i++){
		auto c=str[i];
		if(isdigit(c)){//数字入栈
			int x=0,j=i;//计算数字 
			while(j<str.size()&&isdigit(str[j])){
				//例子（如果是12，那x=1，然后就是1×10加数字2）才得到数字12 
				x=x*10+str[j]-'0';
				j++;
			}
			i=j-1;//使得i指向2，i下一次++就是数字12的下一个位置 
			num.push(x);//把12入栈 
		}
		else if(c=='(')op.push(c);
		else if(c==')'){
			while(op.top()!='(')eval();//一直算到左括号 
			op.pop();//左括号出栈 
		}
		else{
			//待入栈运算符优先级低，则先计算 
			while(op.size()&&pr[op.top()]>=pr[c])eval(); //先判空 
			op.push(c);//操作符入栈
		}
	}
	while(op.size())eval();//剩余结果进行计算
	cout<<num.top()<<endl;//输出结果
    return 0;
}
//例子
//(1+2)*(2+3)
//先放入栈为op中【(+	num【1，2
//然后遇到)了开始执行eval弹出num使得b等于2，a等于1不能颠倒，op弹出+
//然后进行1+2=3，入栈变成num【3，再弹出(，op【 空了
//再op【*,(,+,num【3,2,3最后遇到)执行eval弹出num的b等于3，a等于2，op弹出+
//然后进行 2+3=5,入栈变成num【3,5然后进行剩余计算eval得出结果
//如果过程中有两个符号对碰，比如【*再进行+要入栈时，就会先执行eval把+先计算掉 

 例题：洛谷P10473