数据结构：重言式判别

2018-07-10 本文已影响0人 W杂货铺W

题目：设计一个程序，通过真值表判别一个逻辑表达式属于重言式，矛盾式，或二者都不是，并显示表达式真值表。

一、需求分析

逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括“|”，“&”和“~”，分别表示或，与和非，运算优先程度递增，但可由括号改变，即括号内运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有一个或多个空格符。
若是重言式或矛盾式，可以只显示“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;0,0;0,1;1,0;1,1;

二、概要设计

1. 数据结构

二叉树的抽象数据类型定义如下：

ADT BinaryTree{

数据对象D：D是具有相同特性的数据元素的集合。

数据关系R：

若D=∅，则R=∅，称BinaryTree为空二叉树；

若D≠∅，则R={H}，H是如下二元关系；

（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；

（2）若D-{root}≠∅，则存在D-{root}={D_l，D_r}，且D_l∩D_r=∅

（3）若D_l≠∅，则D_l中一定存在唯一的元素x_l，<root,x_l>∈H，且存在D₁上的关系 $H_l \subset H$ ，若D_r≠∅，则D_r中一定存在唯一的元素x_r，<root,x_r>∈H，且存在D_r上的关系 $H_r \subset H$ ;H={<root,x_l>,<root,x_r>,H_l,H_r};

（4）（D_l，{H_l}）是一颗符合基本定义的二叉树，称为根的左子树，（D_r，{H_r}）是一颗符合基本定义的二叉树，称为根的右子树。

基本操作P:

CreatBiTree(&T, definition)

初始条件：defination给出二叉树的定义

操作结果：按definition构造二叉树T

Assign(T,&e,value)

初始条件：二叉树T存在，e是T中某个节点

操作结果：节点e赋值为value

PreOrderTraverse(T,Visit())

初始条件：二叉树存在，Visit是对每个节点操作的应用函数

操作结果：先序遍历T，对每一个节点调用函数Visit一次且仅一次

PostOrderTraverse(T,Visit())

初始条件：二叉树存在，Visit是对每个节点操作的应用函数

操作结果：后序遍历T，对每一个节点调用函数Visit一次且仅一次

}

以栈作为辅助，数据类型为：

ADT Stack{
数据对象：
D={a_i|a∈EleSet,i=1,2,...,n,n≥0}
数据关系：
R1={<a_i-1,a_i>|a_i-1,a_i∈D,i=2,...,n}
约定a_n为栈顶，a₁为栈底。

基本操作：

InitStack(&S)

操作结果：构造一个空栈S

GetTop(S)

初始条件：栈S已存在且非空

操作结果：返回S栈顶元素

Pop(&S, &e)

初始条件：栈S已存在

操作结果：删除S的栈顶元素，并用e返回其值

Push(&S, &e)

初始条件：栈S已存在

操作结果：插入e为新的栈顶元素

}

2. 使用函数

int InitStack(BiTStack &S)
操作结果：构造栈存放二叉树节点
int Push(BiTStack &S, BiTree &B)
操作结果：二叉树节点入栈
int Pop(BiTStack &S,BiTree &B)
操作结果：二叉树节点出栈
BiTree Gettop(BiTStack S)
操作结果：返回栈顶元素
int CreatBiTree(BiTree &B, char *a)
操作结果：根据表达式a构造二叉树
int Calculate(BiTree B)
操作结果：后序遍历二叉树，计算表达式真值
int AssignValue(BiTree B,char c,int value)
操作结果：先序遍历二叉树，为data为c节点的赋值value
int Evaluate(BiTree B, int kind, char *c, int *res)
操作结果：数组res返回二叉树的真值表
int CustomAssign(BiTree b, char ch[], char a[])
操作结果：手动对表达式a中变量ch赋值
char Judge(int *res)
操作结果：根据真值表判断表达式为矛盾式，永真式或二者都不是
int Show(char *a)
操作结果：打印表达式
int Num2Bin(int *b,int x,int len)
操作结果：数组b返回整数x的二进制表示
int Getvar(char *a,char *ch)
操作结果：返回表达式中不同的变量个数和变量ch
int In(char c)
操作结果：判定字符是否为运算符
char Precede(char c1, char c2)
操作结果：判断逻辑符号的优先级
int CorrectNot(char a[])
操作结果：返回表达式是否合法

三、详细设计

1. 数据储存结构

二叉树的二叉链表储存结构和辅助栈的实现如下：

typedef struct BiTNode{
    char data;      // 元素名称
    int value;      // 0,1值
    struct BiTNode *lchild,*rchild;
}*BiTree;

typedef struct {
    BiTree *top;
    BiTree *base;
}BiTStack;

2. 计算功能实现

识别逻辑表达式符号形式并建立二叉树
采用自底向上的算符优先法，参考教科书3.2.5节

