FZU2215 Simple Polynomial Problem（中缀表达求值）

比赛时没做出这题太可惜了。

赛后才反应过来这就是个中缀表达式求值，数字栈存的不是数字而是多项式。

而且，中缀表达式求值很水的，几行就可以搞定。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 struct Poly{
 6     long long a[1111];
 7     Poly operator+(const Poly &p)const{
 8         Poly np={0};
 9         for(int i=0; i<1111; ++i){
10             np.a[i]=(a[i]+p.a[i])%1000000007;
11         }
12         return np;
13     }
14     Poly operator*(const Poly &p)const{
15         Poly np={0};
16         for(int i=0; i<1111; ++i){
17             if(a[i]==0) continue;
18             for(int j=0; j<1111; ++j){
19                 if(p.a[j]==0) continue;
20                 np.a[i+j]+=a[i]*p.a[j];
21                 np.a[i+j]%=1000000007;
22             }
23         }
24         return np;
25     }
26 }pstk[1111];
27 char ostk[1111]={'#'};
28 int ptop,otop,pri[333];
29 void push(char op){
30     if(ostk[otop]=='#' && op=='#') return;
31     if(ostk[otop]=='(' && op==')'){
32         --otop;
33         return;
34     }
35     if(pri[ostk[otop]]<pri[op] || ostk[otop]=='('){
36         ostk[++otop]=op;
37         return;
38     }
39     if(ostk[otop--]=='+'){
40         Poly p=pstk[ptop]+pstk[ptop-1];
41         ptop-=2;
42         pstk[++ptop]=p;
43     }else{
44         Poly p=pstk[ptop]*pstk[ptop-1];
45         ptop-=2;
46         pstk[++ptop]=p;
47     }
48     push(op);
49 }
50 void output(Poly &p){
51     int i=1110;
52     while(i>=0 && p.a[i]==0) --i;
53     if(i==-1){
54         puts("0");
55         return;
56     }
57     for(int j=i; j>=0; --j){
58         printf("%I64d",p.a[j]);
59         if(j) putchar(' ');
60     }
61     putchar('
');
62 }
63 int main(){
64     pri['+']=2; pri['*']=3;
65     pri['(']=4; pri[')']=1;
66     pri['#']=1;
67     int t;
68     char str[1111];
69     scanf("%d",&t);
70     while(t--){
71         scanf("%s",str);
72         ptop=0; otop=1;
73         for(int i=0;str[i];++i){
74             if(str[i]>='0' && str[i]<='9'){
75                 Poly p={0};
76                 p.a[0]=str[i]-'0';
77                 pstk[++ptop]=p;
78             }else if(str[i]=='x'){
79                 Poly p={0};
80                 p.a[1]=1;
81                 pstk[++ptop]=p;
82             }else{
83                 push(str[i]);
84             }
85         }
86         push('#');
87         output(pstk[ptop]);
88     }
89     return 0;
90 }