全顺序魔王解释.txt

魔王语言是数据结构课程设计中的一块

  #include   <stdio.h>   
  #include   <string.h>   
  #include   <stdlib.h>   
  #include   <ctype.h>   
  #define   MAX_LENGTH   255   
    
  /*==================   STACK   ===================*/   
    
  typedef   struct   {   
  char   data[MAX_LENGTH];   
  int   top;   
  }   STACK;   
    
  void   init_stack(STACK&   S)   
  {   
  S.top=0;   
  }   
    
  void   push(STACK&   S,   char   x)   
  {   
  S.data[S.top++]   =   x;   
  }   
    
  char   top(STACK&   S)     
  {   
  return   S.data[S.top-1];   
  }   
    
  int   stack_empty(STACK&   S)   
  {   
  return   (S.top==0);   
  }   
    
  char   pop(STACK&   S)   
  {   
  if   (stack_empty(S))   {   
  printf("\nERROR!   Stack   is   empty!\n");   
  exit(1);   
  }   
  return   S.data[--S.top];   
  }   
    
    
  /*==================   QUEUE   ===================*/   
    
  typedef   struct   {   
  char   data[MAX_LENGTH];   
  int   head,tail;   
  }   QUEUE;   
    
  void   init_queue(QUEUE&   Q)   
  {   
  Q.head   =   Q.tail   =   0;   
  }   
    
  void   enqueue(QUEUE&   Q,   char   x)   
  {   
  Q.data[Q.tail++]   =   x;   
  if   (Q.tail   >   MAX_LENGTH)   {   
  printf("\nERROR!   Queue   too   big!\n");   
  exit(1);   
  }   
  }   
    
  char   dequeue(QUEUE&   Q)   
  {   
  return   (Q.data[Q.head++]);   
  }   
    
  int   queue_empty(QUEUE&   Q)   
  {   
  return   (Q.head   ==   Q.tail);   
  }   
    
  /*===========================================*/   
    
  void   ReadInput(char*   string)   
  {   
  scanf("%s",   string);   
  }   
    
  void   Translate(char*   string)   
  {   
  char*   RULE_B   =   "tAdA";   
  char*   RULE_A   =   "sae";   
    
  STACK   stack;   
  QUEUE   queue;   
  char   c,   s;   
  int   i;   
    
  init_stack(stack);     
  for   (i=strlen(string)-1;   i>=0;   i--)   {   
  push(stack,   string[i]);   
  }   
  while   (!stack_empty(stack))   {   
  c   =   pop(stack);   
  if   (islower(c))   {         
  printf("%c",c);   
  }   else   if   (c=='B')   {   
  for   (i=strlen(RULE_B)-1;   i>=0;   i--)   {   
  push(stack,   RULE_B[i]);   
  }   
  }   else   if   (c=='A')   {   
  for   (i=strlen(RULE_A)-1;   i>=0;   i--)   {   
  push(stack,   RULE_A[i]);   
  }   
  }   else   if   (c=='(')   {   
  s   =   c   =   pop(stack);   
  if   (c==')')   continue;   
  init_queue(queue);   
  enqueue(queue,   s);   
  while   ((c=pop(stack))   !=   ')')   {   
  enqueue(queue,   c);   
  enqueue(queue,   s);   
  }   
  while   (!   queue_empty(queue))   {   
  push(stack,   dequeue(queue));   
  }   
  }   else   { /*   default   */   
  printf("%c",   c);   
  }   
  }   
  }   
    
  void   main()   
  {   
  char   string[MAX_LENGTH];   
  ReadInput(string);   
  Translate(string);   
  }