ALGO-156 表达式计算

客官°小女子只卖身不卖艺 2022-03-17 14:08 98阅读 0赞

题目：[http://lx.lanqiao.cn/problem.page?gpid=T419][http_lx.lanqiao.cn_problem.page_gpid_T419]

万分感谢大佬 ：[https://blog.csdn.net/reidsc/article/details/54669433][https_blog.csdn.net_reidsc_article_details_54669433]

#include<iostream>
    #include<stack>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    stack<char> s1,s2;
    stack<int> s3;
    int num[25];
    char s[1005];
    int priority(char ch){   //比较运算符 
    	if(ch=='('||ch==')') return 1;
    	if(ch=='+'||ch=='-') return 2;
    	if(ch=='*'||ch=='/') return 3;
    }
    int Scal(int x,int y,char ch){  //计算 
    	if(ch=='+') return x+y;
    	if(ch=='-') return x-y;
    	if(ch=='*') return x*y;
    	if(ch=='/') return x/y;
    } 
    void  transla(int n){//中缀表达式转后缀表达式 
    	 for(int i=0;i<n;i++){
    	 	 if(s[i]>='0'&&s[i]<='9'){//字符为数字 
    	 	 	    s2.push(s[i]); //入数字栈
    	 	 	if(i+1<n&&(s[i+1]<'0'||s[i+1]>'9') ||i==n-1){ //当下个字符不是数字或者为最后一位时，加上分隔符 
    		  	    s2.push('#'); 
    			  }
    			
    		  }
    		 else{
    		 	if(s1.empty()||s[i]=='('|| priority(s[i])>priority(s1.top())){//如果是运算符，三种情况直接入栈 
    		 		s1.push(s[i]);
    			 }
    			else if(s[i]==')'){//如果是右括号 
    				while(s1.top()!='('){//将左括号之前的符号出栈，入栈2 
    					s2.push(s1.top());
    					s1.pop();
    				}
    				s1.pop();
    			}
    			else{//当运算符级别小于或者等于栈1栈顶运算符级别，将第一个大于当前运算符的运算符出栈，当前运算符进栈
    			    while(!s1.empty()&&priority(s[i])<=priority(s1.top())&&s1.top()!='('){
    			    	s2.push(s1.top());
    					s1.pop(); 
    				}
    				s1.push(s[i]);
    			} 
    		 } 
    	 }
    	 while(!s1.empty()){//表达式结束 将栈1符号转移到栈2 
    	 	s2.push(s1.top());
    		 s1.pop(); 
    	 } 
    	 int k=0;
    	 while(!s2.empty()){//将栈内数据放回字符串s中 
    	 	s[k++]=s2.top();
    	 	s2.pop();
    	 }
    	 reverse(s,s+k);//字符串反向
    	 s[k]=0; 
    } 
    int Cal(int n)//后缀表达式计算    
    {    
        int x,y,tmp=0,k=0;    
        for(int i=0;i<n;i++)       
            if(s[i]=='#')//是#直接跳过    
                continue;    
            else if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/')//是运算符弹出栈顶两元素计算后放回栈    
            {    
                x=s3.top();    
                s3.pop();    
                y=s3.top();    
                s3.pop();    
                x=Scal(y,x,s[i]);    
                s3.push(x);    
            }    
            else//是数字字符       
                if(s[i+1]=='#')//下一个元素是#    
                {    
                    num[k++]=s[i]-'0';    
                    for(int i=0;i<k;i++)    
                        tmp+=(num[i]*(int)pow(10,k-i-1));    
                    s3.push(tmp);    
                    tmp=0;    
                    k=0;                    
                }    
                else//下一个元素不是#       
                    num[k++]=s[i]-'0';                  
        return s3.top();    
    }  
    int main(){
    	gets(s);
    	transla(strlen(s));
    	//cout<<s<<endl;
    	cout<<Cal(strlen(s))<<endl;
    	return 0;
    }

[http_lx.lanqiao.cn_problem.page_gpid_T419]: http://lx.lanqiao.cn/problem.page?gpid=T419
[https_blog.csdn.net_reidsc_article_details_54669433]: https://blog.csdn.net/reidsc/article/details/54669433