问题 F: 真值表(Ⅰ）
题目描述
同学们都学习过《离散数学》这门课程，知道真值表是用于逻辑中的一类数学用表，用来计算逻辑表示式在每一个逻辑变量取值组合下的值。在这里我们给定一个逻辑表达式，要求生成对应的真值表。提示一下，数据结构教材中介绍了数学表达式的处理算法，可以将其改造以适用于我们的项目。
项目分为三个子项目，第一部分为词法分析，即将逻辑表达式分隔为多个词(token)。下面给出两个例子。
例一：
逻辑表达式p^q中有p、^和q共三个词;
例二：
逻辑表达式p^(q^r)中有p、^、（、q、^、r和）共七个词。
逻辑联结词有五个，见下表，这些符号和教材上的有所不同，主要是为了方便。
否定 合取 析取 蕴涵 等值
! ^ || -> <->
引入括号，规定基本逻辑联接词优先顺序从高到低依次是：( )、!、∧、||、->、<->。 同一优先级，从左到右顺序进行。
输入
输入由多行组成，每行都是一个正确的逻辑表达式。
逻辑表达式小于100个字符。
一个正确的逻辑表达式可以包含小写字母，空格和逻辑联结词（含括号）。单个小写字母表示一个逻辑变量，一个表达式中逻辑变量的个数不超过10。空格作为分隔符, 不是词，同一个词的字符之间不能有空格。
输出
每一个逻辑表达式产生如下的输出：
第一行按顺序输出表达式中的所有词。每个词之间用空格分开。
第二行按字母序输出表达式中的所有逻辑变量，用空格分开。
第三行开始输出逻辑变量值的所有组合情况。
具体见样例。
样例输入 Copy
p
p->q
p||q
样例输出 Copy
p
p
1
0
p -> q
p q
1 1
1 0
0 1
0 0
p || q
p q
1 1
1 0
0 1
0 0
在codeblocks上测试了几个数据，显示正常，提交到oj上显示输出超限。
#include
#include
#include
#include
using namespace std;
void truth(int m,int n,int a[])
{
int i;
if(m==n)
{
for(i=0; i<n; i++)
{
if(i==n-1)
cout<<a[i];
else
cout<<a[i]<<" ";
}
cout<<endl;
return;
}
else
{
a[m]=1;
truth(m+1,n,a);
a[m]=0;
truth(m+1,n,a);
}
}
char s[100],zimu[10],bian[10];
int main()
{
int i,j=0,k,l;
int m=0,min,temp;
int a[100],b=0,flag=1;
while(cin.get(s,100))//解决输入有空格
{
l=strlen(s);
for(i=0; i<=l; i++)
{
if(s[i]>='a'&&s[i]<='z')
{
zimu[j]=s[i];//将表达式中字母全部存储起来
j++;
if(i==0)//字母在首
{
if(l==1)
cout<<s[i];
else
cout<<s[i]<<" ";
}
else if(i==l-1)//字母在尾
{
cout<<s[i];
}
else //一般情况
cout<<s[i]<<" ";
}
else if(s[i]=='('||s[i]==')'||s[i]=='!'||s[i]=='^'||s[i]=='|'||s[i]=='<'||s[i]=='-'||s[i]=='>')
{
cout<<s[i];
if(s[i]=='('||s[i]==')'||s[i]=='!'||s[i]=='^'||s[i]=='>'||s[i]=='|'&&s[i-1]=='|')
cout<<" ";
}
}
zimu[j]='\0';
cout<<endl;
for(i=0; i<j; i++)
{
for(k=0; k<i+1; k++)
{
if(zimu[i]==zimu[k]&&i!=k)
{
//将已经出现过的字母丢弃
flag=0;
break;
}
}
if(flag==1)
{
bian[m]=zimu[i];//数组r存储逻辑变量
m++;//变量个数
}
flag=1;
}
for(i=0; i<m; i++)
{
min=i;//将变量升序排列
for(k=i+1; k<m; k++)
{
if(bian[k]<bian[min])
min=k;
}
temp=bian[i];bian[i]=bian[min];bian[min]=temp;
}
for(i=0; i<m; i++)
{
if(i==m-1)
cout<<bian[i];
else
cout<<bian[i]<<" ";
}
cout<<endl;
truth(b,m,a);
i=0;b=0;flag=1;m=0;
cin.get();//读取换行符
}
return 0;
}