bianyi.cpp

数据结构：设计存储中间结果及中间代码(逆波兰式)的数据结构； 算法：算符优先分析法的实现；

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

struct STRU
{
	char lei[3];
	char word[20];
        int  num;
};

typedef struct{				
	char nbl1[50];		
	char nbl2[50];			
}Nbl;

Nbl nbl;
int nbln=0;				
int n=0;				
int j=0;
int m=0;
int NQX;
int relatable[5][5]={
	2,  0,  -1,  -1,  2,
       -1,  2,   2,   2,  1,
	2,  1,   2,   2,  2,
	2,  1,   2,   2,  2,
       -1,  2,   2,   2,  0};
int yufa[100];
int yufatop=-1;
char content[200];
int  curpos=0;

void strcpy(char *str1,char *str2) 
{ 
	char *p1,*p2; 
	p1=str1; 
	p2=str2; 
	while(*p2) 
	*p1++=*p2++; 
} 

int strcmp(char *str1,char *str2) 
{ 
	char *p1,*p2; 
	p1=str1; 
	p2=str2; 
	while(*p2 && *p1) 
	if(*(p1++)- *(p2++) ) return *(p1++)- *(p2++) ; 
	return 0; 
} 

void push(int num)
{ 
	if(++yufatop>=100){ cout<<"yufa stack out of size!!"<<endl;return;}
    yufa[yufatop]=num;
}

int pop()
{   
	if(yufatop==-1){ cout<<"yufa stack is empty!!"; return 0;}
	return yufa[yufatop--];
}

int nextword()
{
	char word[20];
	int i=0;
	for(;curpos<200;curpos++)
	{
		if(content[curpos]!=' ') break;
	}
	for(;curpos<200;curpos++)
	{
		if(content[curpos]==' ') break;
		word[i++]=content[curpos];
	}
	word[i]='\0';
	if(strcmp(word,"while")==0){strcat(nbl.nbl2,"while "); return 0;}
	if(strcmp(word,"do")==0){strcat(nbl.nbl2,"do "); return 1;}
	if(strcmp(word,"true")==0){ return 2;}
	if(strcmp(word,"false")==0){ return 3;}
	if(strcmp(word,"#")==0){ return 4;}
	if(strcmp(word,"s")==0){ return 5;}
	return 6;
}

int prefresh(int *w,int top)
{
     while(relatable[w[top-1]][w[top]]!=-1 && top)
	 {
		 if(relatable[w[top-1]][w[top]]==2){"you code is not a valid code";}
		 top--;
	 }
	 return top-1;
}

void Gen(STRU *sy,char *lei1,int word1)
{
	char *p1;
	p1=lei1;
	strcpy(sy[NQX].lei,p1);
	if(strcmp(lei1,"jn")==0)
	{
		sy[NQX].lei[2]='\0';
	}
	else
	{
		sy[NQX].lei[1]='\0';
	}
	sy[NQX].num=0;
        switch(word1)
	{
	case 2:  
		strcpy(sy[NQX].word,"true");  sy[NQX].word[4]='\0';
		strcat(nbl.nbl1,"true ");
		break;
	case 3: 
		strcpy(sy[NQX].word,"false"); sy[NQX].word[5]='\0';
		strcat(nbl.nbl1,"false ");
		break;
	case 4: strcpy(sy[NQX].word,"_");     sy[NQX].word[1]='\0'; 	break;
	case 5: strcpy(sy[NQX].word,"action");sy[NQX].word[6]='\0'; 	break;
	default :cout<<"bool condition error!!"<<endl; return ;
	}
	NQX=NQX+1;
}

int merge(STRU *sy,int p1,int p2)
{
	int q;
	if(p1==0) return p2;
	q=p1;
	while(sy[q].num!=0) q=sy[q].num;
        sy[q].num=p2;
	return p1;
}

void backpatch(STRU *sy,int p,int t)
{
	int q;
	int m;
	q=p;
	while(q!=0)
	{
		m=sy[q].num;
		sy[q].num=t;
		q=m;
	}
}

void yuyi(int *word,int wordtop,STRU *sy)
{
       switch(word[wordtop])
	   {
	      case 0: push(NQX);break;
	      case 1: push(NQX-1);
              backpatch(sy,NQX-2,NQX);break;
              default : ; 
	   }	
}

void main(void)
{
   char fname[50];
   int word[50];
   int wordtop=-1;
   int prebegin=0;
   STRU stru[50];
   NQX=1;
   cout<<"文法如下："<<endl;
   cout<<"S-->while E do S"<<endl;
   cout<<"E-->true|false"<<endl;
   cout<<"please input the file name:"<<endl;
   gets(fname);
   ifstream infile(fname);
   if(! infile)
    {
	   cout<<fname<<" open fail!"<<endl;
	   return;
   }
   content[curpos++]='#';
   content[curpos++]=' ';
   infile.unsetf(ios::skipws);
   char ch;
   while(infile>>ch) { content[curpos++]=ch;}
   infile.close();
   content[curpos++]=' ';
   content[curpos++]='#';
   content[curpos++]='\0';
   curpos=0;
   word[++wordtop]=nextword();
   if(word[wordtop]==6)
   {
     cout<<"ellegal word : "<<word<<endl;
	 return;
   }
   if((word[++wordtop]=nextword())==6)
   {
     cout<<"ellegal word : "<<word<<endl;
	 return;
   }
   do{
	  if(word[wordtop]==5) { wordtop--; Gen(stru,"s",5);continue;}
	  if(relatable[word[wordtop-1]][word[wordtop]]==2)
	  {
		  cout<<"you code is not a valid code!!"<<endl;
		  return;
	  }
      else if(relatable[word[wordtop-1]][word[wordtop]]==-1)
	  {
		  prebegin=wordtop-1;
	  }
	  else if(relatable[word[wordtop-1]][word[wordtop]]==1) 
	  {
		  if(word[prebegin+1]==2||word[prebegin+1]==3 && (wordtop-prebegin)==2)
		  {
			  Gen(stru,"Jn",word[prebegin+1]);
			  Gen(stru,"J",4);
                          word[prebegin+1]=word[wordtop];
                          wordtop=prebegin+1;
			  prebegin=prefresh(word,wordtop);  
			  yuyi(word,wordtop,stru);
			  continue;
		  }
		  else if(word[prebegin+1]==0 && word[wordtop-1]==1 && (wordtop-prebegin)==3)
		  { 
			 int q;
                         Gen(stru,"J",4);
			 q=pop();
			 backpatch(stru,q,NQX);
			 q=pop();
			 backpatch(stru,NQX-1,q);
			 word[prebegin+1]=word[wordtop];
			 wordtop=prebegin+1;
			 prebegin=prefresh(word,wordtop);
			 yuyi(word,wordtop,stru);
			 continue;
		  }
		  else { cout<<"you code is not valid!!";}
	  }
	  else if(relatable[word[wordtop-1]][word[wordtop]]==0)
	  {
          if(word[0]==4 && word[1]==4)
		  {
			  cout<<"successful!"<<endl;
			  break;
		  }
	  }
	  if(word[wordtop]!=1)
	  {
		yuyi(word,wordtop,stru);
	  }
		if(word[wordtop]!='#')
		{
			if((word[++wordtop]=nextword())==6)
			{
				cout<<"you code error";
			}
		}
   }while(1); strcat(nbl.nbl1,"s ");
   cout<<"逆波兰式如下："<<endl;
   cout<<nbl.nbl1<<nbl.nbl2<<endl;
}