expression.cpp

此文挡为数据结构课程设计

//---------------------------------------------------------------------------

#pragma hdrstop

//---------------------------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define NULL 0

typedef struct BiTNode
 {
  char data;
  struct BiTNode *rchild,*lchild;

 } BiTNode, *BiTree;

typedef struct
 {
  char ch;
  char num;
  int length;
  }SqList;
 SqList store[27];

int A[5][5]={{1,1},{1,1},{1,1,1,1},{1,1,1,1},{1,1,1,1,1}};

int choose_ask	(char ch)
{
  if((ch>=48&&ch<=57)||(ch>=97&&ch<=122))
  return(0);
  else return(1);
 }

void output(BiTree T)
{
  if(T==NULL) return;
  output(T->lchild);
  printf("%c",T->data);
  output(T->rchild);
}

void ReadExpr(BiTree *T)
{
 char t;
 t=getchar();
 while(!(t==42||t==43||t==45||t==47||t==94||(t>=97&&t<=122)||(t>=48&&t<=57)))
 t=getchar();
 if(t!=' ')
  {
   *T=(BiTree)malloc(sizeof(BiTNode));
   (*T)->data=t;
   if(!choose_ask((*T)->data))
    {(*T)->lchild=NULL;(*T)->rchild=NULL;return;}
   ReadExpr(&((*T)->lchild));
   ReadExpr(&((*T)->rchild));
  }
 return;
 }

int Mark(char mark1,char mark2)
{
 int i,j;
  switch(mark1)
   {
     case '+':i=0;break;
     case '-':i=1;break;
     case '*':i=2;break;
     case '/':i=3;break;
     case '^':i=4;break;
     default:break;
    }
  switch(mark2)
    {
     case '+':j=0;break;
     case '-':j=1;break;
     case '*':j=2;break;
     case '/':j=3;break;
     case '^':j=4;break;
     default:break;
    }
 return(A[i][j]);
}

void WriteExpr(BiTree T)
{
 int i=0;
 if(T==NULL)return;
 if(choose_ask(T->data)&&choose_ask(T->lchild->data))
  {
   if(Mark(T->data,T->lchild->data))
    {
     printf("(");
     i=1;
    }
   }
 WriteExpr(T->lchild);
 if(i==1) {i=0;printf(")");}
 printf("%c",T->data);
 if(choose_ask(T->data)&&choose_ask(T->rchild->data))
   {
    if(Mark(T->data,T->rchild->data))
    {
     printf("(");
     i=1;
     }
    }
 WriteExpr(T->rchild);
 if(i==1) {i=0;printf(")");}
}

Find_X(BiTree T)
{
 if(T==NULL) return;
 if(T->data>=97&&T->data<=122) store[T->data-96].ch=T->data;
 Find_X(T->lchild);
 Find_X(T->rchild);
 }

Input()
{
 int i;
 char ch;
 for(i=1;i<=26;i++)
 {
  if(store[i].ch)
  {
   ch=getchar();
   if(ch<=48||ch>=57) ch=getchar();
   store[i].num=ch;
   }
  }
}

Assign(BiTree T)
{
 char ch;
 if(T==NULL) return;
 if((T->data>=97)&&(T->data<=122))
 {
  if(store[T->data-96].num) T->data=store[T->data-96].num;
  else
       printf("error\n");
  }
 Assign(T->lchild);
 Assign(T->rchild);
 }

int operate(int sum1,int sum2,char ch)
{
 int sum,n;
 switch(ch)
   {
     case '+':sum=sum1+sum2;break;
     case '-':sum=sum1-sum2;break;
     case '*':sum=sum1*sum2;break;
     case '/':sum=sum1/sum2;break;
     case '^':{sum=1;
	       for(n=1;n<=sum2;n++) sum=sum1*sum;
	       break;
	       }
     default:break;
    }
 return(sum);
 }

