逻辑命题公式计算.docx

题号：第一题
题目：电梯模拟
需求分析：
计算命题演算公式的真值
所谓命题演算公式是指由逻辑变量 (其值为TRUE或FALSE )和逻辑运算符A (AND )、
V (OR)和「( NOT)按一定规则所组成的公式(蕴含之类的运算可以用A、V和「来表 示)。公式运算的先后顺序为「、A、V,而括号()可以改变优先次序。已知一个命题演 算公式及各变量的值，要求设计一个程序来计算公式的真值。
要求：
利用二叉树来计算公式的真值。首先利用堆栈将中缀形式的公式变为后缀形式；
然后根据后缀形式，从叶结点开始构造相应的二叉树； 最后按后序遍历该树，求各子树之值，
即每到达一个结点，其子树之值已经计算出来，当到达根结点时，求得的值就是公式之真值。
逻辑变元的标识符不限于单字母，而可以是任意长的字母数字串。
根据用户的要求显示表达式的真值表。
设计：
：
<1>,数据结构设计：
线性堆栈1的数据结构定义
typedef struct
(
DataType stack [MaxStackSize];
int top; /*当前栈的表长*/
} SeqStack;
用线性堆栈主要是用来存储输入的字符， 它的作用就是将中缀表达式变成后缀
表达式。
线性堆栈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域，然后将它的左