【实验一】
停车场管理系统
设计要求
1.问题描述
设计一个停车场管理系统，模拟停车场运作，此程序具备以下功能：
（1）若车辆到达，则显示汽车在停车场内或便道上的停车位置；
（2）若车辆离开，则显示汽车在停车场内停留的时间和应缴纳的费用（在便道上停留的时间不收费）；
2.需求分析
（1）要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。
（2）要求处理的数据元素包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去时刻。
（3）要求栈以顺序结构实现，队列以链表实现。
概要设计
1. 主界面设计
为了实现“停车管理系统”的各项功能，首先为系统设计一个含有多个菜单的主控菜单子程序，以链接系统的各项子功能，方便用户使用本系统。系统主控菜单运行界面如下：
2. 存储结构设计
本系统采用顺序栈模拟停车场管理操作，以链表队列模拟便道停车管理操作。以下是本系统中涉及的存储结构的定义：
typedef struct{
int *base;
int *top;
int stacksize;
int cartime[m];
int chepaihao[m];
}SqStack;//栈的顺序存储表示
struct List
{
int A[m+n]; //记录车牌号信息
int B[m+n];//记录车辆到达时选择的车位号
int len;//表示数组中元素个数
}L;
typedef struct QNode
{
//链队列元素结点类型
int data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct
{
//链队列类型
QueuePtr front;
QueuePtr rear;
}LinkQueue;
3.系统主要功能设计
本系统共采用3个功能模块，每个模块中又各自包含自己的子功能，各功能模块如下：
1.车辆到达；该模块将给用户提供两种停车选择，是场内停车还是便道停车方式，便于用户选择。
2.车辆离开；用户进入该界面，只要输入相关信息，系统将会显示用户在该停车场内停留的时间以及是否需要支付相应金额的停车费用等。
3.退出系统；方便用户退出本系统。
模块设计
1. 模块设计
本程序包含4个模块，它们分别是：主程序模块、菜单选择模块、栈操作模块、队列操作模块。调用关系如图所示：
2. 系统子程序及功能设计
1) void Initshuzu() //初始化数组
2) void time() //时间函数
3) void chepaihao() //输入的车牌号
4) void InitStack(SqStack &S) //构造一个空栈s
5) void push(SqStack &S,int e) //车辆进入停车场场内停车
6) void pop(SqStack &S,int e) //车辆离开停车场场内
7) void InitQueue(LinkQueue &Q) //构造一个空队列Q
8) void EnQueue(LinkQueue &Q,int elem) //车辆进入便道
9) void DeQueue(LinkQueue &Q ,int &e) //车辆离开便道
10) void tingchefangshi() //选择停车方式，场内停车还是便道停车
11) void likai() //车辆离开
12) void main() //主函数
3. 函数主要调用关系图
详细设计
1.数据类型定义
（1）栈的顺序存储结构体定义
typedef struct{
int *base;
int *top;
int stacksize;
int cartime[m];
int chepaihao[m];
}SqStack;
（2）数组的结构体定义
struct List
{
int A[m+n]; //记录车牌号信息
int B[m+n];//记录车辆到达时选择的车位号
int len;//表示数组中元素个数
}L;
（3）链队列元素结点的结构体定义
typedef struct QNode
{
int data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
（4）全局变量定义
int z;
time_t a[m+n],end;
double A[m+n]={0};
int count1=0,count2=0;//count1、count2分别用来统计场内停车数和便道停车数，并且初始化为0
2.系统主要子程序设计
（1）车辆进入停车场场内停车
void push(SqStack &S,int e)
{//车辆进入停车场场内停车
int stacksize=50;
if(S.top-S.base>=stacksize){//栈满，追加存储空间
S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));
if (!S.base) exit(OVERFLOW );
S.top=S.base+S.stacksize;
S.stacksize +=STACKINCREMENT;
}
*S.top++=e;
}//push
（2）车辆进入便道停车
void EnQueue(LinkQueue &Q,int elem)
{//车辆进入便道
QNode *s;
s=(QueuePtr)malloc(sizeof(QNode));
if(!s) exit(OVERFLOW);
s->data=elem;
s->next=NULL;
Q.rear->next=s;
Q.rear=s;
}
（3）车辆离开场内
void pop(SqStack &S,int e)
{//车辆离开停车场场内
e=*--S.top;
}//pop
（4）车辆离开便道
void DeQueue(LinkQueue &Q ,int &e)
{//车辆离开便道
QNode *t;
if(Q.front==Q.rear)
{
printf("便道内无任何车辆\n");
exit(1);
}
else
{
t=Q.front->next;
e=t->data;
Q.front->next=t->next;
if(Q.rear==t) Q.rear=Q.front;
free(t);
}
}
（5）选择停车方式
void tingchefangshi()
{//选择停车方式，场内停车还是便道停车
printf(" 请选择您的停车方式:\n");
printf(" 1. 场内停车 \n");
printf(" 2. 便道停车 \n");
scanf("%d",&z);
switch(z)
{
case 1:
{if(count1<=m){
printf(" 您选择的是： 1. 场内停车\n");
printf(" 您的车位是：%d 号车位\n",count1);
chepaihao();
printf("\n");
printf(" 从现在开始为您计时，您的到达时间是：\n");
time();
a[count1]=time(NULL);
count1++;
push(S,count1);
}
else printf(" 当前车位已满，请选择其他停车方式\n");
break;
return;
}
case 2:
{if(count2<=n){
printf(" 您选择的是 2.便道停车\n");
printf(" 您的车位是：%d 号车位\n",count2+m);
EnQueue(Q,count2);
chepaihao();
printf("\n");
printf(" 从现在开始为您计时，您的到达时间是：\n");
time();
a[count2]=time(NULL);
count2++;
EnQueue(Q,count2);
}
else printf(" 当前车位已满，请选择其他停车方式\n");
break;
return;
}
default : printf(" 您的输入有误，请重新输入!\n");
return;
}
getch();
}
（6）车辆离开函数
void likai()
{
int i;
printf(" 请输入您的车位号：\n");
scanf("%d",&i);
if(i>=0 && i<=m)
{
end=time(NULL);
A[i]=difftime(end,a[i]);
printf(" 您在停车场内停留时间为：%0.2f 秒\n",difftime(end,a[i]));
printf(" 您所需支付金额为：%0.2f 元\n",difftime(end,a[i])*j);
printf(" 感谢您的使用，欢迎下次光临！");
count1--;
}
else if(i>m && i<=m+n)
{
end=time(NULL);
A[i]=difftime(end,a[i]);
printf(" 您在停车场内停留时间为：%0.2f 秒\n",difftime(end,a[i]));
printf(" 您的服务是免费服务，感谢您的使用，欢迎下次光临！");
count1--;
}
else printf(" 您的输入有误，请重新输入！");
}
测试分析
系统运行主界面如下：
1. 车辆到达界面
车辆到达后需要选择相应的停车方式，主要有两种方式，场内停车方式和便道停车方式。
2. 车辆离开界面
车辆离开时需要输入自己的车位号，系统会自动判别你的停车方式，提供相关服务
3. 车辆进入场内停车
4. 车辆进入便道停车
5. 车辆离开场内
6. 车辆离开便道
源程序清单
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<conio.h>
#include<time.h>
#include<string.h>
#define m 50//停车场内总容纳量m，车位号依次为：1—50
#define n 50 //停车场便道容纳量n，车位号依次为：51-100
#define p 3 //车牌号码的位数000-999
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OVERFLOW 0
#define T 100
int z;
time_t a[m+n],end;
double A[m+n]={0};
#define j 0.001 //停车场内收费标准0.001元/秒
int count1=0,count2=0;//count1、count2分别用来统计场内停车数和便道停车数，并且初始化为0
typedef struct{
int *base;
int *top;
int stacksize;
int cartime[m];
int chepaihao[m];
}SqStack;//栈的顺序存储表示
struct List
{
int A[m+n]; //记录车牌号信息
int B[m+n];//记录车辆到达时选择的车位号
int len;//表示数组中元素个数
}L;
typedef struct QNode
{
//链队列元素结点类型
int data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct
{
//链队列类型
QueuePtr front;
QueuePtr rear;
}LinkQueue;
void Initshuzu()
{//初始化数组
for(int i=1;i<=m+n;i++)
L.B[i]=0;
L.len=0;
};
void time()
{//时间函数
time_t timep;
time (&timep);
printf(" 现在时刻：%s",ctime(&timep));
}
void chepaihao()
{//输入的车牌号
int ch[p];
int i;
printf("请输入您的车牌号：");
for(i=0;i<3;i++)
scanf("%d",&ch[i]);
printf("\n");
printf("您输入的车牌号码为：\n");
for(i=0;i<3;i++)
{
printf("%d",ch[i]);
}
}
void InitStack(SqStack &S){
//构造一个空栈s
S.base=(int *)malloc(STACK_INIT_SIZE * sizeof(int));
if(!S.base)exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}
SqStack S;
void push(SqStack &S,int e)
{//车辆进入停车场场内停车
int stacksize=50;
if(S.top-S.base>=stacksize){//栈满，追加存储空间
S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));
if (!S.base) exit(OVERFLOW );
S.top=S.base+S.stacksize;
S.stacksize +=STACKINCREMENT;
}
*S.top++=e;
}//push
void pop(SqStack &S,int e)
{//车辆离开停车场场内
e=*--S.top;
}//pop
void InitQueue(LinkQueue &Q)
{//构造一个空队列Q
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
}
LinkQueue Q;
void EnQueue(LinkQueue &Q,int elem)
{//车辆进入便道
QNode *s;
s=(QueuePtr)malloc(sizeof(QNode));
if(!s) exit(OVERFLOW);
s->data=elem;
s->next=NULL;
Q.rear->next=s;
Q.rear=s;
}
void DeQueue(LinkQueue &Q ,int &e)
{//车辆离开便道
QNode *t;
if(Q.front==Q.rear)
{
printf("便道内无任何车辆\n");
exit(1);
}
else
{
t=Q.front->next;
e=t->data;
Q.front->next=t->next;
if(Q.rear==t) Q.rear=Q.front;
free(t);
}
}
void tingchefangshi()
{//选择停车方式，场内停车还是便道停车
printf(" 请选择您的停车方式:\n");
printf(" 1. 场内停车 \n");
printf(" 2. 便道停车 \n");
scanf("%d",&z);
switch(z)
{
case 1:
{if(count1<=m){
printf(" 您选择的是： 1. 场内停车\n");
printf(" 您的车位是：%d 号车位\n",count1);
chepaihao();
printf("\n");
printf(" 从现在开始为您计时，您的到达时间是：\n");
time();
a[count1]=time(NULL);
count1++;
push(S,count1);
}
else printf(" 当前车位已满，请选择其他停车方式\n");
break;
return;
}
case 2:
{if(count2<=n){
printf(" 您选择的是 2.便道停车\n");
printf(" 您的车位是：%d 号车位\n",count2+m);
EnQueue(Q,count2);
chepaihao();
printf("\n");
printf(" 从现在开始为您计时，您的到达时间是：\n");
time();
a[count2]=time(NULL);
count2++;
EnQueue(Q,count2);
}
else printf(" 当前车位已满，请选择其他停车方式\n");
break;
return;
}
default : printf(" 您的输入有误，请重新输入!\n");
return;
}
getch();
}
void likai()
{
int i;
printf(" 请输入您的车位号：\n");
scanf("%d",&i);
if(i>=0 && i<=m)
{
end=time(NULL);
A[i]=difftime(end,a[i]);
printf(" 您在停车场内停留时间为：%0.2f 秒\n",difftime(end,a[i]));
printf(" 您所需支付金额为：%0.2f 元\n",difftime(end,a[i])*j);
printf(" 感谢您的使用，欢迎下次光临！");
count1--;
}
else if(i>m && i<=m+n)
{
end=time(NULL);
A[i]=difftime(end,a[i]);
printf(" 您在停车场内停留时间为：%0.2f 秒\n",difftime(end,a[i]));
printf(" 您的服务是免费服务，感谢您的使用，欢迎下次光临！");
count2--;
}
else printf(" 您的输入有误，请重新输入！");
}
//主函数
void main()
{
system("color 1f");
system("mode con:cols=90 lines 35");
Initshuzu();
InitStack(S);
InitQueue(Q);
while(1)
{
printf("\n ***************************** 欢迎光临ABC停车场 ***************************** \n");
printf("\n \n");
printf(" 1.车辆到达\n");
printf(" 2.车辆离开\n");
printf(" 3.退出系统\n\n");
time();
printf("\n 提示：选择后按回车键进入下一步操作\n ");
printf("\n \n");
printf("\n ***************************** 欢迎光临ABC停车场 ***************************** \n");
printf( "请选择您所需服务: ");
int c;
scanf("%d",&c);
switch(c)
{
case 1:
{
system("cls");
printf("\n ***************************** 车辆到达界面 ***************************** \n");
tingchefangshi();
getch();
system("cls");
break;
}
case 2:
{
system("cls");
printf("\n ***************************** 车辆离开界面 ***************************** \n");
likai();
getch();
system("cls");
break;
}
return;
getch();system("cls");
case 3:
return;
getch();
system("cls");
default:printf(" 您的输入有误！请重新输入：\n");
getch();
system("cls");
}
}
}
用户手册
1. 本程序执行程序文件为“停车管理系统.exe”。
2. 车辆进入停车场，场内允许及便道允许停车数分别为50个车位，依次为0-49和50-99，用户可根据自己需要进行适当更改，不影响程序执行。
3. 程序中车牌号暂假定为3位，请用空格键隔开，否则将出现差错。
4. 程序内每一界面跟换需要敲两次回车键方才有效，方便用户确认录入信息是否正确无误。
【实验二】
重言式判别问题
设计要求
1. 问题描述
一个逻辑表达式如果对于其变元的任一种取值都为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式；然而，更多的情况下，既非重言式，也非矛盾式。试写一个程序，通过真值表判断一个逻辑表达式属于上述哪一种类型。
2. 需求分析
（1）逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括“｜”、“＋”、“－”，分别表示或、与、非，运算优先程度递增，但可有括号改变，即括号内的运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有多个空格符。
（2）若是重言式或矛盾式，可以只显示“True Forever”或“False Forever”，否则显示“Satisfactible”以及变量名序列，与用户交互。若用户对表达式中变元取定一组值，程序就求出显示逻辑表达式的值。
概要设计
1. 主界面设计
2. 存储结构设计
为实现上述程序功能，应以有序链表表示集合。为此，需要抽象数据类型：栈和二叉树。
TYPE bpointer=^bnode;
bnode=RECORD
data: char;
val: boolean;
lchild,rchild: bpointer
END;
3. 系统功能设计
该系统主要包含三大功能：
1） 逻辑表达式的判别(不显示各种取值组合的结果)
2） 逻辑表达式的判别(并显示各种取值组合的结果)
3） 逻辑表达式的求值(根据用户的取值)
模块设计
1. 模块设计
该系统主要包含5个模块：
1) 主程序模块
2) 对栈的操作模块
3) 二叉树的建立模块
4) 逻辑运算符的优先级判别模块
5) 重言式的判别模块。
其调用关系如图所示
2. 系统子程序及功能设计
（1） void creatzuhe(int n)//用于产生变量的各种取值组合;
（2） void create(bitree &zigen,bitree l,bitree r)//自底向上地根据运算符的优先级来建立分子树函数;当逻辑表达式读完后-子根zigen就是一棵完整的二叉树；
（3） char youxianji(char lie,char hang)//逻辑运算符的优先级判别；
（4） void creatstack(sqstack &st)//对操作符栈和变量堆栈的操作；
（5） void creattree(char s[],bitree &tree)//重言式的识别函数；
（6） int value_tree(bitree tree)//根据变量的取值组合并利用逻辑表达式的性质对树进行求值；
（7） void user()//用户设定变量的一种取值；
（8） void push(sqstack &st,bitree e)；
（9） void pop(sqstack &st,bitree &e)；
（10）void gettop(sqstack &st,bitree &e)；
（11）void main()//主函数；
3. 函数主要调用关系
函数主要调用关系如下图所示
详细设计
1.数据类型定义
（1）二叉树结点定义
typedef struct btdnode{
char data;
struct btdnode *lchild;
struct btdnode *rchild;
}*bitree;
（2）表达式使用的堆栈定义
typedef struct lnode_optr{
struct btdnode **base; //栈中的元素都是树的结点结构；
struct btdnode **top;
int stacksize;
}sqstack;
（3）全局变量及宏定义
#define stack_size_normal 100
#define bianliang_max 20
#define str_max 60
int zuhe[bianliang_max];//变量的取值组合数组定义;
int N;//变量个数;
3. 系统主要子程序设计
（1）用于产生变量的各种取值组合;
void creatzuhe(int n)
{
int i,num=0,j=0,e;
int temp[bianliang_max];
for(i=0;i<N;i++)
zuhe[i]=0;
while(n)
{
e=n%2;
num++;
temp[j++]=e;
n=n/2;
}
j=j-1;
num=N-num;
while(j>=0)
{
e=temp[j--];
zuhe[num++]=e;
}
}
（2）自底向上地根据运算符地优先级来建立分子树函数;当逻辑表达式读完后-子根zigen就是一棵完整的二叉树
int k=0;//建树的标志，k＝1表示第一次建立分子树，要对左右孩子的指针域处理
void create(bitree &zigen,bitree l,bitree r)
{
zigen->lchild=l;
zigen->rchild=r;//分树的链接
if(l&&r)
{
if(int(l->data)>=65&&int(l->data)<=90)
{
l->lchild=NULL;
l->rchild=NULL;
}
if(int(r->data)>=65&&int(r->data)<=90)
{
r->lchild=NULL;
r->rchild=NULL;
}
}
}
（3）逻辑运算符的优先级判别；
char youxianji(char lie,char hang)
{
int i,j;
char bijiao[7][7]={' ','|','&','~','(',')','#',
'|','>','<','<','<','>','>',
'&','>','>','<','<','>','>',
'~','>','>','>','<','>','>',
'(','<','<','<','<','=',' ',
')','>','>','>',' ','>','>',
'#','<','<','<','<',' ','='};
for(i=0;i<7;i++)
if(bijiao[0][i]==lie)
break;
for(j=0;j<7;j++)
if(bijiao[j][0]==hang)
break;
return bijiao[j][i];
}
（4）对操作符栈和变量堆栈的操作；
void creatstack(sqstack &st)
{
st.base=(bitree*)malloc(stack_size_normal*sizeof(btdnode));
if(!st.base) exit(0);
st.top=st.base;
st.stacksize=stack_size_normal;
}
void push(sqstack &st,bitree e)
{
if(st.top-st.base<st.stacksize)
*st.top++=e;
else exit(0);
}
void pop(sqstack &st,bitree &e)
{
if(st.top==st.base) exit(0);
e=*--st.top;
}
void gettop(sqstack &st,bitree &e)
{
if(st.top==st.base) exit(0);
e=*(st.top-1);
}
（5）重言式的识别函数；
void creattree(char s[],bitree &tree)
{
sqstack variable; //变量栈;
sqstack logic; //逻辑运算符栈;
creatstack(variable);
creatstack(logic);
bitree logic_di,variables,logics,e,a,b,theta,kuohao; //定义栈中的元素;
//theta为最后的二叉树的根;
logic_di=(bitree)malloc(sizeof(btdnode));
if(!logic_di) exit(0);
logic_di->data='#';
push(logic,logic_di);
while(*s!=NULL)
{
if(int(*s)>=65&&int(*s)<=90)
{
variables=(bitree)malloc(sizeof(btdnode));
if(!variables) exit(0);
variables->data=*s;
push(variable,variables);
}
else if(int(*s)>90||int(*s)<65)
{
gettop(logic,e);//取运算符栈的栈顶元素进行优先级比较
switch(youxianji(*s,e->data))
{
case '<': //栈顶的运算符优先级低,逻辑运算符进栈
logics=(bitree)malloc(sizeof(btdnode));
if(!logics) exit(0);
logics->data=*s;
push(logic,logics);
break;
case '='://脱括号并接受下一个字符;
pop(logic,kuohao);break;
case '>':pop(logic,theta);//弹出逻辑运算符
pop(variable,a);//弹出变量
b=NULL;
if(theta->data!='~')
pop(variable,b);
//建树的函数调用
k=k+1;
create(theta,b,a);
push(variable,theta);//将临时的根作为新的变量压入变量栈中;
if(*s!='#'&&*s!=')')
{
logics=(bitree)malloc(sizeof(btdnode));
if(!logics) exit(0);
logics->data=*s;
push(logic,logics);
}
else s=s-1;
break;
}
}
s++;
}
tree=theta;
}
（6）根据变量的取值组合并利用逻辑表达式的性质对树进行求值；
int value_tree(bitree tree)
{
if(!tree) return 0; //遇到空的结点;
else if(tree->data!='|'&&tree->data!='&'&&tree->data!='~')//找到的是变量；
return zuhe[int(tree->data)-65];
else if(int(tree->data)<65||int(tree->data)>90) //找到的是运算符;
switch(tree->data)
{
case '|': return(value_tree(tree->lchild)||value_tree(tree->rchild));
case '&': return(value_tree(tree->lchild)&&value_tree(tree->rchild));
case '~': return(!value_tree(tree->rchild));
}
}
（7）用户设定变量的一种取值；
void user()
{
int i;
cout<<"请依次输入你的变元取值"<<endl;
for(i=65;i<65+N;i++)
{
cout<<char(i)<<" = ";
cin>>zuhe[i-65];
}
}
测试分析
测试各组数据如下所示：
(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
源程序清单
#include<stdlib.h>
#include<stdio.h>
#include<iostream.h>
#include<string.h>
#include<math.h>
#define stack_size_normal 100
#define bianliang_max 20
#define str_max 60
int zuhe[bianliang_max];//变量的取值组合数组定义;
int N;//变量个数;
typedef struct btdnode{//根据表达式建立的二叉树的结点定义;
char data;
struct btdnode *lchild;
struct btdnode *rchild;
}*bitree;
typedef struct lnode_optr{ //识别表达式使用的堆栈定义,它存放的都是树的结构;
struct btdnode **base; //栈中的元素都是树的结点结构；
struct btdnode **top;
int stacksize;
}sqstack;
void creatzuhe(int n)
{//用于产生变量的各种取值组合;
int i,num=0,j=0,e;
int temp[bianliang_max];
for(i=0;i<N;i++)
zuhe[i]=0;
while(n)
{
e=n%2;
num++;
temp[j++]=e;
n=n/2;
}
j=j-1;
num=N-num;
while(j>=0)
{
e=temp[j--];
zuhe[num++]=e;
}
}
int k=0;//建树的标志，k＝1表示第一次建立分子树，要对左右孩子的指针域处理
void create(bitree &zigen,bitree l,bitree r)
{//自底向上地根据运算符的优先级来建立分子树函数;当逻辑表达式读完后-子根zigen就是一棵完整的二叉树
zigen->lchild=l;
zigen->rchild=r;//分树的链接
if(l&&r)
{
if(int(l->data)>=65&&int(l->data)<=90)
{
l->lchild=NULL;
l->rchild=NULL;
}
if(int(r->data)>=65&&int(r->data)<=90)
{
r->lchild=NULL;
r->rchild=NULL;
}
}
}
char youxianji(char lie,char hang)
{//逻辑运算符的优先级判别；
int i,j;
char bijiao[7][7]={' ','|','&','~','(',')','#',
'|','>','<','<','<','>','>',
'&','>','>','<','<','>','>',
'~','>','>','>','<','>','>',
'(','<','<','<','<','=',' ',
')','>','>','>',' ','>','>',
'#','<','<','<','<',' ','='};
for(i=0;i<7;i++)
if(bijiao[0][i]==lie)
break;
for(j=0;j<7;j++)
if(bijiao[j][0]==hang)
break;
return bijiao[j][i];
}
void creatstack(sqstack &st)
{//对操作符栈和变量堆栈的操作；
st.base=(bitree*)malloc(stack_size_normal*sizeof(btdnode));
if(!st.base) exit(0);
st.top=st.base;
st.stacksize=stack_size_normal;
}
void push(sqstack &st,bitree e)
{
if(st.top-st.base<st.stacksize)
*st.top++=e;
else exit(0);
}
void pop(sqstack &st,bitree &e)
{
if(st.top==st.base) exit(0);
e=*--st.top;
}
void gettop(sqstack &st,bitree &e)
{
if(st.top==st.base) exit(0);
e=*(st.top-1);
}
void creattree(char s[],bitree &tree)
{//重言式的识别函数；
sqstack variable; //变量栈;
sqstack logic; //逻辑运算符栈;
creatstack(variable);
creatstack(logic);
bitree logic_di,variables,logics,e,a,b,theta,kuohao; //定义栈中的元素;
//theta为最后的二叉树的根;
logic_di=(bitree)malloc(sizeof(btdnode));
if(!logic_di) exit(0);
logic_di->data='#';
push(logic,logic_di);
while(*s!=NULL)
{
if(int(*s)>=65&&int(*s)<=90)
{
variables=(bitree)malloc(sizeof(btdnode));
if(!variables) exit(0);
variables->data=*s;
push(variable,variables);
}
else if(int(*s)>90||int(*s)<65)
{
gettop(logic,e);//取运算符栈的栈顶元素进行优先级比较
switch(youxianji(*s,e->data))
{
case '<': //栈顶的运算符优先级低,逻辑运算符进栈
logics=(bitree)malloc(sizeof(btdnode));
if(!logics) exit(0);
logics->data=*s;
push(logic,logics);
break;
case '='://脱括号并接受下一个字符;
pop(logic,kuohao);break;
case '>':pop(logic,theta);//弹出逻辑运算符
pop(variable,a);//弹出变量
b=NULL;
if(theta->data!='~')
pop(variable,b);
//建树的函数调用
k=k+1;
create(theta,b,a);
push(variable,theta);//将临时的根作为新的变量压入变量栈中;
if(*s!='#'&&*s!=')')
{
logics=(bitree)malloc(sizeof(btdnode));
if(!logics) exit(0);
logics->data=*s;
push(logic,logics);
}
else s=s-1;
break;
}
}
s++;
}
tree=theta;
}
int value_tree(bitree tree)
{//根据变量的取值组合并利用逻辑表达式的性质对树进行求值
if(!tree) return 0; //遇到空的结点;
else if(tree->data!='|'&&tree->data!='&'&&tree->data!='~')//找到的是变量；
return zuhe[int(tree->data)-65];
else if(int(tree->data)<65||int(tree->data)>90) //找到的是运算符;
switch(tree->data)
{
case '|': return(value_tree(tree->lchild)||value_tree(tree->rchild));
case '&': return(value_tree(tree->lchild)&&value_tree(tree->rchild));
case '~': return(!value_tree(tree->rchild));
}
}
void user()
{//用户设定变量的一种取值；
int i;
cout<<"请依次输入你的变元取值"<<endl;
for(i=65;i<65+N;i++)
{
cout<<char(i)<<" = ";
cin>>zuhe[i-65];
}
}
void main()
{ //主函数
system("color 1f");
system("mode con:cols=90 lines 35");
char str[str_max],string[str_max],*pstr;
int loop=20,choice,i=0,choose,sum;
bitree Tree;
while(loop)
{
pstr=str;
i=0;
int SUM=0,l; //用于累加变量的每种组合的逻辑表达式的结果;可以作为逻辑表达式类别判别的根据
cout<<"请输入逻辑表达式的变量的个数"<<endl;
cin>>N;
sum=int(pow(2,N)); //变量组合的总数;
cout<<"请输入逻辑表达式的表达式(或用'|',与用'&'和非用'~')"<<endl;
cin>>str;
//重言式的正确读取;
for(;*pstr!=NULL;pstr++)
if(*pstr!=' ') string[i++]=*pstr;
string[i]='#';
string[i+1]='\0';
cout<<" 请选择你所需操作 "<<endl;
cout<<" 1. 逻辑表达式的判别(不显示各种取值组合的结果) "<<endl;
cout<<" 2. 逻辑表达式的判别(并显示各种取值组合的结果)"<<endl;
cout<<" 3. 逻辑表达式的求值(根据用户的取值) "<<endl;
cout<<"请选择你所需操作: ";
cin>>choose;
switch(choose)
{
case 1://对变量的不同组合依次调用重言式二叉树的求值函数;并判别重言式的类别;
creattree(string,Tree);//建立重言式的二叉树;
for(loop=0;loop<sum;loop++)
{
creatzuhe(loop);//产生变量取值组合;
SUM+=value_tree(Tree);
}
string[i]='\0';
if(SUM==0) cout<<"逻辑表达式： "<<string<<" False forever"<<endl;
if(SUM==sum) cout<<"逻辑表达式： "<<string<<" True forever"<<endl;
if (SUM>0&&SUM<sum)cout<<"逻辑表达式： "<<string<<" Satisfactible"<<endl;
break;
case 2:creattree(string,Tree);//建立重言式的二叉树;
cout<<" 逻辑表达式变量组合的预算结果 "<<endl;
cout<<"---------------------------------------------"<<endl;
printf("| ");
for(l=65;l<65+N;l++)
printf("%-4c",l);
printf("逻辑表达式的值");
printf(" |\n");
cout<<"---------------------------------------------"<<endl;
for(loop=0;loop<sum;loop++)
{
creatzuhe(loop);//产生变量取值组合;
SUM+=value_tree(Tree);
printf("| ");
for(int h=0;h<N;h++)
printf("%-4d",zuhe[h]);
printf("%8d",value_tree(Tree));
printf(" |\n");
cout<<"-------------------------------------------"<<endl;
}
string[i]='\0';
if(SUM==0) cout<<"逻辑表达式： "<<string<<" False forever"<<endl;
else if(SUM==sum) cout<<"逻辑表达式： "<<string<<" True forever"<<endl;
else cout<<"逻辑表达式： "<<string<<" Satisfactible "<<endl;
break;
case 3: creattree(string,Tree);
user();
cout<<"逻辑表达式的值为："<<value_tree(Tree)<<endl;
break;
}
cout<<"是否继续进行运算？是按1/ 否按0:";
cin>>choice;
if(choice==0)
exit(0);
loop--;
}
}
用户手册
用户使用本系统，需先将表达式中左右变量的总个数输入，按回车键后输入表达式，选择所需操作，即可完成对表达式的求值和判别。