数据结构与算法课程设计报告重言式判别.doc

合肥学院
计算机科学与技术系

课程设计报告
2016～2017学年第1学期

课程
数据结构与算法
课程设计题目名称
重言式的判别
学生姓名

学号

专业班级
计算机科学与技术14级1班
指导教师

2016年9月

一、题目
【问题描述】
一个逻辑表达式如果对于其变元的任一种取值都为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式；然而，更多的情况下，既非重言式，也非矛盾式。试写一个程序，通过真值表判别一个逻辑表达式属于上述哪一类。
【基本要求】
(1) 逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括 "|"，"&" 和 "~"，分别表示或、与和非，运算优先程度递增，但可由括号改变，即括号内的运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有多个空格符。
(2) 若是重言式或矛盾式，可以只显示"True forever"，或"False forever"，否则显示 "Satisfactible" 以及变量名序列，与用户交互。若用户对表达式中变元取定一组值，程序就求出并显示逻辑表达式的值。
【测试数据】
(1) (A|~A)&(B|~B)
(2) (A&~A)&C
(3) A|B|C|D|E|~A
(4) A&B&C&~B
(5) (A|B)&(A|~B)
(6) A&~B|~A&B;O ,0;0,1;1,0;1,1 。
二、问题分析
1、 一个逻辑表达式如果对于其变元的任一种取值均为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式，若对于其变元的任一种取值既有真，又有假，则称其为可满足式。写一个程序通过真值表判别一个逻辑表达式属于上述哪一类。基本要求如下：
1) 逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括“|”、“&”、“~”，分别表示或、与、非，运算优先程度递增，但可有括号改变，即括号内的运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有多个空格符。
2) 若是重言式或矛盾式，可以只显示“True Forever”或“False Forever”，否则显示运算中每种赋值和与其相对应的表达式的值。
2、通过真值表判别逻辑表达式是否为重言式，需解决以下问题：
1) 对逻辑表达式中空格符的处理。
为了方便对逻辑表达式进行扫描判断，应先去掉表达式中的空格符。
2) 算符的优先级问题
在带括号的表达式中，界限符包括左右括号以及表达式起始、结束符“#”。对于一个简单的表达式求值运算规则如下：（1）从左至右依次计算。（2）先取反，然后相与，后相或。（3）先括号内，后括号外。
为统一算法的描述，将运算符和界限符统称为算符。这样，算符集为{~，&，|，（，），#}。根据上述3条规则，两个前后相继出现的算符a1，a2间的优先关系可以归纳如下：
（1） 若a1,a2同为“&”或同为“|”，则算符a1的优先级大于a2。
（2） “~”、“&”、“|”的优先级依次减小。
（3） 由于先括号内，后括号外，若a1为“|”、“&”、“~”，a2为“（”；或者，a1为“（”，而a2为“|”、“&”、“~”，则a1的优先级小于a2。
（4） 同理，若a1为“|”、“&”、“~”，a2为“）”；或者，a1为“）”，而a2为“|”、“&”、“~”，则a1的优先级大于a2。
（5） 若a1、a2同为“（”，则a1的优先级小于a2；若a1、a2同为“）”，则a1的优先级大于a2。
（6） 表达式的起始、结束符“#”的优先级小于其他所有合法出现的算符。
（7） 若a1为“（”，a2为“）”；或者，a1、a2同为“#”，则a1、a2优先级相同。
综上所述，将两个相继出现的算符a1、a2的优先关系进行归纳如表1所示。
表1 算符a1和a2间的优先关系
a1 a2
|
&
~
(
)
#
|
>
<
<
<
>
>
&
>
>
<
<
>
>
~
>
>
>
<
>
>
(
<
<
<
<
=
___
)
>
>
>
___
>
>
#
<
<
<
<
___
=
我们可以将逻辑表达式的计算类比算术表达式的计算，通常借助堆栈来实现按运算符的优先级完成表达式的求值计算。一个是存放运算符栈，另一个是存放变量或中间结果栈。
（1） 首先初始化算符栈logic和变量栈，并将表达式的起始符“#”压入算符栈logic。
（2） 依次读入表达式中的每个字符。若是变量，则为其分配结构node的size大小的内存,强制转换为bitree类型，并将其压入变量栈variable；若是运算符，则为其分配结构node的size大小的内存,强制转换为bitree类型，并与运算符栈logic的栈顶算符进行优先级比较，并作如下处理：
① 若栈顶算符a1的优先级低于刚读入的算符a2，则将a2压入运算符栈logic。
② 若栈顶算符a1的优先级高于刚读入的算符a2，则将a1出栈，同时将变量栈variable出栈一次，得到变量A，再判断栈顶算符a1是否为“~”，如果a1不是“~”，则继续出栈变量栈variable一次，得到变量B，将a1作为根结点，B作为a1的左孩子，A作为a1的右孩子，并将根结点a1压入变量栈variable；如果栈顶算符a1是“~”，则将a1作为根结点，A作为a1的右孩子，a1的左孩子则为空，并将根结点a1压入变量栈。
③ 若栈顶算符a1优先级与刚读入的算符a2的优先级相同，说明左右括号相遇，或者是表达式的起始、结束符相遇，只需将栈顶算符（左括号或起始符）出栈即可；当运算符栈logic空时，算法结束
这样就可以将逻辑表达式构造成一棵完整二叉树，根结点是优先级最小的算符（除了括号和起始结束符，在构造二叉树的过程中已被脱去）。如(A|~A)&(B|~B)构造成的二叉树如图1所示

图1 表达式构造的二叉树
1) 变量的赋值问题
若只有1个变量，则有21种情况的赋值；若有2个变量，易知有22种情况的赋值；若有3各变量，则有23种情况的赋值，那么如果有n个变量，就有2n种情况的赋值。既然要对变量进行赋值，首先要找到逻辑表达式中的变量，并确定变量的个数。
2) 逻辑表达式取值的判断
由上述对运算符的优先级的分析可知，对逻辑表达式的计算，就是中序遍历由优先级确定的逻辑表达式构成的二叉树。
5）重言式的判别
可以将给变量的所有赋值的逻辑表达式的逻辑值相加，如果相加结果与2n相等，则为重言式；若相加结果为0，则为矛盾式；否则为可满足式。
本问题的关键和难点在于算符优先级的判断和二叉树的构造。
三、数据结构的选择和概要设计
1、数据结构的选择
通过问题分析可知，需要用到的数据结构有堆栈和二叉树。
1) 对于堆栈选用顺序栈结构来进行存放算符或变量，存放的都是二叉树的结点。设有两个堆栈，一个是存放运算符栈，另一个是存放变量或中间结果栈。
2) 对于二叉树，选用二叉树的链接存储结构，其结点存放得都是表达式中的元素。将表达式构造成一棵二叉树。
2、概要设计
从整体上可以分为三个模块：
第一个模块：属于堆栈和二叉树结点类型的定义
typedef struct stack //识别表达式使用的堆栈定义,它存放的都是树的结构
{ //栈中的元素都是树的结点结构
bitree *base; //栈底指针
bitree *top; //栈顶指针
int stacksize; //栈容量
}seqstack;
typedef struct node //根据表达式建立的二叉树的结点定义
{
char data;
struct node *lchild;
struct node *rchild;
}BiTNode,*bitree;
第二个模块：主要函数及其功能。
堆栈的创建
void creatstack(sqstack &st){}；
初始化栈
void setstack(seqstack &st){}；
进栈
void push(sqstack &st,bitree e){}；
出栈
void pop(sqstack &st,bitree &e){}；
将逻辑表达式中的元素转换为二叉树结点的形式，使栈中存储的都是二叉树的结点。
void creattree(char s[],bitree &tree){}；
通过优先级将逻辑表达式构造成一颗完整的二叉树
void create(bitree &zigen,bitree l,bitree r){}；
对逻辑表达式求值
int valuetree(bitree tree){}；
生成变量的各种取值组合
void creatzuhe(int n,int m,char a[]){}；
逻辑运算符的优先级判别，返回值为“<”、“>”、“=”
char youxianji(char m,char n){}；
第四个模块为于用户的交互
void user(){}；
流程图：
图2 程序流程图
开始
main
meun
输入表达式
1. 计算机
2. 用户
3. 3.返回
建树
建树
计算机穷举
用户输入变量值
输出结果
继续
结束
2
1
3
N
Y

