cys.cpp

这事一个重言式判定程序

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
char var[20];
char *expr;
int zuhe[20],i;
struct stack{
  char *base;
  char *top;
};
typedef struct bitree{
  char data;
  struct bitree *lchild,*rchild;
}*bitreeptr;
void initstack(stack &s)
{
	s.base=(char *)malloc(50*sizeof(char));
	s.top=s.base;
}
void gettop(stack s,char &e)
{
	if(s.top==s.base);
	e=*(s.top-1);
}
void push(stack &s,char e)
{
	*s.top++=e;
}
void pop(stack &s,char &e)
{
	if(s.top==s.base);
	e=*--s.top;
}
int readch(char s[])//读入表达式的字符串
{
	int j;
	char c;
	c=getchar();
	for(j=0;c!='\n';j++)
	{
		s[j]=c;
		c=getchar();
	}
	s[j]='\0';
	return j-1;
}
int compare(char a,char s[])
{
	int j=0;
	while(s[j]!='\0'&&a!=s[j])
		j++;
	if(a!=s[j])
		return 0;
	else
		return j;
}
char *mid_to_fro(char s[],int m,stack &a)//把中缀转化为前缀表达式
{
	int g=0,n=0,j=0;
	char *ch,e;
	ch=(char *)malloc(50*sizeof(char));
	var[0]='\0';
	while(s[g]!='\0')
	{
		if(s[g]!='('&&s[g]!=')')
			j++;
		g++;
	}
	ch[j]='\0';
	j--;
	while(m>=0)
	{
		if(s[m]==')')
			push(a,')');
		else if(s[m]=='|')
		{
			gettop(a,e);
			while(e=='&'||e=='~'||e=='|')
			{
				pop(a,ch[j--]);
				gettop(a,e);
			}
			push(a,'|');
		}
		else if(s[m]=='&')
		{
			gettop(a,e);
			while(e=='&'||e=='~')
			{
				pop(a,ch[j--]);
				gettop(a,e);
			}
			push(a,'&');
		}
		else if(s[m]=='~')
		{
			gettop(a,e);
			while(e=='~')
			{
				pop(a,ch[j--]);
				gettop(a,e);
			}
			push(a,'~');
		}
		else if(s[m]=='(')
		{
			gettop(a,e);
			while(e!=')')
			{
				pop(a,ch[j--]);
				gettop(a,e);
			}
			pop(a,e);
		}
		else if((s[m]>64&&s[m]<91)||(s[m]<123&&s[m]>96))
		{
			ch[j--]=s[m];
			if(compare(s[m],var)==0)
			{
				var[n++]=s[m];
				var[n]='\0';
			}
		}
		m--;
	}
	while(a.top!=a.base)
		pop(a,ch[j--]);
	return ch;
}
bitreeptr creatbitree(bitreeptr T)  //用所得的前缀表达式先序创建二叉树
{
  int t;//i=0;
  T=(bitree *)malloc(sizeof(bitree));
  if(expr[i]=='~')
  {
	  T->data=expr[i++];
	  creatbitree(T->lchild);
	  T->rchild=NULL;
  }
  else if((expr[i]>64&&expr[i]<91)||(expr[i]<123&&expr[i]>96))
  {
	  t=compare(expr[i++],var);
	  T->data=zuhe[t];
	  T->lchild=NULL;
	  T->rchild=NULL;
  }
  else
  {
	  T->data=expr[i++];
	  creatbitree(T->lchild);
	  creatbitree(T->rchild);
  }
  return T;
}
void creatzuhe(int n)
{
	int t,j,l=0,num=0,temp[20];
	t=strlen(var);
	for(j=0;j<t;j++)
		zuhe[j]=0;
	for(;n!=0;n/=2)
	{
		num++;
		temp[l++]=n%2;
	}
	l--;
	num-=t;
	while(l>=0)
		zuhe[num++]=temp[l--];
}
int value(char c,int a,int b)  
{
	switch(c)
	{
	case '|':
		return a||b;
    case '&':
		return a&&b;
	default:
		break;
	}
}
int preorderval(bitreeptr &T)//先序遍历二叉树,以求值.
{
	if(T->rchild!=NULL&&T->lchild!=NULL)
		return value(T->data,preorderval(T->lchild),preorderval(T->rchild)); 
	else if(T->rchild==NULL&&T->lchild!=NULL)
		return !(T->lchild->data);
	else if(T->rchild==NULL&&T->lchild==NULL)
		return T->data;
}
void main()
{
	int num1,num2,w,nvar=1,j;
	int result[100];
	char s[50],d[2];
	stack st;
	bitreeptr T;
	initstack(st);
	printf("请输入逻辑表达式:");
	num1=readch(s);
	expr=mid_to_fro(s,num1,st);
	w=strlen(var);
	for(j=0;j<w;j++)
		nvar*=2;
	printf("以下是程序的功能：\n“1”为判别表达式是否为重言式\n“2”为输入变量的值求结果\n");
	printf("请输入你的指令:");
	scanf("%s",d);
	if(d[0]=='1')//判断是否为重言式
	{
		for(w=0;w<nvar;w++)
		{
			creatzuhe(w);
			i=0;
			T=creatbitree(T);
			result[w]=preorderval(T);
		}
		for(w=0;w<(nvar-1)&&result[w]==result[w+1];w++);
		if(w==nvar)
		{
			if(result[0]==1)
				printf("Ture forever.\n");
			else
				printf("False forever.\n");
		}
		else
			printf("Satisfactible.\n");
	}
}