数据结构课程设计：命题演算公式真值的计算

#include <stdio.h> #include <malloc.h> #include <string.h> typedef struct {char fuhao[100]; int top; }SeqStack;//定义符号结构体 typedef struct Node { char data[100]; //数据域 struct Node *leftChild; //左子树指针 struct Node *rightChild; //右子树指针 struct Node *father;//根结点指针 }BiTreeNode;//结点的结构体定义 typedef struct { BiTreeNode * dizhi[100]; int top; }SeqStack1; //定义结点结构体 void StackInitiate(SeqStack *S)//初始化符号顺序堆栈s，栈底为$ { S->fuhao[0]='$'; S->top = 1; //定义初始栈顶下标值 } void StackPush(SeqStack *S,char x) //入栈,把x压入顺序堆栈 { S->fuhao[S->top] = x ; S->top++; } void StackPop(SeqStack *S,char *x)//出栈，弹出堆栈s的栈顶元素值到参数x { S->top--; *x = S->fuhao[S->top]; } int StackTop(SeqStack S,char *d)//取栈顶数据元素值到参数d成功返回1，否则返回0 { if(S.top<=0) { printf("堆栈已空!\n"); return 0; } else { *d=S.fuhao[S.top-1]; return 1; } } void Initiate(BiTreeNode **root)//初始化创建二叉树的头结点 { *root = (BiTreeNode * ) malloc(sizeof(BiTreeNode)); (*root)->leftChild=NULL; (*root)->rightChild=NULL; (*root)->father=NULL; } void StackInitiate1(SeqStack1 *S)//初始化指针结点堆栈s1 { S->top = 0; //定义初始栈顶下标值 } void StackPush1(SeqStack1 *S,BiTreeNode *x)//入栈,把x压入顺序堆栈 { S->dizhi[S->top] = x ; S->top++; } BiTreeNode * StackPop1(SeqStack1 *S)//出栈，弹出堆栈s1的栈顶元素值到参数x { BiTreeNode *x; S->top--; x = S->dizhi[S->top]; return x; } //根据表达式优先级将中缀形式转化为后缀形式 int exchange(char a[100],char b[100][100],SeqStack *S,int n) { int i,j,k=0; char temp; for(i=0;i<n;i++) { if(a[i]=='~' || a[i]=='#' || a[i]=='&' ||a[i]=='(' ||a[i]==')'||a[i]=='$') { while(a[i]=='~' || a[i]=='#' || a[i]=='&' ||a[i]=='(' ||a[i]==')'||a[i]=='$') { StackTop(*S,&temp); if(temp=='$'&&a[i]=='$') return k; else if((temp=='$'&&a[i]!='$')||(temp=='#'&&a[i]=='~')|| (temp=='#'&&a[i]=='&')||(temp=='#'&&a[i]=='(')|| (temp=='&'&&a[i]=='~')||(temp=='&'&&a[i]=='(')||(temp=='~'&&a[i]=='(')||(temp=='('&&a[i]!=')')) { StackPush(S,a[i]); break; } else if(temp=='('&&a[i]==')') { StackPop(S,&temp); break; } else { StackPop(S,&temp); b[k][0]=temp; b[k][1]=0; k++; continue; } } continue; } if(a[i]!='~' && a[i]!='#' && a[i]!='&' && a[i]!='(' && a[i]!=')' && a[i]!='$') { j=0; while(a[i]!='~' && a[i]!='#' && a[i]!='&' && a[i]!='(' && a[i]!=')' && a[i]!='$') { b[k][j]=a[i]; j++; i++; } i--; b[k][j]=0; k++; } } return 0; }////////////////////////////////////////////////////////////////// BiTreeNode * gouzao(char b[100][100],int n)//从叶节点开始构造相应二叉树 { int i; BiTreeNode *p; BiTreeNode *q; BiTreeNode *o; SeqStack1 s; StackInitiate1(&s); for(i=0;i<n;i++) { p=(BiTreeNode *)malloc(sizeof(BiTreeNode)); strcpy(p->data,b[i]); p->rightChild=NULL; p->leftChild=NULL; p->father=NULL; if(b[i][0]=='~') { q=StackPop1(&s); p->rightChild=q; q->father=p; StackPush1(&s,p); } else if(b[i][0]=='#' || b[i][0]=='&') { q=StackPop1(&s); o=StackPop1(&s); q->father=p; o->father=p; p->leftChild=o; p->rightChild=q; StackPush1(&s,p); } else { StackPush1(&s,p); } } p=StackPop1(&s); return p; } int postorder(BiTreeNode *t,int b1[100],char b[100][100],int n)//后序遍历二叉树t { int n1,n2,i; if(t!=NULL) { n1=postorder(t->leftChild,b1,b,n); n2=postorder(t->rightChild,b1,b,n); if(t->data[0]=='~')//非运算 { if(n2==0) return 1; if(n2==1) return 0; } else if(t->data[0]=='&')//与运算 { if(n1==1 && n2==1) return 1; else return 0; } else if(t->data[0]=='#')//或运算 { if(n1==0 && n2==0) return 0; else return 1; } else { for(i=0;i<n;i++) { if(!(strcmp( b[i],t->data))) break; } return b1[i]; } } return 2; } ////////////////////////////////////////////////////////////////////////////////////////// int main() { char a[100],b[100][100]; int i,j,flag; int b1[1000];//表达式的值 int n; int zhi; SeqStack S; BiTreeNode *B; Initiate(&B); StackInitiate(&S); printf("\n\n\t\t\t欢迎使用! 命题演算公式真值的计算\n" ); printf("\n\n\t\t其中:<&代表'与'运算,#代表'或'运算,~代表'非'运算>\n\n"); printf("\n\t\t\t请输入表达式:"); scanf("%s",a); n=strlen(a); a[n]='$'; n=exchange(a,b,&S,n+1); //测试输出后序表达式// printf("\n\t\t\t输出公式的后缀形式: "); for(i=0;i<n;i++) { for(j=0;b[i][j]!=0;j++) { printf("%c",b[i][j]); } } //////////////////////////////// B=gouzao(b,n); while(1) { printf("\n\n\t\t\t表达式里的变量："); for(i=0;i<n;i++) { flag=0; if(b[i][0]!='~'&&b[i][0]!='&'&&b[i][0]!='#') { for(j=0;j<i;j++) { if(!strcmp(b[i],b[j])) {flag=1;break;} } if(flag==0) { puts(b[i]); printf("\n\t\t\t请输入此变量的真值(1:true 0:false)："); scanf("%d",&b1[i]); } else { b1[i]=b1[j]; } } else b1[i]=2; } zhi=postorder(B,b1,b,n); printf("\n\t\t\t得到此表达式的真值为：%d \n\n\t\t\t是否需要继续输入计算？（1.是,0.否）:",zhi); scanf("%d",&i); if(i==0) break; } return 0; }