四、算法思想
1、穷举法思想
通过真值表来判断重言式，需要一一给变量赋值，共有2^n中情况（n表示变量的个数），这里用到穷举的思想。
2、递归与分治思想
每给变量赋一组值，通过递归中序遍历二叉树求值，这里用到了递归与分治思想。
3、运算符的优先级判断思想（见问题分析算符的优先级问题分析第5页）
五、详细设计和主要编码段
首先将用户输入的逻辑表达式存到char *str当中，然后去除逻辑表达式中的空格符。
for(;*pstr!=NULL;pstr++,n++){
if(str[n]!=' ') stri[i++]=*pstr; //去除表达式中的空格
}
此时stri当中存储的就是没有空格符的逻辑表达式。通过问题分析，需找到表达式中的变量，并确定变量的个数。下面的代码就是实现此功能。
for(int k=0;k< strlen(stri);k++)
if(stri[k]>=65&&stri[k]<=90)//找到变量
{
int mark=0; //标记变量
for(int j=0;j<m;j++)
{
if(bl[j]==stri[k])//将找到的变量与bl[]中已找到过的变量比较，若相等则将变量标记置为1，表示找到的变量在前面已出现过
{
mark=1;break;
}
}
if(mark==0)//若标记为0，表示找到的变量没有重复，并将其记录到bl[]中，变量个数m加1。
{
bl[m]=str[k];
m++;//m是变量个数
}
}
此时bl[]当中存储的就是变量，m就是变量个数，那么变量赋值的情况就有2m种。
下面对生成变量的各种取值组合的算法进行分析和说明。int zuhe[30]用来存储变量的取值组合，为了方便说明，采用两个变量进行算法叙述。
A
B
第n次数
0
0
0
0
1
1
1
0
2
1
1
3
表2 变量赋值实例
从表2可以发现给变量赋值的次数n与变量的取值组合成的二进制数相等，能得到一个规律：变量的取值组合zuhe[]二进制数（从低位到高位）的第i位数取值等于(n>>i)%2。用一下代码可以实现第n次对变量的赋值组合
int lzp=m;
for(int i=0;i<m;i++)
{
zuhe[bl[lzp]-65]=(n>>i)%2;
lzp--;
}
下面说明优先级的判断。char bijiao[7][7]用来存放算符间的优先关系表中的数据。
int i,j;
bijiao[7][7]={
' ','|','&','~','(',')','#', //二维数组比较优先级先后
'|','>','<','<','<','>','>',
'&','>','>','<','<','>','>',
'~','>','>','>','<','>','>',
'(','<','<','<','<','=',' ',
')','>','>','>',' ','>','>',
'#','<','<','<','<',' ','='};
for(i=0;i<7;i++)
if(bijiao[0][i]==a2) //找到a2运算符的列号
break;
for(j=0;j<7;j++) //找到a1运算符的行号
if(bijiao[j][0]==a1)
break;
return bijiao[j][i]; //返回优先级的符号:>、<、=
下面说明将表达式构成二叉树的过程。s=stri是逻辑表达式的首地址。
while(*s!=NULL) //循环条件，为空则扫描结束
{
if(int(*s)>=65&&int(*s)<=90) //读取的是变量
{
variables=(bitree)malloc(sizeof(node));
//分配结构node的size大小的内存,强制转换为bitree类型
variables->data=*s;
push(variable,variables); //入变量栈
}
else if(int(*s)>90||int(*s)<65) //读取的逻辑运算符
{
gettop(logic,e); //取运算符栈的栈顶元素进行优先级比较
switch(youxianji(*s,e->data))
{
case '<': //栈顶的运算符优先级低,逻辑运算符进栈
logics=(bitree)malloc(sizeof(node));
//分配结构node的size大小的内存,强制转换为bitree类型
logics->data=*s;
push(logic,logics);
break;
case '=':
pop(logic,kuohao); //括号并接受下一个字符
break;
case '>': //栈顶的运算符优先级高,变量出栈运算
pop(logic,g); //弹出逻辑运算符g
pop(variable,a); //弹出变量a
b=NULL; //'~'只有右子树
if(g->data!='~')
pop(variable,b); //出栈变量b
create(g,b,a); //将变量b作为g的左子树，a作为g的右子树，若a是变量，将其左、右孩子置空，若b是变量，将其左、右孩子置空
push(variable,g);//将临时的根g作为新的变量压入变量栈中
gettop(logic,e);//取变量栈栈顶算符e
if(*s!='#'&&*s!=')'&&youxianji(*s,e->data)!='>') //如果读入算符*s不是结束符也不是右括号，并且栈顶算符优先级小于读入算符优先级将读入的算符入栈
{
logics=(bitree)malloc(sizeof(node));//分配结构node的size大小的内存,强制转换为bitree类型
logics->data=*s;
push(logic,logics); //逻辑运算符入栈
}
else s=s-1;//若栈顶算符优先级大于读入算符优先级或读入算符为“#”或“）”
break;
}
}
s++;
}
tree=g;
}
下面说明对逻辑表达式的求值过程。中序遍历二叉树
int valuetree(bitree tree) //根据变量的取值组合并利用逻辑表达式的性质对树进行求值
{
if(!tree) return 0; //遇到空的结点
else if(tree->data!='|'&&tree->data!='&'&&tree->data!='~') //找到的是变量
return zuhe[int(tree->data)-65]; //返回对应变量赋予的值（0或1）
else if(int(tree->data)<65||int(tree->data)>90) //找到的是运算符
switch(tree->data)
{
case '|':
return(valuetree(tree->lchild)||valuetree(tree->rchild)); //递归调用
break;
case '&':
return(valuetree(tree->lchild)&&valuetree(tree->rchild)); //递归调用
break;
case '~':
return(!valuetree(tree->rchild)); //递归调用
break;
default: return 0;
}
else return 0;
}
最后说明判断逻辑表达式或为重言式，或为矛盾式或为可满足式。每给变量一组值，调用一次int valuetree(bitree tree)函数求其逻辑值，需要给变量2n组值，则需求其逻辑值2n次，把每次求得的逻辑值相加，得到数字SUM，若SUM=2n,则逻辑表达式为重言式；若SUM=0，则逻辑表达式为矛盾式；若0<SUM<2n,则逻辑表达式为可满足式。若表达式为可满足式，则输出运算中每种赋值和与其相对应的表达式的值。
六、上机调试情况记录
出现的问题及解决方法
问题：
a) 测试题目给定的数据A&~B|~A&B，发现其结果不正确，
原因是没有正确的解决优先级，建树的过程中，运算符入栈时，如果检测到的表达式中的算符优先级低于栈顶的优先级，则应出栈运算符，在出栈运算符后，如果检测到的表达式中的算符（并且算符不是结束符’#’也不是’）’）的优先级依旧低于栈顶算符,应该继续算符出栈，而不是算符入栈。
解决方法：将算符入栈条件if(*s!='#'&&*s!=')')改为
if(*s!='#'&&*s!=')'&&youxianji(*s,e->data)!='>')
b) 测试数据时如果逻辑表达式的变量不是递增按顺序输入（如：A&B&F&G），结果会出错。
原因是在给变量组合赋值时，赋值组合数组的小标是递增顺序的，而在递归调用求值函数时用到的变量组合值数组的下标却是与变量的ACS编码有关的，两者对不上。
解决方法：在生成变量组合数时，将zuhe[i]=(n>>i)%2改为zuhe[a[lzp]-65]=(n>>i)%2;
七、测试用例、结果及其算法性能分析
（一）、初始界面

