22魔王语言解释.doc

魔王语言解释 一．实验目的 本次实习的目的在于使读者深入了解栈和队列的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对这两种结构的构造方法的理解。 二．实验内容 【问题描述】有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去：（1）α-β1β2β…βm (2)(θδ1δ2δ…δn)-θδnθδn-1…θδ1θ在这两种形式中，从左到右均表示解释，试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话。 【基本要求】用下述两条具体规则和上述规则形式（2）实现，设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量，魔王语言可含人的词汇。（1）B-tAdA (2)A-sae 三．实验步骤（可选） #includestdio.h #includestdlib.h #includeiostream using namespace std; #define stack_init_size 100 #define stack_increment 10 struct Stack{//***定义栈*** char* base; char* top; int stacksize;}; void InitStack(struct Stack s){//***构造栈*** s.base=(char*)malloc(stack_init_size*sizeof(char)); s.top=s.base; s.stacksize=stack_init_size;} void Push(struct Stack s,char e){//***往栈中压入元素*** if(s.top-s.base=stack_init_size){ s.base=(char*)realloc(s.base,(s.stacksize+stack_increment)*sizeof(char)); s.top=s.base+s.stacksize; s.stacksize+=stack_increment; } *(s.top)=e; s.top++;} void Pop(struct Stack s,char e){//***取出栈中的元素*** e=*--s.top;} int StackEmpty(struct Stack s){//***判断栈是否为空*** if(s.top==s.base) return 1; else return 0;} void ClearStack(struct Stack s){//***清空栈*** s.top=s.base;} struct Queue{//***定义队列*** char data; struct Queue* next;}; struct LinkQueue{ struct Queue* front; struct Queue* rear;}; void InitQueue(struct LinkQueue q){//***构造队列*** q.front=q.rear=(struct Queue*)malloc(sizeof(struct Queue)); q.front-next=NULL;} void EnQueue(struct LinkQueue q,char e){//***元素入队*** struct Queue* p; p=(struct Queue*)malloc(sizeof(struct Queue)); p-data=e; p-next=NULL; q.rear-next=p; q.rear=p;} void DeQueue(struct LinkQueue q,char e){//***元素出队*** struct Queue* p; p=q.front-next; e=p-data; q.front-next=p-next; if(q.rear==p) q.rear=q.front; free(p);} int QueueEmpty(struct LinkQueue q){ //***判断队列是否为空，如果对为空，返回，否则返回*** if(q.front==q.rear) return 1; else return 0;} void I