编绎原理.cpp

本程序的功能是：将中缀表达式（只能含有的运算符为( ) / * + - =）转化为后缀表达式

//    本程序的功能是：将中缀表达式（只能含有的运算符为( ) / * + - =）转化为后缀表达式，
//    它的实现过程为：把输入的中缀表达式放到一个字符数组中，然后从左至右扫描，直到找到
//    第一对括号，再对括号内的表达式进行从左至右扫描，只要一找到'/'或'*'，就把该运算
//    符放到新建立的二叉树结点中，该结点的左，右子树结点分别为：与该运算符相邻的左，右
//    字符,（当然,根结点中存放的是运算符，其它的变量或常量字符存放在叶子结点中）直到'/'
//    或'*'扫描完毕，然后对'+'，'-'采取相同的方法进行扫描，并建立二叉树，最后对'='也采
//    取相同的方法进行扫描，并建立二叉树。接着从第一对括号后采取相同的方法处理第2,3...n
//    对括号.当然，已经放入到二叉树结点中的字符，会留下访问过的标志'#',如果某个运算符相
//    邻的左字符或右字符是'#',则意味着该运算符所在结点的左子树或右子树不是一个叶子结点，
//    而是一棵二叉树，应当把左字符或右字符所在的树的根结点作为该运算符所在结点的左子树或
//    右子树.当括号处理完毕后，重新把字符数组从左至右扫描，采取前面相同方法构造二叉树，当
//    然，左括号和右括号不会留下访问过的标志'#'，因些在构造二叉树时可以通过判断运算符的左
//    字符或右字符是'('或')',把括号内的二叉树添加到该运算符所在结点的左子树或右子树中.
        


#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef struct Tnode
{
	char data;
    struct Tnode *lchild,*rchild,*parent;
}Tnode,*Bitree;

void PostOrder(Bitree root)  //中序遍历二叉树
{
	if(root==0)return;
	else
	{
		PostOrder(root->lchild);
		PostOrder(root->rchild);
		printf("%c",root->data);
	}

}

