magic language.c

魔王语言的实现 里面有详细的报告与源程序实现魔王语言的翻译 是栈与队列的运用与实现

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

#define OK 1 
#define ERROR 0 
#define NULL 0 
#define OVERFLOW -2 
#define MAXSIZE 100 
#define stack_init_size 100 
#define Sincremen 10 

char e; 
char mag[MAXSIZE]; 

/**************栈及其基本操作 **********************/
typedef struct
{
 char *base; 
 char *top; 
 int stacksize; 
}sqstack; 

int in_stack (sqstack *s) 
{ 
 s->base=(char *)malloc(stack_init_size*sizeof(char)); 
 if(!s->base) exit (OVERFLOW); 
 s->top=s->base; 
 s->stacksize=stack_init_size; 
 return OK; 
}/*创建栈*/ 

int push (sqstack *s,char e) 
{ 
 if(s->top-s->base>=s->stacksize) 
 { 
  s->base=(char *) realloc(s->base,(s->stacksize+Sincremen)*sizeof(char)); 
  if(!s->base) exit(OVERFLOW); 
  s->top=s->base+s->stacksize; 
  s->stacksize+=Sincremen; 
 } 
 *(s->top++)=e; 
 return OK; 
}/*入栈*/ 

int pop(sqstack *s,char *e) 
{ 
if(s->top==s->base) return ERROR; 
*e=*(--(s->top)); 
return OK; 
}/*出栈*/ 

/*****************队列及其基本操作 ********************/
typedef struct qnode 
{ 
 char data; 
 struct qnode *next; 
}qnode,*queueptr; 

typedef struct 
{ 
 queueptr front; 
 queueptr rear; 
}linkqueue; 

int initqueue(linkqueue *q) 
{ 
 q->front=q->rear=(queueptr)malloc(sizeof(qnode)); 
 if(!q->front) exit(OVERFLOW); 
 q->front->next=NULL; 
 return OK; 
}/*创建队列*/ 

int enqueue(linkqueue *q,char e) 
{ 
 queueptr p; 
 p=(queueptr)malloc(sizeof(qnode)); 
 if(!p) exit(OVERFLOW); 
 p->data=e; 
 p->next=NULL; 
 q->rear->next=p; 
 q->rear=p; 
 return OK; 
}/*入队*/ 

int dequeue(linkqueue *q,char *e) 
{ 
 queueptr p; 
 if(q->front==q->rear) return ERROR; 
 p=q->front->next; 
 *e=p->data; 
 q->front->next=p->next; 
 if(q->rear==p) 
 { 
  q->rear=q->front; 
 } 
 free(p); 
 return OK; 
}/*出队*/ 

/***************特殊入队函数 ****************/
void spenqueue(linkqueue *q,char BIG) 
{ 
 int j; 
 char a[5]; 
 switch(BIG) /*判断大写字母对应的字符串*/
 { 
  case'A':strcpy(a,"ase");break; 
  case'B':strcpy(a,"tAdA");break; 
  case'C':strcpy(a,"tB");break; 
  case'D':strcpy(a,"del");break; 
 
  default:strcpy(a,"???"); /*不能翻译的魔王语言以"???"输出*/ 
 } 
 for(j=0;a[j]!='\0';j++) /*如果数组还有字母*/ 
  { 
   enqueue(q,a[j]);/*进队*/ 
  } 
}/*特殊入队*/ 

/*****************括号内元素入栈处理函数***********************/
void tempstack(sqstack *temps) 
{ 
 int i=0; 
 char t; 
 char c; 
 c=mag[i ]; 
 for(i=0;c!='!';i++)/*遍历数组*/ 
 { 
  c=mag[i ]; 
  if(c=='(')
  { 
  t=mag[i+1];/*取括号中的首字母*/
  push(temps,t);/*入栈*/ 
  i++;/*指向首字母*/ 
  do 
   { 
    i++; 
    c=mag[i ]; 
    push(temps,c); 
    push(temps,t);
   }while(c!=')');
  pop(temps,&t);
  pop(temps,&t); 
  } 
 } 
}/*临时栈*/ 


/************排序入队处理函数**********************/
int sort(sqstack *s,linkqueue *q) 
{ 
 qnode b; 
 int flag=0;/*大写字母监视哨置零*/ 
 int i; 
 for(i=0;mag[i]!='!';i++)/*遍历数组*/ 
 { 
  b.data=mag[i]; 
  if( ('a'<=b.data&&b.data<='z') || b.data=='?') /*进栈*/ 
   { 
    enqueue(q,b.data); 
   } 
  else  
  { 
   if('A'<=b.data&&b.data<='Z') /*特殊进栈函数,*/ 
    { 
    spenqueue(q,b.data); 
    flag=1; /*发现大写字母监视哨置1*/ 
    } 
   else 
   { 
    if(b.data=='(')
     { 
      do 
      { 
       pop(s,&e); 
       enqueue(q,e); 
      }while(!(s->top==s->base)); /*只要栈不为空,则出栈进队*/ 
      while (b.data!=')') 
       { 
        i++; 
        b.data=mag[i]; 
       }/*while*/
     } /*if*/
   }
  }
 }
 return flag; 
}/*排序*/ 

/*************主模块 ***********************/
void play()
{ 
 sqstack s1; 
 linkqueue q1; 
 int k=0; 
 int flag=1; 
 

 in_stack(&s1); /*创建栈*/ 
 initqueue(&q1); /*创建队*/ 
 tempstack(&s1); /*调用括号里元素入栈函数*/ 
 while (flag==1) /*大写字母*/
 { 
  k=0; 
  flag=sort(&s1,&q1); 
  while(q1.front!=q1.rear) /*重写mag[i ]*/ 
  { 
   dequeue(&q1,&e); 
   mag[k]=e;  /* 把元素重新写入数组mag[i] */
   k++; 
  } 
  mag[k]='!'; 
 } 
 mag[k]='\0'; 
 printf("\n\n\t***************************************");
 printf("\n\t\t你输入的魔王语言是:\n\t    %s",mag);
 printf("\n\t***************************************\n");
 getch();
}


/************主函数***********/ 
void main()
{int temp=1;
 char c;
 while(temp)
  {
     system("cls");
     play();
     printf("\t想要继续吗?（Y/N) ");
     scanf("%s",&c);
     if(c=='y')
      temp=1;
     else temp=0;
  }
  
}