逻辑命题公式计算(共18页).doc

精选优质文档-倾情为你奉上题号：第一题题目：电梯模拟1，需求分析： 计算命题演算公式的真值所谓命题演算公式是指由逻辑变量（其值为TRUE或FALSE）和逻辑运算符（AND）、（OR）和（NOT）按一定规则所组成的公式（蕴含之类的运算可以用、和来表示）。公式运算的先后顺序为、，而括号（）可以改变优先次序。已知一个命题演算公式及各变量的值，要求设计一个程序来计算公式的真值。要求：（1）利用二叉树来计算公式的真值。首先利用堆栈将中缀形式的公式变为后缀形式；然后根据后缀形式，从叶结点开始构造相应的二叉树；最后按后序遍历该树，求各子树之值，即每到达一个结点，其子树之值已经计算出来，当到达根结点时，求得的值就是公式之真值。（2）逻辑变元的标识符不限于单字母，而可以是任意长的字母数字串。（3）根据用户的要求显示表达式的真值表。2，设计： 2.1 设计思想：<1>，数据结构设计： (1) 线性堆栈1的数据结构定义 typedef struct DataType stack MaxStackSize; int top; /* 当前栈的表长*/ SeqStack;用线性堆栈主要是用来存储输入的字符，它的作用就是将中缀表达式变成后缀表达式。(2) 线性堆栈2的数据结构定义typedef struct BiTreeNode *stack MaxStackSize;int top; /* 当前栈的表长*/ TreeStack;这个堆栈和上面的堆栈的唯一不同就是它们存储的数据的类型不同，此堆栈存储的是树节点，它的作用是将后缀表达式构成一棵二叉树。(3) 树节点数据结构定义 typedef struct Node DataType data; struct Node *leftChild; struct Node *rightChild; BiTreeNode; <2>算法设计详细思路如下： 首先实现将中缀表达式变成后缀表达式： 在将中缀表达式变成后缀表达式的时候会用到堆栈，因此首先需要初始化一个堆栈。又由于逻辑变元可能是字符也可能是字符串，所以它又不同于将单字符的逻辑变元的中缀表达式变成后缀表达式。我的设计是这样的，我将中缀表达式变成后缀表达式的过程分成了两部：化简（将一维的复杂的中缀表达式变成一维的简单的中缀表达式，并将字符串逻辑变元存放在二维数组中），转化（将化简后的中缀表达式变成后缀表达式）。（1）化简：先用一个字符数组存放输入的中缀表达式（表达式以#号结束），然后将一维的中缀表达式中的字符串逻辑变元用一个字符进行标识，这样我们就可以将原来复杂的中缀表达式变成熟悉而又简单的中缀表达式，同时用二维数组存放那些字符串逻辑变元。实现的过程就是首先扫描一维中缀表达式，如果遇到逻辑符号，那么记住这个逻辑符号在数组中的相对位置用一个变量存放，然后继续扫描中缀表达式直到再次遇到逻辑符号，再一次记住它在中缀表达式中的相对位置，这两个逻辑符号之间的部分就是一个完整的逻辑变元，将这个字符串逻辑变元用一个字符代替并将这个字符串逻辑变元保存在二维数组中。这个过程的实现我把它放在change()函数中。（2）转化：在实现该功能时，首先需要定义各符号的优先级，即：'(' 和 ')' 的优先级最高；'!'（逻辑非号）的优先级次之；'&'（逻辑与号）的优先级又低一级，'|'（逻辑或号）的优先级跟低；'#' （他不是逻辑符号，只是为了方便使用堆栈而设置）的优先级最低，接着将 '#'压入堆栈。在这之后就是正式的转化了，其过程为：当读到的是逻辑变元时直接输出，并保存到保存后缀表达式的数组中，当读到的单词为运算符时，令x1为当前栈顶运算符的变量，x2为当前扫描到的简单中缀表达式的运算符的变量，把当前读入的单词赋予变量x2，然后比较x1和x2的优先级。若x1的优先级高于x2的优先级，将x1退栈作为后缀表达式的一个单词输出，然后接着比较新的栈顶运算符x1的优先级与x2的优先级；若x1的优先级低于x2的优先级，将x2的值进栈，然后接着读下一个单词；若x1的优先级等于x2的优先级且x1为“（”，x2为“）”，将x1退栈，然后接着读下一个单词；若x1的优先级等于x2的优先级且x1为“#”，x2为“#”，算法结束。这个过程我把它放在InToPost()函数中。 然后用后缀表达式构造出二叉树：在这个过程中，我用到了之前所定义的存放树的堆栈。具体实现为：扫描后缀表达式，如果遇到逻辑变元然后将这个变元变成一个树节点，它的实现就是将该逻辑变元赋给树的data域，然后将它的左右子树赋为NULL，然后将这个树节点压入相应的堆栈；接着继续扫描，如果遇到的是单目运算符（非号“！”）也将它构造成一个树节点然后从堆栈里面弹出一个树形节点，将弹出的元素的作为它的左子树，右子树设置为NULL，然后将这个树节点压入相应的堆栈；如果扫描到的是双目运算符（与号“&”或者或号“|”）将它也构造成一棵树，然后将这个树节点压入相应的堆栈，然后从栈中弹出两个元素，一个作为它的左子树，一个作为它的右子树，如此重复n（n为后缀表达式的长度）次。这个过程我把它放在Maketree()函数中。 最后打印真值表： 打印真值表也用到了前面的简单的后缀表达式，其实现的基本思想为和构造二叉树差不多，它实现了每到一个根节点就计算一个运算的值。在打印之前需要统计字符的个数，有m个字符则要打印2m行，因为他有这么多情况。具体实现为：用一个字符型的数组来存放每个元素的一次取值，然后扫描后缀表达式，如果遇到逻辑变元就通过这个标识将相应的取值赋给它，然后它压入堆栈；接着继续扫描，如果遇到的是单目运算符（非号“！”）则从堆栈里面弹出一个元素，并对它进行非运算，然后又将这个运算后的值压入堆栈；如果扫描到的是双目运算符（与号“&”或者或号“|”）则从栈中弹出两个元素，并对这两个元素进行相应的运算，然后将这个运算后的值压入堆栈，如此重复n（n为后缀表达式的长度）次。这个过程我把它放在Print()函数中。其中第一，二过程的流程图描述分别为：开始扫描后缀表达式扫描后缀表达式 扫描到的是逻辑变元？扫描到x2是逻辑变元？输出YesYes栈顶元素的优先级高？NoNo构造成树节点并进栈取栈顶元素x1双目运算符单目运算符构造成树节点从栈中弹出两个元素作为其左右子树构造成树节点从栈中弹出一个元素作为其左子树 No进栈小于出栈Yes进栈进栈Yes结束x1,x2都为'#'x1为'(',x2we为')'No 2.2 设计表示：<1>, 函数调用关系及函数说明： main() Maketree()Print()InToPost()change()StackPush1()StackPop1StackTop()StackPop()StackPush()Precede()StackPop()StackPush() change()函数原型为： void change(char prefixStr1,char prefixStr,int length,char store10,int* row,int* k )该函数含有有六个参数，其中 prefixStr1为用户输入的中缀表达式，prefixStr为即将转化成为的简单中缀表达式，length为二维数组中存放的各个字符串的的长度store10用来存放中缀表达式中的逻辑变元，row就是逻辑变元的个数，k简化后的中缀表达式的长度。该函数的功能就是将复杂的中缀表达式变成简单的中缀表达式。 InToPost()函数原型为：void InToPost(char prefixStr,char postfixStr,SeqStack* myStack,int* n,int k)该函数函数有五个参数 prefixStr为中缀表达式，postfixStr为简化后的后缀表达式，myStack为在转化过程中用到的堆栈，n为后缀表达式的字符长度，k为中缀表达式的字符长度。该函数的功能就是将简单的中缀表达式变成简单的后缀表达式。 Maketree()函数原型为： void Maketree(BiTreeNode *root,TreeStack* myTree,char postfixStr,int n)该函数共有四个参数，其中root为所建立的树的根节点，myTree是在构造树时所用到的堆栈，另外两个参数和前面的同名参数具有相同意义。这个函数的功能就是将简单的中缀表达式变成简单的后缀表达式。 Precede()函数原型为： DataType Precede(DataType x1,DataType x2)该函数有两个参数，返回值类型为DataType型，其中x1和x2就是要进行优先级比较的两个两个字符。x1为栈顶元素，x2为扫描到的元素。该函数的功能就是比较x1和x2的优先级并将比较结果返回给调用函数。 Print()函数原型为：void Print(char postfixStr,char store10,int length,int row,int n,SeqStack* myStack)该函数有六个参数，其中myStack是在输出真值表过程中要用到的堆栈，其余的参数和前面介绍的函数中的同名参数具有相同的意义。该函数的功能就是打印真值表。 <2> 函数接口说明：函数的调用关系在上面的图中已经显示出来了，整个程序就是由一些子函数的集合，他们之间按所要实现的功能不同而调用不同的函数。在这些函数中除主函数外，其它函数的级别相同。2.3详细设计：（1） ，定义所需要的结构体，前面已经介绍了；（2），我将中缀表达式变成后缀表达式的过程分成了两部：化简（将一维的复杂的中缀表达式变成一维的简单的中缀表达式，并将字符串逻辑变元存放在二维数组中），转化（将化简后的中缀表达式变成后缀表达式）。其中化简部分将要用伪代码描述为while(prefixStr1m!='#')扫描中缀表达式while(prefixStr1m不为运算'符)继续扫描，直到扫描到运算符;扫描到运算符后 构造简化的中缀表达式; 得到这个字符串的长度; 将这个字符串存放在store10中; 转化部分用伪代码描述为： 循环扫描中缀表达式 if(扫描到逻辑变元) 保存到后缀表达式中；elseStackTop(myStack,&x);res=Precede(x,扫描到的运算符);if(res='>') x退栈；if(res='<') 扫描到的运算符进栈；if(res='=' && x='(') 退栈if(res='=' && x='#') 结束； （3），构造二叉树，其思想就是将逻辑变元作为叶子节点，运算符作为根节点，用堆栈实现，用伪代码简单描述为： 循环扫描后缀表达式 if(扫描到逻辑变元') 讲逻辑变元进栈； else if('扫描到双目运算符) StackPop1(myTree,&x1); StackPop1(myTree,&x2); 将x1，x2作为它的左右子树； StackPush1(myTree,p); else StackPop1(myTree,&x1); 将x1作为它的左子树，又子树为空； StackPush1(myTree,p); StackPop1(myTree,&x1); root->leftChild=x1; （4），打印二叉树，其基本思想就是每到一个根节点就计算一个值，如此重复，直到总根节点，用伪代码简单描述为： 循环赋值if(扫描到逻辑变元') 赋值进栈；elseif(扫描到双目运算符) 从栈中弹出两数对两数进行相应的运算;将运算结构进栈；;else 从栈中弹出两数; 对两数进行非运算; 将运算结构进栈; 每循环一次输出一个结构; 3，调试分析： <1>，调试过程中遇到的问题与解决方案： 这个题我个人觉的是这几个中最麻烦的一个，因为它有几个难点去分析与实现：首先就是中缀表达式中的逻辑变元不是单个字符而是一些字符串，这样在将中缀表达式转化成后缀表达式的时候就会比较麻烦，起初我也不太清楚该怎么处理他，后来经过一番分析与调试后，我觉得用二维数组存放比较好，那样实现起来就会比较简单，当然虽然这么说，其实实现起来也还是有一定的困难的，比如怎样去找到一个完整的字符串逻辑变元，找到之后又怎样存放等等。然后再就是构造树，在构造树时要用到堆栈，但是前面用到的堆栈的数据类型和此时用到的又有很大的差别，在此时又要想到再换一个类型的堆栈，同时在构造树的时候有要找到合适的算法最后就是真值表的打印，对这一模块的实现最容易想到的就是有几个逻辑变元就进行几次循环，每一重循环对应着一个变量的取值。但是经过分析这显然是行不通的，因为在事先我们并不知道会有多少个变元。最后我用到的方法就是那种最原始的方法，用一重循环去实现，每重循环都会有一个值，将这个值反复进行对2取余和对2进行整除，将取余后的值赋给相应的变元。这样总共循环2的变元素的n次方次即可。当然在完成这个程序时还遇到其它的很多的问题，这里就不多进行列出了，最后我在声明一下这个程序的一个缺陷，他在进行逻辑变元数统计的时候没有对两个相同的变元进行识别。 <2>，算法的时空复杂度分析： 本次程序的完成除书上的那些头文件外，其它的算法都是自己提供，对于我自己写的那些函数，比如change()函数，InToPost()函数，Print()函数，Maketree()函数他们的时间复杂度均为o(n),而对于change()函数其空间复杂度为o(1),其它的三个函数，由于他们都用到了堆栈这个数据结构他们的空间复杂度都是o(n).4，用户手册： 本程序经过编译，连接后，运行时只需要用户输入一个中缀表达式，也即用户想要进行的逻辑运算的表达式。这里有三点需要要提醒用户： 1，在输入表达式时“&”表示逻辑与；“|”号表示逻辑或，“！”表示逻辑非。在输入中缀表达式后程序将自动执行并输出结构，用户不需进行干预； 2，在本程序的书写中我定义了一个最多的逻辑变元的数量为十个，用户在输入表达式时应该注意输入，不要超过这个界限。 3，用户在输入完所要进行运算的表达式后要记得以“#”号结尾，“#”号是判断输入结束的标识，如果用户没有以“#”号结束，那么程序的运行结果将会出错，这时用户必须重新对程序进行编译连接，然后按照要求输入表达式。 5，测试数据及测试结果： 由于用户的不同输入将对应着不同的结果，这里我仅随便输入一个逻辑表达式以供用户参考：请输入表达式(以#号结束)： !aaa&(bb|cd1)&wq|d#将中缀表达式变成后缀表达式为：aaa ! bb cd1 | & wq & d |打印构造的二叉树为： -d-| -wq -& -! -aaa -& -cd1 -| -bb二叉树的后序遍历为：bb cd1 | aaa ! & wq & d |打印真值表为：aaa bb cd1 wq d 运算结果0 0 0 0 0 01 0 0 0 0 00 1 0 0 0 01 1 0 0 0 00 0 1 0 0 01 0 1 0 0 00 1 1 0 0 01 1 1 0 0 00 0 0 1 0 01 0 0 1 0 00 1 0 1 0 11 1 0 1 0 00 0 1 1 0 11 0 1 1 0 00 1 1 1 0 11 1 1 1 0 00 0 0 0 1 11 0 0 0 1 10 1 0 0 1 11 1 0 0 1 10 0 1 0 1 11 0 1 0 1 10 1 1 0 1 11 1 1 0 1 10 0 0 1 1 11 0 0 1 1 10 1 0 1 1 11 1 0 1 1 10 0 1 1 1 11 0 1 1 1 10 1 1 1 1 11 1 1 1 1 16，源程序清单：caculate.cpp /程序源文件BiTree.h /树的相关操作的头文件BiTreeTraverse.h /树的遍历的头文件caozuo.h /自己提供的为实现所要求的功能而添加的头文件Compare.h /比较运算符优先级的头文件SeqStack.h /线性堆栈的有关操作的头文件TreeStack.h /为构造树而用到的头文件/caculate.cpp 程序源文件#include <stdio.h>#include <string.h>#include <stdlib.h>#define MaxStackSize 50#include "SeqStack.h"#include "BiTree.h"#include "TreeStack.h"#include "Compare.h"#include "BiTreeTraverse.h"#include "caozuo.h"/void main()int i,j,n=0,k=0,row=0;SeqStack myStack;char prefixStr100,prefixStr1100;char postfixStr100;char store1010;int length10,index=0; BiTreeNode *root; TreeStack myTree;StackInitiate(&myStack);StackPush(&myStack,'#');printf("请输入表达式(以#号结束)： ");scanf("%s",prefixStr1);change(prefixStr1,prefixStr,length,store,&row,&k); /k是中缀表达式的字符长度InToPost(prefixStr,postfixStr,&myStack,&n,k);/ printf("将中缀表达式变成后缀表达式为： n");for(i=0;i<n;i+) /n是后缀表达式中的字符的长度if(postfixStri>='A' && postfixStri<='Z') for(j=0;j<lengthindex;j+) printf("%c",storeindexj);index+;printf(" ");else printf("%c ",postfixStri); printf("n");/构造二叉树 printf("n打印构造的二叉树为： n");StackInitiate1(&myTree); TreeInitiate(&root); Maketree(root,&myTree,postfixStr,n); PrintBiTree(root,0,store,length); /凹入打印二叉树printf("二叉树的后序遍历为：n");PostOrder(root->leftChild,store,length);printf("n");/打印真值表printf("n打印真值表为： n");Print(postfixStr,store,length,row,n,&myStack);/caozuo.h 头文件void change(char prefixStr1,char prefixStr,int length,char store10,int* row,int* k )int j,t,m=0;char ch='A'while(prefixStr1m!='#')j=m;while(prefixStr1m!='&' && prefixStr1m!='|' && prefixStr1m!='!' && prefixStr1m!='(' && prefixStr1m!=')' && prefixStr1m!='#')m+;if(m!=j) prefixStr(*k)+=ch; ch+=1; for(t=j;t<m;t+) length*row=m-j; store*rowt-j=prefixStr1t; (*row)+;prefixStr(*k)+=prefixStr1m;m+;if(prefixStr1m='&' | prefixStr1m='|' | prefixStr1m='!' | prefixStr1m='(' | prefixStr1m=')' | prefixStr1m='#') prefixStr(*k)+=prefixStr1m;else m-;if(prefixStr1m!='#') m+;elsebreak;/void InToPost(char prefixStr,char postfixStr,SeqStack* myStack,int* n,int k)int i;DataType res,x;for(i=0;i<k;i+) /k是中缀表达式中的字符的长度if(prefixStri>='A' && prefixStri<='Z')postfixStr(*n)+=prefixStri;elseStackTop(myStack,&x);res=Precede(x,prefixStri);if(res='>')while(res='>') StackPop(myStack,&x); postfixStr(*n)+=x;StackTop(myStack,&x);res=Precede(x,prefixStri);if(res='<')StackPush(myStack,prefixStri);if(res='=' && x='(')StackPop(myStack,&x);if(res='=' && x='#')break;/void Print(char postfixStr,char store10,int length,int row,int n,SeqStack* myStack)char *ptr;DataType x,v1,v2;int i,j,t,total=1;int value,value1,value2,value3;for(i=0;i<row;i+)for(j=0;j<lengthi;j+)printf("%c",storeij);printf(" ");printf("运算结果");printf("n");for(i=0;i<row;i+)total*=2;ptr=(char* )malloc(sizeof(char)*row); for(i=0;i<total;i+)t=i;for(j=0;j<row;j+) ptrj=t%2+48; printf("%c ",ptrj); t=t/2;for(j=0;j<n;j+)if(postfixStrj>='A' && postfixStrj<='Z')value=postfixStrj-'A'StackPush(myStack,ptrvalue);elseif(postfixStrj!='!') StackPop(myStack,&v1);value1=v1-48;StackPop(myStack,&v2);value2=v2-48;switch(postfixStrj) case '&': value3=value1&&value2; break;case '|': value3=value1|value2; break;x=value3+48;StackPush(myStack,x);else StackPop(myStack,&v1);value1=v1-48;value3=!value1;x=value3+48;StackPush(myStack,x);StackPop(myStack,&x);printf(" %c",x);printf("n");/void Maketree(BiTreeNode *root,TreeStack* myTree,char postfixStr,int n)int i; BiTreeNode *p,*x1,*x2; for(i=0;i<n;i+)if(postfixStri>='A' && postfixStri<='Z') p=(BiTreeNode *)malloc(sizeof(BiTreeNode);p->data=postfixStri;p->leftChild=NULL;p->rightChild=NULL;StackPush1(myTree,p);else p=(BiTreeNode *)malloc(sizeof(BiTreeNode); x1=(BiTreeNode *)malloc(sizeof(BiTreeNode); x2=(BiTreeNode *)malloc(sizeof(BiTreeNode);if(postfixStri!='!') StackPop1(myTree,&x1); StackPop1(myTree,&x2); p->data=postfixStri;if(x1->data>='A' && x1->data<='Z') p->leftChild=x2; p->rightChild=x1;else p->leftChild=x1; p->rightChild=x2; StackPush1(myTree,p);else StackPop1(myTree,&x1); p->data=postfixStri; p->leftChild=x1; p->rightChild=NULL; StackPush1(myTree,p);StackPop1(myTree,&x1);root->leftChild=x1; /Compare.h 头文件DataType Precede(DataType x1,DataType x2) DataType result; switch(x2) case '|': if(x1='('|x1='#') result='<' else result='>' break; case '&': if(x1='&' |x1=')' |x1='!') result='>' else result='<' b