东6宿舍灵异事件(0322)
Time limit(ms): 1000 Memory limit(kb): 65535 Submission: 88 Accepted: 31
Description
将军听说最近东6闹鬼了，作为一个无神论者，将军当然不相信。但是这个传言已经泛滥了，许多人都在说这个事情，将军从每个人那里听到一个传言，将军可以容易的就知道这个传言是真还是假，但是当一大堆消息组合起来，将军就不知道了，所以将军就找到了你。
提供两种组合方式：
A&B:代表A和B都为真的时候，A和B组合起来为真，否则为假
A|B:代表A和B里面至少有1个为真的时候，A和B组合起来为真，否则为假
优先级顺序 “括号”>“&”>“|”
例如：a&b|(a|b&c)，a=真，b=假，c=真；
那么上式可以这样转化
真&假 | （真|假&真）
假 | （真|假）
假 | 真
真
提供两种组合方式：
A&B:代表A和B都为真的时候，A和B组合起来为真，否则为假
A|B:代表A和B里面至少有1个为真的时候，A和B组合起来为真，否则为假
优先级顺序 “括号”>“&”>“|”
例如：a&b|(a|b&c)，a=真，b=假，c=真；
那么上式可以这样转化
真&假 | （真|假&真）
假 | （真|假）
假 | 真
真
Input
有多组测试数据，每组测试数据共两行，第一行是一个逻辑范式，数据不用判错；
接下来三个字符，以空格隔开，分表代表a,b,c的真假（T/F）;
接下来三个字符，以空格隔开，分表代表a,b,c的真假（T/F）;
Output
对于每一组数据，输出最终的结果（TRUE or FALSE）;
Sample Input
a&b|(a|b&c)
T F T
Sample Output
TRUE
Hint
SCPC - ChenYi
#include<stdio.h>
#include<string.h> struct
{
char ch;
int pri;
}lpri[]={{'=',},{'(',},{'+',},{'*',},{')',}},rpri[]={{'=',},{'(',},{'+',},{'*',},{')',}}; void Change(char *a)
{
if(*a=='T')
*a='';
else
*a='';
} void Transform(char exp[],char a,char b,char c)
{
int len,i;
len=strlen(exp);
for(i=;i<len;i++)
{
if(exp[i]=='a')
exp[i]=a;
if(exp[i]=='b')
exp[i]=b;
if(exp[i]=='c')
exp[i]=c;
if(exp[i]=='&')
exp[i]='*';
if(exp[i]=='|')
exp[i]='+';
}
} int Lpri(char ch)
{
int i;
for(i=;i<;i++)
{
if(ch==lpri[i].ch)
{
return lpri[i].pri;
}
}
} int Rpri(char ch)
{
int i;
for(i=;i<;i++)
{
if(ch==rpri[i].ch)
{
return rpri[i].pri;
}
}
} void expTOpostexp(char exp[],char postexp[])
{
int len,top=-,t=,i;
char op[];
len=strlen(exp);
for(i=;i<len;)
{
if(exp[i]==''||exp[i]=='')
{
postexp[t++]=exp[i++];
}
else
if(Lpri(op[top])<Rpri(exp[i])||top==-)//最开始栈顶是 -1
{
op[++top]=exp[i++];
}
else
if(Lpri(op[top])>Rpri(exp[i]))
{
postexp[t++]=op[top--];
}
else
if(Lpri(op[top])==Rpri(exp[i]))
{
top--;
i++;
}
}
for(i=top;i>-;i--)//top就是栈顶的指针
{
postexp[t++]=op[top--];
}
postexp[t]='\0';
//printf("postexp:%s\n",postexp);
} int Judge(char postexp[])
{
int top=-,len,i,num[],a,b;
len=strlen(postexp);
for(i=;i<len;i++)
{
if(postexp[i]==''||postexp[i]=='')
num[++top]=postexp[i]-'';
if(postexp[i]=='+')
{
a=num[top--];
b=num[top];
num[top]=a+b;
}
if(postexp[i]=='*')
{
a=num[top--];
b=num[top];
num[top]=a*b;
}
}
return num[];
} int main()
{
char exp[],postexp[];
char a,b,c;
while(scanf("%s",exp)!=EOF)
{
getchar();
scanf("%c",&a);
getchar();
scanf("%c",&b);
getchar();
scanf("%c",&c);
Change(&a);
Change(&b);
Change(&c);
Transform(exp,a,b,c);
//printf("exp:%s\n",exp);
expTOpostexp(exp,postexp);
if(Judge(postexp))
printf("TRUE\n");
else
printf("FALSE\n");
}
return ;
}
注：与运算可以看成是 *（乘法），或运算可看成是 +（加法），FALSE=0 TRUE=1，中缀表达式变后缀表达式并求值。