重言式判别实验报告[实用论文].docVIP

重言式判别 一、问题描述 一个逻辑表达式如果对于其变元的任一种取值都为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式；然而，更多的情况下，既非重言式，也非矛盾式。试写一程序，通过真值表判断一个逻辑表达式属于那一类。 二、需求分析 （1）逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括“|”，“”和“~”, 分别表示或、与和非，运算优先程度递增，但可以有括号改变，即括号内的运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有多个空格符。 （2）若是重言式或矛盾式，可以只“显示True forever”或“False forever”，否则显示“Satisfactible”以及变量名序列，与用户交互。若用户对表达式中变元取一组值，程序就求出并显示逻辑表达式的值。 （3）测试数据： ①(A|~A)(B|~B) ②(A|~A)C ③A|B|C|D|E|~A ④ABC~B ⑤(A|B)(A|~A) ⑥A~B|~AB 三、概要设计 void creatzuhe(int n) 初始条件：n是循环体，以便产生各种情况。 操作结果：产生变量的各种取值组合 void create(bitree root,bitree l,bitree r) 初始条件：root是根结点，l是左子树，r是右子树。 操作结果：按照运算符优先级关系建立二叉树。 char youxianji(char lie,char hang) 初始条件：lie是第一个运算符，hang是第二个运算符。 操作结果：得出优先级比较关系。 void creatstack(sqstack st) 初始条件：若栈st存在。 操作结果：把栈置空。 void push(sqstack st,bitree e) 初始条件：若栈st存在，对树结点e操作。 操作结果：把操作符入栈。 void pop(sqstack st,bitree e) 初始条件：若栈st存在，对树结点e操作。 操作结果：把操作符出栈。 void Gettop(sqstack st,bitree e) 初始条件：若栈st存在，对树结点e操作。 操作结果：取栈顶元素。 void creattree(char s[],bitree tree) 初始条件：是s[]存放运算符，tree是按照运算符优先级建立的二叉树。 操作结果：判断重言式。 int value_tree(bitree tree) 初始条件：tree是按照运算符优先级建立的二叉树。 操作结果：对逻辑表达式求值。 算法思想： 自底向上地根据运算符地优先级来建立分子树函数;当逻辑表达式读完后-子根root就是一棵完整的二叉树。用穷举法得出所有可能组合，对二叉树进行先序遍历，对存放在上面的表达式进行求值。并用两个栈分别存放运算符和变量，来判别是否为重言式。 四、程序实现关键代码 typedef struct btdnode{ char data; struct btdnode *lchild; struct btdnode *rchild; }*bitree; //识别表达式使用的堆栈定义,它存放的都是树的结构; typedef struct Stack{ struct btdnode **base; //栈中的元素都是树的结点结构； struct btdnode **top; int stacksize; }sqstack; //用于产生变量的各种取值组合; void creatzuhe(int n) { int i,num=0,j=0,e; int temp[max]; for(i=0;iN;i++) zuhe[i]=0; while(n) { e=n%2; num++; temp[j++]=e; n=n/2; } j=j-1; num=N-num; while(j=0) { e=temp[j--]; zuhe[num++]=e; } } //自底向上地根据运算符地优先级来建立分子树函数;当逻辑表达式读完后-子根root就是一棵完整的二叉树 int k=0;//建树的标志，k＝1表示第一次建立