bitree.h

实现基于二叉树表示的算术表达式Expression的操作

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct BiTNode{
	char data;
	int nu;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef int status;
status Sign(char a)
{
	if(a=='+'||a=='-'||a=='*'||a=='/'||a=='^') return 1;
	else return 0;
}
char a[50];
int i=0;
status Num(char c)
{
	if(c<='9'&&c>='0')return 1;
	else return 0;
}

status Creat(BiTree &T)
{ 
	while(a[i]!='\0'){
	
   if(Sign(a[i]))
   {
      if (!(T=(BiTNode *)malloc(sizeof (BiTNode)))) return 0;
      T->data=a[i];
      i++;
	Creat(T->lchild);
	Creat(T->rchild);
	return 1; 
	}
   else {
	   if (!(T=(BiTNode *)malloc(sizeof (BiTNode)))) return 0;
	   T->data=a[i];
       T->lchild=T->rchild=NULL;
	   i++;return 1;}
	}

}
/*
typedef struct NodeType{
	char * ch;
	struct NodeType * next;
}*Node;
typedef struct stack{
	Node head;
	int size;
}stack;
void InitStack(stack &S)
{//初始化栈
   S.head=NULL;
   S.size=0;
}
status MakeNode(Node &p,char *ch)
{
	 p=(Node)malloc(sizeof(NodeType));
	 if(!p) return 0;
	 p->ch=ch;p->next=NULL;
     return 1;
   
}
status Push(stack &S,char *ch)
{   
	Node p;
	if(!MakeNode(p,ch))return 0;
	p->next=S.head;S.head=p;S.size++;
	return 1;
}
status Pop(stack &S,char *e)
{
    Node p;p=S.head;
	if(S.head==NULL) return 0;
	else{
	e=S.head->ch;S.head=p->next;
	S.size--;free(p);return 1;}      
}*/
char OP[5]={'+','-','*','/','^'};
int precede[5][5]={
2,2,2,2,2,
1,1,2,2,2,
1,1,2,2,1,
1,1,1,1,1,
1,1,1,1,1};

int Precede(char b,char c)
{
   int a;
   int s;
   int i;
	for(i=0;i<5;i++)
	{
	if(b==OP[i]) a=i;
	if(c==OP[i]) s=i;
	}
	   switch(precede[a][s])
	   {
	   case 1: return 1;
       case 2: return 0;
	   }
}

status Letter(char c)
{
	if((c>='a'&&c<='z')||(c>='A'&&c<='Z'))return 1;
	else return 0;
}

status Caclue(BiTree &T)
{  
	int n,c;
   if(Sign(T->data))
   {
      if(T->lchild->data=='#'&&T->rchild->data=='#')
	  {
      switch(T->data)
	  {
            case '+': T->nu=(T->lchild->nu)+(T->rchild->nu);break;
			case '-': T->nu=(T->lchild->nu)-(T->rchild->nu);break;
			case '*': T->nu=(T->lchild->nu)*(T->rchild->nu);break;
			case '/': T->nu=(T->lchild->nu)/(T->rchild->nu);break;
			case '^': for(n=1,c=T->lchild->nu;n<T->rchild->nu;n++)
						c*=T->lchild->nu; T->nu=c;break;
	  }
		T->data='#';
		free(T->lchild);
		free(T->rchild);
		T->lchild=T->rchild=NULL;
	  }
     else
	 {
		Caclue(T->lchild);
		Caclue(T->rchild);
	 }

   }return 1;
}