（二）、测试用例及结果
(1) (A|~A)&(B|~B)（重言式）

(2) (A&~A)&C（矛盾式）

(3) A|B|C|D|E|~A（重言式）

(4) A&B&C&~B（矛盾式）

(5) (A|B)&(A|~B)（可满足式）

(6) A&~B|~A&B;O ,0;0,1;1,0;1,1 。（可满足式）

通过测试验证结果都正确，实现了题目的要求。
（三）、算法性能分析
1、算法的时间性能分析
用穷举法列真值表有2^n（n为变量个数）种情况，为每一种情况的所有变量赋值的次数为n,则为所有情况的变量赋值次数为n*2^n次，即在函数void creatzuhe(int n,int m,char a[])中的语句需执行n*2^n次，是整个算法当中频度最大的语句，由于算法的时间复杂度考虑的只是对于问题规模n的增长率，所以该算法的时间复杂度为T(n)=O(n*2^n)。
2、算法的空间性能分析
本算法的空间复杂度较低，需要一个zuhe[30]的数组来存放变量的取值，一个大小为M的数组存放逻辑表达式，一个M的二叉树链接存放逻辑表达式构成的树结点。两个堆栈长度不超过M，所以空间复杂度为O（M）。
（四）、经验和体会
初拿到本问题，就觉得与学过的带括号的算术表达式计算问题相似。其最关键的是算符优先级的判断，可以将它类比算术表达式列出同数据结构与算法课本上表4-1类似的算符的优先关系表表1。通过查表来判断算符的优先级就变得简易了。观察逻辑表达式可以发现，对逻辑表达式的计算类似于对二叉树的中序遍历，可以将逻辑表达式通过优先级将其构造成一棵二叉树。当然最终实现过程中有很多细节问题需要注意，通过一步步测试、调试程序找到问题，并改善，知道最终解决问题。
八、用户使用说明
1、运行程序进入显示文本方式的用户界面；
2、根据提示输入要判别的逻辑表达式（表达式中可以有空格）
3、输入表达式后出现菜单选项，用户可以选择程序自动穷举赋值法和用户赋值法进行判别；
4、在显示相应结果后，根据提示信息在进行下一步。
九、参考文献
[1] 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2006年5月。
[2] 严蔚敏，吴伟明. 数据结构. 北京：清华大学出版社，2007年5月。
[3] 李春葆. 数据结构教程. 北京：清华大学出版社，2003年5月。
[4]蹇强，罗宇. 数据结构. 北京：邮电大学出版社，2004年5月。
[5] 金远平. 《数据结构》（C++描述. 北京：清华大学出版社 2005年5月。
十、附录（完整代码）
#include "stdlib.h" // 调用stdlib.h 里面的函数 `
#include "stdio.h"
#include "iostream.h"
#include "string.h"//包含字符串处理函数的头文件
#include "math.h"//调用数学函数库
#include "iomanip.h"//是I/O流控制头文件
#define maxsize 100
int zuhe[maxsize]; //变量的取值组合数组定义
int N; //变量个数
typedef struct node //根据表达式建立的二叉树的结点定义
{
char data;
struct node *lchild;
struct node *rchild;
}BiTNode,*bitree;
typedef struct stack //识别表达式使用的堆栈定义,它存放的都是树的结构
{ //栈中的元素都是树的结点结构
bitree *base; //栈底指针
bitree *top; //栈顶指针
int stacksize; //栈容量
}seqstack;
void creatzuhe(int n,int m,char a[])//生成变量的组合数
{
int lzp=m-1;
for(int i=0;i<m;i++)
{
zuhe[a[lzp]-65]=(n>>i)%2;
lzp--;
}
}
void create(bitree &f,bitree l,bitree r) //自底向上地根据运算符地优先级来建立分子树函数
{
f->lchild=l; //分树的链接
f->rchild=r; //分树的链接
if(l&&r)
{
if(int(l->data)>=65&&int(l->data)<=90) //左子树
{
l->lchild=NULL;
l->rchild=NULL;
}
if(int(r->data)>=65&&int(r->data)<=90) //右子树
{
r->lchild=NULL;
r->rchild=NULL;
}
}
}
char youxianji(char m,char n) //逻辑运算符的优先级判别
{
int i,j;
char bijiao[7][7]={
' ','|','&','~','(',')','#', //二维数组比较优先级先后
'|','>','<','<','<','>','>',
'&','>','>','<','<','>','>',
'~','>','>','>','<','>','>',
'(','<','<','<','<','=',' ',
')','>','>','>',' ','>','>',
'#','<','<','<','<',' ','='};
for(i=0;i<7;i++)
if(bijiao[0][i]==m) //找到m运算符的列号
break;
for(j=0;j<7;j++) //找到n运算符的行号
if(bijiao[j][0]==n)
break;
return bijiao[j][i]; //返回优先级的符号:>、<、=
}
void setstack(seqstack &st) //初始化栈
{
st.base=(bitree *)malloc(maxsize*sizeof(node));
st.top=st.base;
st.stacksize=maxsize; //栈容量
}
void push(seqstack &st,bitree e) //入栈
{
if(st.top-st.base<st.stacksize) //符合条件入栈
{
*st.top=e;
st.top++;
}
else cout<<"ERROR!!!"<<endl; //不符合输出ERROR!!!
}
void pop(seqstack &st,bitree &e) //出栈
{
if(st.top==st.base) cout<<"ERROR!!!"<<endl; //不符合条件输出ERROR!!!
st.top--; //符合条件
e=*st.top;
}
void gettop(seqstack &st,bitree &e) //取栈顶元素
{
if(st.top==st.base) cout<<"ERROR!!!"<<endl//不符合条件输出ERROR!!!
e=*(st.top-1); //符合取栈顶元素
}
void creattree(char s[],bitree &tree) //根据逻辑表达式将数据存入二叉树中，定义两个栈
{
seqstack variable; //变量栈
seqstack logic; //逻辑运算符栈
setstack(variable); //变量栈初始化
setstack(logic); //逻辑运算符栈初始化
bitree logic1,variables,logics,e,a,b,g,kuohao;//定义栈中的元素,g为最后的二叉树的根
logic1=(bitree)malloc(sizeof(node));//分配结构node的size大小的内存,强制转换为bitree类型
logic1->data='#'; //将逻辑运算符栈的栈底元素设为'#'
push(logic,logic1); //将逻辑运算符栈入栈.
while(*s!=NULL)
{
if(int(*s)>=65&&int(*s)<=90) //读取的是变量
{
variables=(bitree)malloc(sizeof(node));
//分配结构node的size大小的内存,强制转换为bitree类型
variables->data=*s;
push(variable,variables); //入变量栈
}
else if(int(*s)>90||int(*s)<65) //读取的逻辑运算符
{
gettop(logic,e); //取运算符栈的栈顶元素进行优先级比较
switch(youxianji(*s,e->data))
{
case '<': //栈顶的运算符优先级低,逻辑运算符进栈
logics=(bitree)malloc(sizeof(node));//强制转换为bitree类型
logics->data=*s;
push(logic,logics);
break;
case '=':
pop(logic,kuohao); //括号并接受下一个字符
break;
case '>': //栈顶的运算符优先级高,变量出栈运算
pop(logic,g); //弹出逻辑运算符
pop(variable,a); //弹出变量
b=NULL; //'~'只有右子树
if(g->data!='~')
pop(variable,b);
create(g,b,a); //建树的函数调用
push(variable,g);//将临时的根作为新的变量压入变量栈中
gettop(logic,e);
if(*s!='#'&&*s!=')'&&youxianji(*s,e->data)!='>')
{
logics=(bitree)malloc(sizeof(node));//强制转换为bitree类型
logics->data=*s;
push(logic,logics); //逻辑运算符入栈
}
else s=s-1;
break;
}
}
s++;
}
tree=g;
}
int valuetree(bitree tree) //根据变量的取值组合并利用逻辑表达式的性质对树进行求值
{
if(!tree) return 0; //遇到空的结点
else if(tree->data!='|'&&tree->data!='&'&&tree->data!='~') //找到的是变量
return zuhe[int(tree->data)-65]; //返回