hdu 1296

原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1296

题意：多项式求值；

思路：很水的一道题（方法有多种），这里用表达式求值（转化成后缀表达式）的方式

　　　不知到这个方法的朋友可以看看大神的：http://blog.csdn.net/sr_19930829/article/details/50809712

　　　可以帮助大家理解；

反省：这个题的数据可以说很坑人：-X，+X，0X（是数字零不是字母o）一直RE就是死在这三个数据上了

代码：

  1 #include<stack>
  2 #include<iostream>
  3 #include<string>
  4 #include<cstdio>
  5 
  6 using namespace std;
  7 
  8 struct Pri{
  9     char op;
 10     int pri;
 11 }lpri[4]={{'+',2},{'-',2},{'*',4},{'^',6}},
 12  rpri[4]={{'+',1},{'-',1},{'*',3},{'^',5}};
 13  
 14 int find_leftPri(char op)
 15 {
 16     for(int i=0;i<4;i++)
 17         if(op==lpri[i].op)
 18             return lpri[i].pri;
 19 }
 20 
 21 int find_rightPri(char op)
 22 {
 23     for(int i=0;i<4;i++)
 24         if(op==rpri[i].op)
 25             return rpri[i].pri;
 26 }
 27 
 28 int Precede(char op1,char op2)
 29 {
 30     int L=find_leftPri(op1);
 31     int R=find_rightPri(op2);
 32     if(L==R)
 33         return 0;
 34     if(L>R)
 35         return 1;
 36     return -1;
 37 }
 38 
 39 long long pow(int x,int n)
 40 {
 41     long long ans=1;
 42     while(n--)
 43         ans*=x;
 44     return ans;
 45 }
 46 
 47 long long Run(stack<long long>& num,char op)
 48 {
 49     long long a=num.top();
 50     num.pop();
 51     long long b=num.top();
 52 //    cout<<"a="<<a<<" b="<<b<<" op is "<<op<<endl;
 53     num.pop();
 54     switch(op)
 55     {
 56         case '+':
 57             return b+a;
 58         case '-':
 59             return b-a;
 60         case '*':
 61             return b*a;
 62         case '^':
 63             return pow(b,a);
 64     }
 65 }
 66 
 67 int main()
 68 {
 69     string s;
 70     int x;
 71     while(scanf("%d",&x)!=EOF)
 72     {
 73         stack<char>op;
 74         stack<long long>num;
 75         int i,j;
 76         cin>>s;
 77         for(i=0;i<s.length();i++)
 78         {
 79         //    cout<<"i="<<i<<endl;
 80             if(s[i]>='0'&&s[i]<='9')
 81             {
 82                 int t=0;
 83                 for(j=i;s[j]>='0'&&s[j]<='9';j++)
 84                     t=t*10+(s[j]-'0');
 85                 num.push(t);
 86                 i=j-1;
 87             //    cout<<"@@t="<<t<<" i="<<i<<" j="<<j<<endl;
 88             }
 89             else if(s[i]=='X')
 90             {
 91                 int t=0;
 92                 if((s[i-1]=='-'||s[i-1]=='+')&&i!=0)
 93                     num.push(1);
 94                 if(!num.empty())
 95                     op.push('*');
 96                 num.push(x);
 97             }
 98             else
 99             {
100                 if((s[i]=='-'||s[i]=='+')&&num.empty())
101                 {
102                 //    cout<<"......-x......."<<endl;
103                         num.push(0);
104                 }
105                 if(op.empty())
106                     op.push(s[i]);
107                 else
108                 {
109                     int judg=Precede(op.top(),s[i]);
110                     switch(judg)
111                     {
112                         long long t;
113                         case 1:
114                             t=Run(num,op.top());
115                             num.push(t);
116                     //        cout<<"Run(num,op.top())="<<t<<endl;
117                             op.pop();
118                             i--;break;
119                         case -1:
120                             if((s[i]=='-'||s[i]=='+')&&s[i+1]=='X')
121                                 num.push(1);
122                             op.push(s[i]);break;        
123                     }
124                 }    
125             }
126         }
127         while(!op.empty())
128         {
129             num.push(Run(num,op.top()));
130             op.pop();
131         }
132         cout<<num.top()<<endl;
133     }
134     
135     return 0;
136 }

---------------欢迎评论指导---------------