int CreatBiTree(BiTree &B, char *a){
    // 自底向上的算符优先算法建立二叉树。OPTR和OPND分别为运算符栈和运算数栈
    char *expr;
    char End[] = {'#','\0'};
    expr = strcat(a,End);
    BiTStack OPTR, OPND;
    InitStack(OPTR);
    InitStack(OPND);
    BiTree b1,b,x,y,theta;
    b1 = (BiTree)malloc(sizeof(BiTNode));
    b1->data = '#';
    b1->value = 0;
    b1->lchild = NULL;
    b1->rchild = NULL;
    Push(OPTR, b1);  
    while(*expr !='#'||Gettop(OPTR)->data!='#'){
        if(*expr ==' '){    // 忽略空格
            expr++;
            continue;
        }
        b = (BiTree)malloc(sizeof(BiTNode));
        b->data = *expr;
        b->value = 0;
        b->lchild = NULL;
        b->rchild = NULL;
        if(!In(*expr)){
            Push(OPND, b);    
            expr++;
            continue;
        }else {
            switch(Precede(Gettop(OPTR)->data, *expr)){
                case '<': // 栈顶元素优先权低
                    Push(OPTR,b);
                    expr++;
                    break;
                case '=': // 脱括号指针移动到下一字符
                    Pop(OPTR, b);
                    expr++;
                    break;
                case '>': // 退栈并将运算结果入栈
                    Pop(OPTR, theta);
                    Pop(OPND, x);
                    theta->rchild = x;
                    if(theta->data != '~'){  // 运算符为‘~’，则左子树为空
                        Pop(OPND, y);
                        theta->lchild = y;
                    }
                    Push(OPND,theta);
            }
        }
    }
    B=Gettop(OPND);
    return 1;
}

先序遍历为二叉树赋值

int AssignValue(BiTree B,char c,int value){     // 先序遍历赋值
    if(B){
        if(B->data==c) B->value=value;
        AssignValue(B->lchild, c, value);
        AssignValue(B->rchild, c, value);
    }
    return 1;
}

后序遍历计算表达式

int Calculate(BiTree B){    // 后序遍历计算表达式值
    if(B){
        Calculate(B->lchild);
        Calculate(B->rchild);
        switch(B->data){
            case '|':
                B->value = B->lchild->value||B->rchild->value;
                break;
            case '&':
                B->value = B->lchild->value&&B->rchild->value;
                break;
            case '~':
                B->value = !B->rchild->value;
                break;
        }
    }
    return 1;
}

手动赋值计算表达式取值

int CustomAssign(BiTree b, char ch[], char a[]){    // 用户赋值计算表达式
    printf("Assign values manually?(Y/N)\n");
    char c;
    c=getchar();
    if(c=='Y' || c=='y'){
        int k=0,x;
        while(ch[k] != '\0'){
            printf("%c=", ch[k]);
            scanf("%d", &x);
            while(x!=0 && x!=1){
                printf("Error！0 and 1 only：");
                scanf("%d", &x);
            }
            AssignValue(b, ch[k], x);
            k++;
        }
        Calculate(b);
        printf("The value of ");
        Show(a);
        printf(" is %d\n", b->value);
    }
    return 1;
}

循环计算所有命题下表达式取值

int Evaluate(BiTree B, int kind, char *c, int *res){    
// 2^n循环计算所有命题下表达式取值
    int comb[20];
    int i,j,k,l;
    int num;
    num = pow(2,double(kind));
    for(k=0; k<num; k++){
        for(i=0; i<kind; i++){
            comb[i] = 0;
        }
        Num2Bin(comb, k, kind-1);
        for(j=0; j<kind; j++){
            AssignValue(B, c[j], comb[j]);
        }
        Calculate(B);
        res[k] = B->value;
        for(l=0; l<kind; l++){
            printf("%d ",comb[l]);
        }
        printf("| %d\n",res[k]);
    }
    return 1;
}

3. 主程序

首先判断输入表达式是否合法，决定是否构建二叉树进行计算

int main(){
    int res[1024];  // 真值表
    int kind;   // 变量数
    BiTree b;
    char a[100],ch[20]; // 表达式和变量名
    for(int m=0; m<1024; m++){
        res[m]=-1;
    }
    for(int k=0; k<20; k++){
        ch[k]='\0';
    }
    gets(a);
    if(!CorrectNot(a)){
        int i = 0;
        kind = Getvar(a, ch);
        CreatBiTree(b,a);
        printf("Truth Table:\n");
        while(ch[i]!='\0'){
            printf("%c ",ch[i]);
            i++;
        }
        printf("| ");
        Show(a);
        printf("\n");
        Evaluate(b, kind, ch, res);
        switch(Judge(res)){
            case 'T':
                printf("True forever\n");
                break;
            case 'F':
                printf("False forever\n");
                break;
            case 'S':
                printf("Satisfactible\n");
                CustomAssign(b,ch,a);
                break;
        }
    }else{
        printf("expression error!");
    }
    return 1;
}

4. 程序的层次结构

层次结构

四、用户手册

本程序的运行环境为DOS操作系统，执行文件为：logic.exe
进入程序按提示操作，输入表达式
输入后按回车符即显示结果
非矛盾和重言式可以选择自行赋值，赋值后显示逻辑表达式值

五、测试结果