用栈来处理算式

3302. 表达式求值 - AcWing题库

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n' 
const int N=5e5+10;
stack<int>st;//存数字 
stack<char>op;//存操作符

void eval()
{
   int a=st.top();//第二个数 
   st.pop();
   int b=st.top();//第一个数 
   st.pop();
   char c=op.top();//运算符 
   op.pop();
   
   int x;
   if(c=='+' )x=b+a;
   if(c=='-' )x=b-a;
   if(c=='*') x=b*a;
   if(c=='/') x=b/a;
   
   st.push(x);	//入栈 


}







signed main()
{   
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0); 
  //优先级表 
  unordered_map<char,int>mp{ {'+',1},{'-',1},{'*',2},{'/',2} };
  string s;
  cin>>s;
  for(int i=0;i<s.size();i++)
  {
  	  auto c=s[i];
  	  if(isdigit(c))//是数字 
  	  {
  	      int x=0,j=i;
		  while(j<s.size() && isdigit(s[j]))//找到非数字为止 
		   x=x*10+ s[j++]-'0';
		  i=j-1;//更新i 
		  st.push(x);
		  
		  	
			
	   }
	   
	   else if(c=='(') op.push(c);//（入栈 
	   else if(c==')') 
	   {
	   	   while(op.top()!='(') eval();//找到（为止 先进行运算括号内的值因为优先级最大 
	   	   op.pop();//（出栈 
	   }
	   else 
	      {
	   	       while(op.size() &&op.top() != '('&& mp[op.top()]>=mp[c]) eval();//如果栈顶运算符更大就进行运算 
	   	       op.push(c);//入栈 
	      }
  }
  while(op.size()) eval();//对剩余数运算 
   cout<< st.top()<<endl;
	
  
   
      
   
  
    
  
  
  
  
  
}