http://acm.hnu.cn/online/?action=problem&type=show&id=12817&courseid=267 7.19hnu/数据结构/数学 xxs.code

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<deque>
 6 #include<cstdlib>
 7 using namespace std;
 8 typedef long long INT;
 9 const INT MOD = 1000000007; 
10 const int maxn = 2000000+5;
11 char str[maxn],temp[maxn];
12 int get_num(INT s,INT t)
13 {
14     for(int i = 0;i < t;++i)
15     {
16         s = s >> 1;
17         if(s == 0)
18         return 0;
19     }
20     return s;
21 }
22 int main()
23 {
24     while(gets(temp))
25     {
26         if(temp[0] == '#')
27         break;
28         int len = strlen(temp),f = 0;
29         for(int i = 0;i < len; ++i)
30         if(temp[i] != ' ')
31         str[f++] = temp[i];
32         str[f] = NULL;
33         len = f;
34         deque<INT> que1;
35         deque<char> que2;
36         //预处理
37         for(int i = 0;i < len-2;++i)
38         if(str[i] == '>' && str[i+1] == '>' && str[i+2] != '>')
39         str[i] = str[i+1] = '^';
40         char ss[20];       //缓存数字
41         for(int i = 0;i < len;++i)
42         {
43             if(str[i] == 'S'  || str[i] == 's')
44             {
45                 i++;
46                 que2.push_front('<');
47             }
48             if(str[i] == '>')
49             {
50                 INT tt = *que1.begin();
51                 que1.pop_front();
52                 que2.pop_front();    //计算完后把'<'弹出来
53                 tt *= tt;
54                 tt %= MOD;
55                 if(*que2.begin() == '^')
56                 {
57                     INT tt2 = *que1.begin();
58                     que1.pop_front();
59                     que1.push_front(get_num(tt2,tt));
60                     que2.pop_front();
61                 }
62                 else que1.push_front(tt);
63             }
64             if(str[i] == '^')
65             {
66                 i++;
67                 que2.push_front('^');
68             }
69             if(str[i] >= '0' && str[i] <= '9')
70             {
71                 int ll = 0;
72                 while(str[i] >= '0' && str[i] <= '9')
73                 {
74                     ss[ll++] = str[i];
75                     i++;
76                 }
77                 i--;
78                 ss[ll] = NULL;
79                 int tt = atoi(ss);
80                 if(*que2.begin() == '^')
81                 {
82                     int tt2 = *que1.begin();
83                     que1.pop_front();
84                     que2.pop_front();
85                     que1.push_front(get_num(tt2,tt));  //get_num计算tt2 >> tt之后压回到栈中
86                 }
87                 else que1.push_front(tt);
88             }
89         }
90         
91         printf("%d
",*que1.begin());
92         que2.clear();
93         que1.clear();
94     }
95     return 0;
96 }