1、计算命题演算公式的真值计算命题演算公式的真值 一、一、需求分析需求分析 所谓命题演算公式是指由逻辑变量 （其值为TRUE 或FALSE） 和逻辑运算符 （AND） 、 （OR）和（NOT）按一定规则所组成的公式（蕴含之类的运算可以用、和来表 示） 。公式运算的先后顺序为、，而括号（）可以改变优先次序。已知一个命题演 算公式及各变量的值，要求设计一个程序来计算公式的真值。 要求： （1）利用二叉树来计算公式的真值。首先利用堆栈将中缀形式的公式变为后缀形式； 然后根据后缀形式， 从叶结点开始构造相应的二叉树； 最后按后序遍历该树， 求各子树之值， 即每到达一个结点， 其子树之值已经计算出来， 当到
2、达根结点时， 求得的值就是公式之真值。 （2）逻辑变元的标识符不限于单字母，而可以是任意长的字母数字串。 （3）根据用户的要求显示表达式的真值表。 二、二、设计设计 1、设计思想设计思想 (1) 数据结构设计 (1) 线性堆栈 1 的数据结构定义 typedef char DataType ； typedef struct DataType stackMaxStackSize; int top; SeqStack1; 用线性堆栈主要是用来存储输入的字符，它的作用就是将中缀表达式变成后缀表达 式。 (2) 线性堆栈 2 的数据结构定义 typedef struct snode DataType
3、data; Struct snode *next; LSNode; 用于检测表达式的括号匹配。 (3) 定义二叉树的结点 BiTreeNode typedef struct Node DataType dataMaxStackSize; struct Node *leftChild; struct Node *rightChild; struct Node *parent; BiTreeNode; （3）算法设计 首先实现将中缀表达式变成后缀表达式：首先实现将中缀表达式变成后缀表达式： 在将中缀表达式变成后缀表达式的时候会用到堆栈，因此首先需要初始化一个堆栈。 又由于逻辑变元可能是字符也可能是
4、字符串， 所以它又不同于将单字符的逻辑变元的中缀表 达式变成后缀表达式。 我的设计是这样的， 我将中缀表达式变成后缀表达式的过程分成了两 部：化简（将一维的复杂的中缀表达式变成一维的简单的中缀表达式，并将字符串逻辑变元 存放在二维数组中），转化（将化简后的中缀表达式变成后缀表达式）。 然后用后缀表达式构造出二叉树：然后用后缀表达式构造出二叉树： 在这个过程中，我用到了之前所定义的存放树的堆栈。具体实现为：扫描后缀表达式， 如果遇到逻辑变元然后将这个变元变成一个树节点，它的实现就是将该逻辑变元赋给树的 data 域，然后将它的左右子树赋为 NULL，然后将这个树节点压入相应的堆栈；接着继续扫 描
5、，如果遇到的是单目运算符（非号“！”）也将它构造成一个树节点然后从堆栈里面弹出 一个树形节点，将弹出的元素的作为它的左子树，右子树设置为 NULL，然后将这个树节点 压入相应的堆栈；如果扫描到的是双目运算符（与号“ 扫描到运算符后 构造简化的中缀表达式; 得到这个字符串的长度; 将这个字符串存放在 store10中; 转化部分用伪代码描述为： 循环扫描中缀表达式 if(扫描到逻辑变元) 保存到后缀表达式中； else StackTop(myStack, res=Precede(x,扫描到的运算符); if(res=) x 退栈； if(res=leftChild=x1; （4） ，打印二叉树，
6、其基本思想就是每到一个根节点就计算一个值，如此重复，直到总 根节点，用伪代码简单描述为： 循环赋值 if(扫描到逻辑变元) 赋值进栈； else if(扫描到双目运算符) 从栈中弹出两数 对两数进行相应的运算; 将运算结构进栈；; else 从栈中弹出两数; 对两数进行非运算; 将运算结构进栈; 每循环一次输出一个结构; 三、三、调试分析调试分析 调试过程中遇到的问题与解决方案：调试过程中遇到的问题与解决方案： 首先就是中缀表达式中的逻辑变元不是单个字符而是一些字符串， 这样在将中缀表达式 转化成后缀表达式的时候就会比较麻烦， 后来经过一番分析与调试后， 用二维数组存放比较 好，那样实现起来就会比较简单。 然后再就是构造树， 在构造树时要用到堆栈， 但是前面用到的堆栈的数据类型和此时用 到的又有很大的差别， 在此时又要想到再换一个类型的堆栈， 同时在构造树的时候有要找到 合适的算法。 最后就是真值表的打印， 对这一模块的实现最容易
