NOIP2005等价表达式
题目描述
明明进了中学之后,学到了代数表达式。有一天,他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式,然后列出了若干选项,每个选项也是一个代数表达式,题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。 这个题目手算很麻烦,因为明明对计算机编程很感兴趣,所以他想是不是可以用计算机来解决这个问题。假设你是明明,能完成这个任务吗?
这个选择题中的每个表达式都满足下面的性质:
1. 表达式只可能包含一个变量‘a’。
2. 表达式中出现的数都是正整数,而且都小于10000。
3. 表达式中可以包括四种运算‘+’(加),‘-’(减),‘*’(乘),‘^’(乘幂),以及小括号‘(’,‘)’。小括号的优先级最高,其次是‘^’,然后是‘*’,最后是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运算从左到右进行。(注意:运算符‘+’,‘-’,‘*’,‘^’以及小括号‘(’,‘)’都是英文字符)
4. 幂指数只可能是1到10之间的正整数(包括1和10)。
5. 表达式内部,头部或者尾部都可能有一些多余的空格。 下面是一些合理的表达式的例子: ((a^1) ^ 2)^3,a*a+a-a,((a+a)),9999+(a-a)*a,1 + (a -1)^3,1^10^9…… 对于30%的数据,表达式中只可能出现两种运算符‘+’和‘-’; 对于其它的数据,四种运算符‘+’,‘-’,‘*’,‘^’在表达式中都可能出现。 对于全部的数据,表达式中都可能出现小括号‘(’和‘)’。
输入
输入的第一行给出的是题干中的表达式。第二行是一个整数n(2 < = n < = 26),表示选项的个数。后面n行,每行包括一个选项中的表达式。这n个选项的标号分别是A,B,C,D…… 输入中的表达式的长度都不超过50个字符,而且保证选项中总有表达式和题干中的表达式是等价的。
输出
输出包括一行,这一行包括一系列选项的标号,表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列,而且之间没有空格。
样例输入
样例输出
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
#include <iostream> #include <cstring> #include <cstdio> using namespace std; long long check,result_t,final; long long num[50],op[50]; long long power(long long a,long long b) { long long k=1; for(int i=0;i<b;i++) k*=a; return k; } void cul(int p,int op) { if(op==0) num[p-1]=num[p-1]+num[p]; if(op==1) num[p-1]=num[p-1]-num[p]; if(op==2) num[p-1]=num[p-1]*num[p]; if(op==5) num[p-1]=power( num[p-1],num[p] ); } long long result(string str) { int op_nxt,//下一个操作符 len=str.length(), p=-1,q=-1; //数字栈,符号栈指针 long long num_nxt=0;//下个数字 for(int i=0;i<len;i++) { if(str[i]=='a') { num[++p]=check; } else if(str[i]>='0' && str[i]<='9') { num_nxt=num_nxt*10+(str[i]-'0'); } else if(str[i]!=' ') { if( num_nxt!=0) { num[++p]=num_nxt; num_nxt=0; } if(str[i]=='+') op_nxt=0; if(str[i]=='-') op_nxt=1; if(str[i]=='*') op_nxt=2; if(str[i]=='^') op_nxt= 5; if(str[i]=='(') op_nxt=6; if(str[i]==')') op_nxt=7; if(op_nxt==6) { op[++q]=op_nxt; } else if(op_nxt==7) { while(q>=0 && op[q--]!=6) { //从上一个无该右括号匹配的左括号开始处理括号內的表达式 cul(p--,op[q+1]); } } else { //优先级高的运算符出栈 while( q >= 0 && op[q] <= 5 && op[q]/2>=op_nxt/2) { cul(p--,op[q--]); } op[++q]=op_nxt; } } } //清空堆栈 if(num_nxt!=0) { num[++p]=num_nxt; num_nxt=0; } while(q>=0) { cul(p--,op[q--]); } return num[0]; } int main() { string str1,str2; int n; final=0; getline(cin,str1); cin>>n; getline(cin,str2); while(n--) { bool flag=true; getline(cin,str2); for (int i=10;i<=20;i++) { check=i; if (result(str1)!=result(str2)) { flag=false; break; } } if (flag) cout<<(char)('A'+final); final++; } cout<<endl; return 0; } |