魔王语言.txt

数据结构课程设计--魔王语言的解析 ### ### ### ### ### ### ### ### ### #### 问题描述: 魔王总是使用自己的一种非常精练而抽象的语言讲话,没人能听懂,但他

数据结构课程设计--魔王语言的解析
##########################################################
问题描述:
魔王总是使用自己的一种非常精练而抽象的语言讲话,没人能听懂,但他
的语言是可逐步解释成人能听懂的语言,因为他的语言是由以下两种形式
的规则由人的语言逐步抽象上去的:
-----------------------------------------------------------
1)a--->  (B1)(B2)....(Bm)
2)[(op1)(p2)...(pn)]---->[o(pn)][o(p(n-1))].....[o(p1)o]
-----------------------------------------------------------
在这两种形式中,从左到右均表示解释.试写一个魔王语言的解释系统,把
他的话解释成人能听得懂的话.
###########################################################
基本要求:
用下述两条具体规则和上述规则形式(2)实现.
设大写字母表示魔王语言的词汇;
  小写字母表示人的语言的词汇;
希腊字母表示可以用大写字母或小写字母代换的变量.
魔王语言可含人的词汇.
1) B --> tAdA
2) A --> sae
############################################################
测试数据:
B(ehnxgz)B 解释成 tsaedsaeezegexenehetsaedsae
若将小写字母与汉字建立下表所示的对应关系,则魔王说的话是:
"天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅".
---------------------------------------------------
| t  | d  | s  | a  | e  | z  | g  | x  | n  | h  |
---------------------------------------------------
| 天 | 地 | 上 | 一只| 鹅 | 追 | 赶 | 下 | 蛋 | 恨 |
---------------------------------------------------
#############################################################
实现提示:
将魔王的语言自右至左进栈,总是处理栈顶字符.若是开括号,则逐一出栈,将
字母顺序入队列,直至闭括号出栈,并按规则要求逐一出队列再处理后入栈.
其它情形较简单.
应首先实现栈和队列的基本操作.
#############################################################
选作内容:
1)由于问题的特殊性,可实现栈和队列的顺序存储空间共享
2)代换变量的数目不限,则在程序开始运行时首先读入一组第一种形式的规则,
而不是把规则固定在程序中(第二种形式的规则只能固定在程序中). 
 


修改了在网上下载的东西：

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

#define TRUE 1 
#define FALSE 0 
#define OK 1 
#define ERROR 0 
#define OVERFLOW -2 
#define MAXSIZE 50 
#define stack_init_size 100 
#define stackincrement 10 

typedef char SElemType; 
typedef char QElemType; 
typedef char ElemType; 
typedef int status; 

char e; 
char string[MAXSIZE]; 
char string1[MAXSIZE];
char string2[MAXSIZE];

typedef struct
{
 SElemType *base; 
 SElemType *top; 
 int stacksize; 
}sqstack;

status initstack(sqstack *s) 
{ 
 s->base=(SElemType *)malloc(stack_init_size*sizeof(SElemType)); 
 if(!s->base) exit (OVERFLOW); 
 s->top=s->base; 
 s->stacksize=stack_init_size; 
 return OK; 
}

status push(sqstack *s,SElemType e) 
{ 
 if(s->top-s->base>=s->stacksize) 
{ 
 s->base=(ElemType *) realloc(s->base,(s->stacksize+stackincrement)*sizeof(ElemType)); 
 if(!s->base) exit(OVERFLOW); 
 s->top=s->base+s->stacksize; 
 s->stacksize+=stackincrement; 
} 
 *(s->top++)=e; 
 return OK; 
}

status pop(sqstack *s,SElemType *e) 
{ 
if(s->top==s->base) return ERROR; 
*e=*(--(s->top)); 
return OK; 
} 

typedef struct QNode 
{ 
 QElemType data; 
 struct QNode *next; 
}QNode,*QueuePtr; 

typedef struct 
{ 
 QueuePtr front; 
 QueuePtr rear;  
}LinkQueue; 

status initqueue(LinkQueue *q) 
{ 
 q->front=q->rear=(QueuePtr)malloc(sizeof(QNode)); 
 if(!q->front) exit(OVERFLOW); 
 q->front->next=NULL; 
 return OK; 
}

status enqueue(LinkQueue *q,QElemType 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; 
}

status dequeue(LinkQueue *q,QElemType *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 tempstack(sqstack *ts) 
{ 
 int i=0; 
 char t; 
 char c;
 c=string[i]; 
 for(i=0;c!='#';i++) 
{ 
 c=string[i]; 
 if(c=='(') 
{ 
 t=string[i+1];
 push(ts,t); 
 i++;
 do 
{ 
 i++; 
 c=string[i]; 
 push(ts,c);
 push(ts,t);
}
 while(c!=')');
 pop(ts,&t);
 pop(ts,&t);  
} 
} 
} 

void spenqueue(LinkQueue *q,char k) 
{ 
 int j=0;
 int n,m;
 char a[10]; 
 switch(k)  
{ 
 case'A': { 
      for(n=0;n<MAXSIZE;n++)
      enqueue(q,string1[n]);}
      ;break; 
 case'B':{
         for(m=0;m<MAXSIZE;m++)
         enqueue(q,string2[m]);}
      ;break;
} 
 while(a[j]!='\0') 
{ 
 enqueue(q,a[j]);
 j++; 
} 
}

status sort(sqstack *s,LinkQueue *q) 
{ 
 QNode b; 
 int flag=0;
 int i; 
 for(i=0;string[i]!='#';i++) 
{ 
 b.data=string[i]; 
 if('a'<=b.data&&b.data<='z') 
{ 
 enqueue(q,b.data); 
} 
 else if('A'<=b.data&&b.data<='B') 
{ 
 spenqueue(q,b.data); 
 flag=1; 
} 
 else if(b.data=='(')
{ 
 do 
{ 
 pop(s,&e); 
 enqueue(q,e); 
}while(!(s->top==s->base)); 
 while (b.data!=')') 
{ 
 i++; 
 b.data=string[i]; 
} 
} 
} 
 return flag; 
}

status main() 
{ 
 sqstack S; 
 LinkQueue Q; 
 int k; char a;
 int flag;
 printf("\n***************************************\n"); 
 printf("\n       欢迎使用魔王语言解释系统        \n");
 printf("\n***************************************\n");
loop:
 printf("请输入第一条规则:A=");
 scanf("%s",string1);
 printf("                 B=");
 scanf("%s",string2);
 printf("请输入魔王语言（请以#结尾）:"); 
 scanf("%s",string); 
 initstack(&S);  
 initqueue(&Q);  
 tempstack(&S);
 flag=1;
 while (flag==1) 
{ 
 k=0; 
 flag=sort(&S,&Q); 
 while(Q.front!=Q.rear)  
{ 
 dequeue(&Q,&e); 
 string[k]=e; 
 k++; 
} 
 string[k]='#'; 
} 
 string[k]='\0'; 
 printf("\n***************************************\n");
 printf("解释成人类的语言是:\t%s",string);
 printf("\n***************************************\n");
 printf("是否继续进行魔王语言操作（y为是，n为否） \n");
 printf("请选择：");
 scanf("%s",&a);
 switch(a)
{
  case'y':goto loop;break;
  case'n':break;
}  
}