void main()
{
  Bitree t,s[80],p1,p2,p;
  char str[80];
  int len;
  int i,j,i1,i2,temp=0;
  printf("请输入正确的中缀表达式:");
  gets(str);
  len=strlen(str);
  for(i=0;i<80;i++)
	  s[i]=0;
  for(i=0;i<len;i++)
   {
      if(str[i]=='(')
		{
            i1=i;
			while(str[i]!=')'){i++;}
			i2=i;
			temp=1;
	    }
      if(temp==1){
       for(j=i1+1;j<i2;j++){
            if(str[j]=='/'||str[j]=='*')
			{ 
              s[j]=(Bitree)malloc(sizeof(Tnode));
              if(str[j-1]=='#')
			   {
				  p=s[j-2];
				  while(p->parent!=0)
					  p=p->parent;
				  p1=p;
                  p->parent=s[j]; 
				  
			   }
			   else{ p1=(Bitree)malloc(sizeof(Tnode));p1->data=str[j-1];
			   p1->lchild=0;p1->rchild=0;p1->parent=s[j];str[j-1]='#';}
			   if(str[j+1]=='#')
			   {
                  p=s[j+2];
				  while(p->parent!=0)
					  p=p->parent;
				  p2=p;
				  p->parent=s[j];
			   }
			   else{p2=(Bitree)malloc(sizeof(Tnode));p2->data=str[j+1];
			   p2->lchild=0;p2->rchild=0;p2->parent=s[j];str[j+1]='#';}
		       s[j]->data=str[j];s[j]->lchild=p1;s[j]->rchild=p2;
			   str[j]='#';s[j]->parent=0;
			}
	   }


       for(j=i1+1;j<i2;j++){
		   if(str[j]=='+'||str[j]=='-')
		   {
              s[j]=(Bitree)malloc(sizeof(Tnode));
              if(str[j-1]=='#')
			   {
				  p=s[j-2];
				  while(p->parent!=0)
					  p=p->parent;
				  p1=p;
                  p->parent=s[j]; 
				  
			   }
			   else{ p1=(Bitree)malloc(sizeof(Tnode));p1->data=str[j-1];
			   p1->lchild=0;p1->rchild=0;p1->parent=s[j];str[j-1]='#';}
			   if(str[j+1]=='#')
			   {
                  p=s[j+2];
				  while(p->parent!=0)
					  p=p->parent;
				  p2=p;
				  p->parent=s[j];
			   }
			   else{p2=(Bitree)malloc(sizeof(Tnode));p2->data=str[j+1];
			   p2->lchild=0;p2->rchild=0;p2->parent=s[j];str[j+1]='#';}
		       s[j]->data=str[j];s[j]->lchild=p1;s[j]->rchild=p2;
			   str[j]='#';s[j]->parent=0;
		   }
	   }

       for(j=i1+1;j<i2;j++){
		   if(str[j]=='=')
		   {
              s[j]=(Bitree)malloc(sizeof(Tnode));
              if(str[j-1]=='#')
			   {
				  p=s[j-2];
				  while(p->parent!=0)
					  p=p->parent;
				  p1=p;
                  p->parent=s[j]; 
				  
			   }
			   else{ p1=(Bitree)malloc(sizeof(Tnode));p1->data=str[j-1];
			   p1->lchild=0;p1->rchild=0;p1->parent=s[j];str[j-1]='#';}
			   if(str[j+1]=='#')
			   {
                  p=s[j+2];
				  while(p->parent!=0)
					  p=p->parent;
				  p2=p;
				  p->parent=s[j];
			   }
			   else{p2=(Bitree)malloc(sizeof(Tnode));p2->data=str[j+1];
			   p2->lchild=0;p2->rchild=0;p2->parent=s[j];str[j+1]='#';}
		       s[j]->data=str[j];s[j]->lchild=p1;s[j]->rchild=p2;
			   str[j]='#';s[j]->parent=0;
		   }
	   }

	  }
   }

   for(j=0;j<len;j++)
   {
         if(str[j]=='/'||str[j]=='*')
			{ 
              s[j]=(Bitree)malloc(sizeof(Tnode));
              if(str[j-1]=='#')
			   {
				  p=s[j-2];
                  while(p->parent!=0)
					  p=p->parent;
				  p1=p;
                  p->parent=s[j]; 
				  
			   }
			  else if(str[j-1]==')')
			  {
				  p=s[j-3];
                  while(p->parent!=0)
					  p=p->parent;
				  p1=p;
                  p->parent=s[j]; 
			  }
			   else{ p1=(Bitree)malloc(sizeof(Tnode));p1->data=str[j-1];
			   p1->lchild=0;p1->rchild=0;p1->parent=s[j];str[j-1]='#';}
			  
			   if(str[j+1]=='#')
			   {
                  p=s[j+2];
				  while(p->parent!=0)
					  p=p->parent;
				  p2=p;
				  p->parent=s[j];
			   }
			   else if(str[j+1]=='(')
			   {
                  p=s[j+3];
				  while(p->parent!=0)
					  p=p->parent;
				  p2=p;
				  p->parent=s[j];
			   }
			   else{p2=(Bitree)malloc(sizeof(Tnode));p2->data=str[j+1];
			   p2->lchild=0;p2->rchild=0;p2->parent=s[j];str[j+1]='#';}
		       s[j]->data=str[j];s[j]->lchild=p1;s[j]->rchild=p2;
			   str[j]='#';s[j]->parent=0;
			}
   }

   for(j=0;j<len;j++)
   {
	   if(str[j]=='+'||str[j]=='-')
		   {
              s[j]=(Bitree)malloc(sizeof(Tnode));
              if(str[j-1]=='#')
			   {
				  p=s[j-2];
                  while(p->parent!=0)
					  p=p->parent;
				  p1=p;
                  p->parent=s[j]; 
				  
			   }
			  else if(str[j-1]==')')
			  {
				  p=s[j-3];
                  while(p->parent!=0)
					  p=p->parent;
				  p1=p;
                  p->parent=s[j]; 
			  }
			   else{ p1=(Bitree)malloc(sizeof(Tnode));p1->data=str[j-1];
			   p1->lchild=0;p1->rchild=0;p1->parent=s[j];str[j-1]='#';}
			  
			   if(str[j+1]=='#')
			   {
                  p=s[j+2];
				  while(p->parent!=0)
					  p=p->parent;
				  p2=p;
				  p->parent=s[j];
			   }
			   else if(str[j+1]=='(')
			   {
                  p=s[j+3];
				  while(p->parent!=0)
					  p=p->parent;
				  p2=p;
				  p->parent=s[j];
			   }
			   else{p2=(Bitree)malloc(sizeof(Tnode));p2->data=str[j+1];
			   p2->lchild=0;p2->rchild=0;p2->parent=s[j];str[j+1]='#';}
		       s[j]->data=str[j];s[j]->lchild=p1;s[j]->rchild=p2;
			   str[j]='#';s[j]->parent=0;
		   }
   }

    for(j=0;j<len;j++)
   {
	   if(str[j]=='=')
		   {
              s[j]=(Bitree)malloc(sizeof(Tnode));
              if(str[j-1]=='#')
			   {
				  p=s[j-2];
                  while(p->parent!=0)
					  p=p->parent;
				  p1=p;
                  p->parent=s[j]; 
				  
			   }
			  else if(str[j-1]==')')
			  {
				  p=s[j-3];
                  while(p->parent!=0)
					  p=p->parent;
				  p1=p;
                  p->parent=s[j]; 
			  }
			   else{ p1=(Bitree)malloc(sizeof(Tnode));p1->data=str[j-1];
			   p1->lchild=0;p1->rchild=0;p1->parent=s[j];str[j-1]='#';}
			  
			   if(str[j+1]=='#')
			   {
                  p=s[j+2];
				  while(p->parent!=0)
					  p=p->parent;
				  p2=p;
				  p->parent=s[j];
			   }
			   else if(str[j+1]=='(')
			   {
                  p=s[j+3];
				  while(p->parent!=0)
					  p=p->parent;
				  p2=p;
				  p->parent=s[j];
			   }
			   else{p2=(Bitree)malloc(sizeof(Tnode));p2->data=str[j+1];
			   p2->lchild=0;p2->rchild=0;p2->parent=s[j];str[j+1]='#';}
		       s[j]->data=str[j];s[j]->lchild=p1;s[j]->rchild=p2;
			   str[j]='#';s[j]->parent=0;
		   }
   }

 for(i=0;i<80;i++) //找出二叉树的根结点
	 if(s[i]!=0)
     {
		 t=s[i];
		 while(t->parent!=0)
			 t=t->parent;
	 }
  printf("该表达式的逆波兰表示为:");
  PostOrder(t);
  printf("\n");
}