int Value(BiTree T)
 {
   int sum,sum1,sum2;
   if(T==NULL) return(NULL);
   sum1=Value(T->lchild);
   sum2=Value(T->rchild);
   if(choose_ask(T->data)) sum=operate(sum1,sum2,T->data);
   else
      sum=T->data-48;
   return(sum);
 }


BiTree CompoundExpr(char P,BiTree E1,BiTree E2)
{
 BiTree T;
 T=(BiTree)malloc(sizeof(BiTNode));
 T->lchild=E1;
 T->rchild=E2;
 T->data=P;
 return(T);
}


main()
{int i,m;
 char ot,P;
BiTree T=0,M=0,New=0;
loop:
clrscr();      /*清屏*/
printf("\n\n");
printf("*-----------------------------------------------------------------------------*\n");
printf("*        Welcome         To          Use           My          Program        *\n");
printf("*                                                                             *\n");
printf("*       计算机科学与技术（9）班            邝嘉豪             3104006844      *\n");
printf("*-----------------------------------------------------------------------------*\n\n");
printf("                           表达式类型的实现Program                   \n");
printf("\n1.构造表达式及计算表达式");
printf("\n2.构造复合表达式");
printf("\n3.Exit");
printf("\n\n请输入要执行的操作(1/2/3):");
scanf("%d",&m);
switch(m)
{
case 1:
loop1:
printf("\n请输入正确的前缀表达式:");
ReadExpr(&T);
printf("\n输出的表达式为:");
WriteExpr(T);
if(Find_X(T))
{printf("\n\n输入的表达式含有变量:");
for(i=1;i<=26;i++)
   {
     if(store[i].ch) printf("'%c'",store[i].ch);
    }
printf("\n请依次输入变量的数值，并以逗号隔开:");
}
Input();
Assign(T);
printf("\n表达式的结果为:");
printf("%d",Value(T));
printf("\n\n是否继续进行“1.构造表达式及计算表达式”的操作?(y/n):");
ot=getchar();
while(!(ot=='y'||ot=='Y'||ot=='n'||ot=='N')) ot=getchar();
if(ot=='y'||ot=='Y')
{ for(i=1;i<=26;i++)
   {
     if(store[i].ch) store[i].ch=NULL;
    }
printf("\n");
goto loop1;}
else {
           for(i=1;i<=26;i++)
            {
             if(store[i].ch) store[i].ch=NULL;
            }
          goto loop;
      }

case 2:
 loop2:
   printf("\n请输入第一个正确的前缀表达式:");
   ReadExpr(&T);
   printf("输出的表达式为:");
   WriteExpr(T);
   printf("\n\n请输入另一个正确的前缀表达式:");
   ReadExpr(&M);
   printf("输出的表达式为:");
   WriteExpr(M);
   printf("\n\n请给复合表达式P输入正确的运算符号:");
   P=getchar();
   while(P!='+'&&P!='-'&&P!='*'&&P!='/'&&P!='^') P=getchar();
   New=CompoundExpr(P,T,M);
   printf("\n复合表达式为:");
   WriteExpr(New);
   if(Find_X(New))
   {printf("\n\n复合表达式含有变量:");
     for(i=1;i<=26;i++)
      {
         if(store[i].ch) printf("'%c'",store[i].ch);
        }
   printf("\n请依次输入变量的数值，并以逗号隔开：");
   }
   Input();
   Assign(New);
   printf("\n表达式的结果为:");
   printf("%d",Value(New));
   printf("\n\n是否继续进行“2.构造复合表达式”的操作?(y/n):");
   ot=getchar();
   while(!(ot=='y'||ot=='Y'||ot=='n'||ot=='N')) ot=getchar();
   if(ot=='y'||ot=='Y')
   { for(i=1;i<=26;i++)
     {
      if(store[i].ch) store[i].ch=NULL;
     }
     printf("\n");
      goto loop2;}
    else {
           for(i=1;i<=26;i++)
            {
             if(store[i].ch) store[i].ch=NULL;
            }

          goto loop;
         }
 }
}

//---------------------------------------------------------------------------