这道题把我恶心到了。。。
暴力的思路是用模拟来做:
1.用两个栈来存储数字和操作;
2.每次计算,数字栈弹出数字,操作栈弹出操作;
3.计算结果压入数字栈;
4.最终结果是数字栈栈顶。
要考虑几种情况:
1.遇到“S”,“平方”操作应当入栈;
2.遇到数字,截取数字部分,转化为整型,压入数字栈;
3.遇到“>”,有几种情况要考虑:
a.如果下一位也是“>”,再下一位是“S”或者数字,“右移”操作入栈;
b.如果不是,则是平方操作,弹出一个数字进行计算,之后,检查操作栈顶是否为“右移”,如果是,还要弹出数字计算右移之后才能将结果压入数字栈。
4.每次弹出前要检查是否栈空。
在这里非常感谢工大的孩纸夏笑声,半夜还帮我debug真是感激不尽,AC全靠他!
AC代码:
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <assert.h> #include <algorithm> #define MAX 1234567890 #define MIN -1234567890 #define eps 1e-8 #define MOD 1000000007 using namespace std; const int maxn = 2000000+5; int i, k; int OPE[] = {1, 2}; /// 1 代表平方,2 代表右移 char tmp[maxn]; char str[maxn]; ///无空格的表达式 int num[maxn]; ///数字栈 int ope[maxn]; ///操作栈 int numptr; ///指向数字栈顶 int opeptr; ///指向操作栈顶 ///将表达式中的数字截取下来,并转化为整型,最后i指针指向数字最后一位 int number() { int t = 0; char n[108]; memset(n, 0, sizeof(n)); while (str[i] >= '0' && str[i] <= '9') { n[t++] = str[i++];} n[t] = '\0'; i--; return atoi(n); } ///右移,之后数字栈弹出栈顶(右移位数),再弹出新栈顶(被右移的数),计算结果压回栈中,数字指针-1指向栈顶 void rightmove() { opeptr--; int temp1 = num[numptr--],temp2 = num[numptr--]; while(temp1--) { temp2 = temp2 >> 1; if(temp2 == 0) { num[++numptr] = 0; return; } } num[++numptr] = temp2; } int main() { while (gets(tmp) && tmp[0] != '#') { int ans = 0; int lent = strlen(tmp); memset(str, 0, sizeof(str)); ///除去空格 for (i = 0, k = 0; i < lent; i++) { if(tmp[i] != ' ') str[k++] = tmp[i]; } str[k] = '\0'; int len = k; numptr = -1; opeptr = -1; for (i = 0; i < len; i++) { ///将 平方 压入操作栈,操作指针+1指向栈顶,i指针跳过 '<' if(str[i] == 'S') { ope[++opeptr] = 1; i++; } ///将数字压入数字栈,数字指针+1指向栈顶,i指针将指向数字最后一位 else if(str[i] >= '0' && str[i] <= '9') { num[++numptr] = number(); ///如果 右移 在操作栈顶,计算 while (opeptr >= 0 && ope[opeptr] == 2) { rightmove(); } } else if(str[i] == '>') { ///如果新操作为 右移 if(str[i+1] == '>' && (i + 2) < len && (str[i+2] == 'S' || (str[i+2] >= '0' && str[i+2] <= '9'))) { ///将 右移 压入操作栈,操作指针+1指向栈顶,i指针跳过 '>' if(str[i+2] == 'S') { ope[++opeptr] = 2; i++; } else { ///将 右移 压入操作栈,操作指针+1指向栈顶,i指针跳过 '>'和数字,停在最后一位数字上,并计算 i+= 2; ope[++opeptr] = 2; num[++numptr] = number(); rightmove(); } ///新操作为 平方,计算,修改数字栈顶,弹出 右移 并且操作指针-1指向栈顶 } else { long long s = num[numptr]; s = s * s % MOD; num[numptr] = s; ope[opeptr--] = 0; while(opeptr >= 0 && ope[opeptr] == 2) rightmove(); } } } printf("%d\n", num[numptr]); } return 0; }