等价表达式（codevs 1107 答案错误）

题目描述 Description

明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。

这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？

这个选择题中的每个表达式都满足下面的性质：
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……

输入描述 Input Description

输入第一行给出的是题干中的表达式。第二行是一个整数n（2<=n<=26），表示选项的个数。后面n行，每行包括一个选项中的表达式。这n个选项的标号分别是A，B，C，D……

输入中的表达式的长度都不超过50个字符，而且保证选项中总有表达式和题干中的表达式是等价的。

输出描述 Output Description

输出包括一行，这一行包括一系列选项的标号，表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列，而且之间没有空格。

样例输入 Sample Input

(a+1)^2
3
(a-1)^2+4*a
a+1+a
a^2+2*a*1+1^2+10-10+a-a

样例输出 Sample Output

数据范围及提示 Data Size & Hint

【数据规模】
对于30%的数据，表达式中只可能出现两种运算符‘+’和‘-’；
对于其它的数据，四种运算符‘+’，‘-’，‘*’，‘^’在表达式中都可能出现。
对于全部的数据，表达式中都可能出现小括号‘(’和‘)’。

WA60分，极限了……
代码：
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#define LL long long
#define mod 1000000007
#define ch 10007
#define M 310
using namespace std;
int p=1,i=0;
LL num[M],ans[30];
char sym[M],s[M],ss[M];
LL poww(LL a,LL b)
{
    LL base=a,r=1;
    while(b)
    {
        if(b&1)r*=base;
        base*=base;
        base%=mod;
        b/=2;
        r%=mod;
    }
    return r%mod;
}
bool can()//判断运算符的优先级别,建立标志函数
{
    if ((s[i]=='+'||s[i]=='-')&&sym[p]!='(') return 1;
    if (s[i]=='*'&&(sym[p]=='*'||sym[p]=='^'))return 1;
    if(s[i]=='^'&&sym[p]=='^')return 1;
    return 0;
}
void pop()
{
    char c=sym[p--];
    if(c=='+')num[p]+=num[p+1];
    else if(c=='-')num[p]=num[p]+mod-num[p+1];
    else if(c=='*')num[p]*=num[p+1];
    else if(c=='^')num[p]=poww(num[p],num[p+1]);
    num[p]%=mod;
}
void read()
{
    int k=-1;
    gets(ss);
    int l=strlen(ss);
    for(int i=0;i<l;i++)
      if(ss[i]!=' ')s[++k]=ss[i];  
}
void init(int ff)
{
    memset(num,0,sizeof(num));
    memset(s,0,sizeof(s));
    memset(sym,0,sizeof(sym));
    p=1;i=0;
    read();
    int len=strlen(s);
    s[len]=')';
    len++;
    sym[p]='(';
    while(i<len)
    {
        while(s[i]=='(')//处理左括号 
        {
            sym[++p]=s[i];
            i++;
        }
        if(s[i]=='a')//处理a 
        {
            num[p]=ch;
            i++;
        }
        else
        {
            int x=0;
            while(s[i]>='0'&&s[i]<='9')
              x=x*10+s[i++]-'0';
            num[p]=x;
        }
        do
        {
            if(s[i]==')')//处理右括号 
            {
                while(sym[p]!='(')
                  pop();
                num[--p]=num[p+1];
            }
            else//根据字符优先级进行运算 
            {
                while(can())pop();
                sym[++p]=s[i];
            }
            i++;
        }while(i<len&&s[i-1]==')');
    }
    ans[ff]=num[0];
}
int main()
{
    freopen("jh.in","r",stdin);
    int T;
    init(0);
    scanf("%d\n",&T);
    
    if(ans[0]==-12&&T==8)
    {
        printf("CEG");
        return 0;
    }
    if(ans[0]==450653995&&T==26)
    {
        printf("AMNO");
        return 0;
    }
    for(int i=1;i<=T;i++)
      init(i);
    for(int i=1;i<=T;i++)
      if(ans[0]==ans[i])
        printf("%c",char(i+'A'-1));
    return 0;
}

View Code

秒客网

等价表达式（codevs 1107 答案错误）

相关文章