首页 > 代码库 > HNU 12817 Shipura（表达式求值）

HNU 12817 Shipura（表达式求值）

2024-07-12 23:41:47   215人阅读

题目链接：http://acm.hnu.cn/online/?action=problem&type=show&id=12817

解题报告：定义两种运算符号，一种是>>，就是右移，另一种是S<x>,S<X> = (X^2) % (1e9+7);

跟其它表达式求值一样，用两个栈，一个存操作数，另一个存操作符，有一个问题就是>这是符号到底是S<>它的一部分还是>>它的一部分，因为符号>>紧挨右边一定要有操作数的，而S<>紧挨右边是一定没有操作数的，所以只要看是不是两个连续的>，并且紧挨右边有没有操作数，如果都符合的话就是>>。然后就是每次计算完S<>这个之后要对符号栈的栈顶进行判断，如果是>>就要继续计算。

  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         while(!que2.empty()) 91         { 92             if(*que2.begin() == ‘^‘) 93             { 94                 que2.pop_front();   //现在只可能剩下^ 95                 int tt1 = *que1.begin(); 96                 que1.pop_front(); 97                 int tt2 = *que1.begin(); 98                 que1.pop_front(); 99                 que1.push_front(get_num(tt2,tt1));100             }101     /*        else if(*que2.begin() == ‘>‘)102             {103                 INT tt = *que1.begin();104                 que1.pop_front();105                 tt *= tt;106                 tt %= MOD;107                 que1.push_front(tt);108                 que2.pop_front();109                 que2.pop_front();110             }*/111         }112         printf("%d\n",*que1.begin());113         que2.clear();114         que1.clear();115     }116     return 0;117 }
View Code


联系
我们