Sicily 1149 等价表达式 (SOJ 1149)「中缀转后缀」

0.00 avg. rating (0% score) - 0 votes
转载请注明: 吹水小镇 | reetsee.com
原文链接地址: http://blog.reetsee.com/archives/36

这题乍一看觉得好蛋疼(广东话叫“DUM春”),我是要把所有的表达式都简化到最短,还是把所有表达式都展开到最长?最麻烦的就是有个变量a,好了下面是正文了。

——————————正文——————————

从这题我就学醒目了,类似近似的思想,从题干可以知道最高的次数是10···其实不是10,因为可以是这样:a^10^10^10^10…. 这样一直下去,从题干知道最长为50个字符,每个^10占3个字符,所以最多会有a^160,两条这样的曲线公共点个数的上界是160个,也就是说,对a进行161次试值,如果两个表达式相等,那么就可以认为两个表达式是等价的。

说多一句····到网上一搜可以发现,不少通过的代码使用3次试值若相等就判断表达式是相等的了,不过我个人还是觉得161次的试值是最保险的。

还有一点要注意的是,我一开始计算的是:10^10^10=10^10000000000,这样就悲剧了···哈哈。可能很多同学使用2来测试2^2^2的两种计算方法是否相等,但是这样计算出来相等是个巧合,可以直接假设要求的是a^b^c,对于两种运算顺序,取log,其中一个结果是(b^c)*log(a),另外一个是b*c*log(a),所以两种运算顺序得到的结果是不一样的。

这样就解决表达式的判断问题了。

然后就是怎么样计算表达式的值,很多的童鞋肯定看过中缀转后缀表达式,最常用的方式是边扫描边计算,扫描到最后,就刚好计算完表达式。在做这题时,我脑袋抽了一下,我想既然每个表达式要计算161次,那不如我先把整个后缀表达式求出来,然后计算的时候直接扫描后缀表达式就好了,就不用每次扫描原串,然后进行转换·····但是其实两种做法都要扫描161次字符串···所以是差不多的。我发现这个问题的就是就是在我写这篇博客的时候,果然写博客有助于思考·····不过我之前的程序已经写完了,也懒得改,大概多了20行,不算太多,思路也蛮清晰的。

在运算符里面,我习惯加上“#”符号,作为符号栈的开始符号或者最终字符串的结束符号,符号优先矩阵如下:

符号优先矩阵

其实有个问题,就是做题时需不需要用高精度?从题意来看是要的,不过用long long来做过了,就不管它了。

对于a的试值,你可以自己找161个值,或者直接从0~160就可以了,不过我是选了-80~80。

下面就是代码了:

#include<iostream>
#include<stdio.h>
#include<string>
#include<cstring>
using namespace std;
string s0,s1;
int n;
long long a0[200],a1[200];
string nn[1000];
char op[1000]; //数字栈,符号栈
int nnn,opn;
bool m[7][7]={//算符优先级
    {0,0,0,0,1,0,1},
    {0,0,0,0,1,0,1},
    {1,1,0,0,1,0,1},
    {1,1,1,0,1,0,1},
    {1,1,1,1,1,1,1},
    {0,0,0,0,1,0,0},
    {0,0,0,0,0,0,1}
};//+ - * ^ ( ) #
long long power(long long aa, long long bb)
{
    if(bb==0) return 1;
    return aa*power(aa, bb-1);
}
long long comp(long long x, long long y, char c)
{
    switch(c)
    {
        case '+': return x+y;
        case '-': return x-y;
        case '*': return x*y;
        case '^': return power(x,y);
    }
}
void compute(string s, long long a[])
{
    long long sta[100];
    int stan;
    for(long long digit=-80;digit<=80;digit++)
    {
         stan=0;
     for(int i=0;i<s.size();/*在循环体中i会累加*/)
     {
             sta[stan++]=0;
       while(s[i]!='@')
             {
                 if(s[i]=='a')
                  sta[stan-1]=digit;
                 else
                     sta[stan-1]=sta[stan-1]*10+(s[i]-'0');
                 i++;
             }
             i++;
             while(!(isdigit(s[i])||s[i]=='a'||i>=s.size()))
               sta[--stan-1]=comp(sta[stan-1],sta[stan],s[i++]);
         }
         a[digit+80]=sta[0];
    }
}
int cast(char c)
{
    switch(c)
    {
        case '+': return 0; 
        case '-': return 1;
        case '*': return 2;
        case '^': return 3;
        case '(': return 4;
        case ')': return 5;
        case '#': return 6;
    }
}
bool pre(char c1, char c2)
{
    return m[cast(c1)][cast(c2)];
}
string postexp(string s)
{
    string tmp;
	nnn=opn=0;
    op[opn++]='#';
    for(int i=0;i<s.size();++i)
    {
        if(s[i]==' ')
         continue;
        if(isdigit(s[i])||s[i]=='a')
        {
			 tmp="";
             for(;isdigit(s[i])||s[i]=='a';++i)
              tmp.append(1,s[i]);
             tmp.append(1,'@');//数字之间的分割符号
             --i;
             nn[nnn++]=tmp;
        }
        else
        {
			 if(s[i]!=')' && pre(s[i],op[opn-1]))//优先级高压栈
               op[opn++]=s[i];
             else
             {
				 while(!pre(s[i],op[opn-1]))
                 {
                    nn[--nnn].append(1,op[--opn]);
					nn[nnn-1]+=nn[nnn];
                 }
                 if(s[i]==')')
                  opn--;
                 else
                  op[opn++]=s[i];
             }
        }
    }
    return nn[0];//得到后缀表达式
}
int main()
{
    //freopen("in","r",stdin);
    //freopen("out","w",stdout);
    char tt;
    string ans="";  //最终结果
    getline(cin,s0);
    s0=postexp(s0+"#");  //将s0变成后缀表达
	compute(s0,a0);      //代入11个数计算结果存入a0
    cin>>n;
    scanf("%c",&tt);
    for(int lll=0;lll<n;++lll)
    {
        getline(cin,s1);
        s1=postexp(s1+"#"); //将s1变成后缀表达
		compute(s1,a1);
        int i;
        for(i=0;i<161;++i)
		if(a0[i]!=a1[i])
          break;
        if(i==161)
         ans.append(1,'A'+lll);
    }
  cout<<ans<<endl;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注