魔王语言.cpp

1．主要是对栈和队列的运用。 2．首先实现栈和队列的基本操作。 3．将魔王语言自右至左进栈

#include <malloc.h>
#include <iostream.h>
#include <string.h>

const int OK =1;
const int ERROR =0;
const int OVERFLOW =-1;
const int INIT_SIZE = 100;
const int INCREMENT = 10;
typedef char ElemType;

typedef struct {
	ElemType *base;
 	ElemType *top;
	int stacksize;
}SqStack;

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

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

int InitStack(SqStack &S)
{
	S.base = (ElemType * ) malloc(INIT_SIZE * sizeof(ElemType));
	if (!S.base ) return OVERFLOW;
	S.top =S.base;
	S.stacksize = INIT_SIZE;
	return OK;
}


int Push(SqStack &S,ElemType e)
{
	if (S.top - S.base >= S.stacksize)
	{
		S.base = (ElemType * ) realloc (S.base,(S.stacksize + INCREMENT) * sizeof (ElemType));
		if(!S.base) return OVERFLOW;
		S.top = S.base +S.stacksize;
		S.stacksize += INCREMENT;
	}
	*S.top++ = e;
	return OK;
}

int Pop(SqStack &S,ElemType &e)
{
	if (S.top == S.base) return ERROR;
	e = * --S.top;
	return OK;
}

int StackEmpty(SqStack &S)
{
        if (S.base == S.top) return 1;
        else return 0;
}
int DestroyStack(SqStack &S)
{
	S.base = S.top;
	free(S.base);
	return OK;
}

int InitQueue(LinkQueue &Q)
{
	Q.front = Q.rear =(QueuePtr)malloc(sizeof(QNode));
	if (!Q.front) return OVERFLOW;
	Q.front->next =NULL;
	return OK;
}

int EnQueue (LinkQueue &Q,ElemType e)
{
	QueuePtr p;
    p = (QueuePtr)malloc(sizeof(QNode));
    if (!p) return OVERFLOW;
    p ->data = e;
    p ->next = NULL;
    Q.rear ->next = p;
    Q.rear = p; 
	return OK;
}

int DeQueue(LinkQueue &Q,ElemType &e)
{
	QueuePtr p;
	if (Q.rear == Q.front) 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;
}

int DestroyQueue(LinkQueue &Q)
{
        while(Q.front)
        {
               Q.rear = Q.front->next;
               free(Q.front);
               Q.front = Q.rear;
        }
        return OK;
}

int MagicLanguage (SqStack &S,SqStack &S1)
{   
	char n,ch,n1,n2;
    LinkQueue Q;
	InitQueue(Q);
	while(!StackEmpty(S))
	{
		Pop(S,n);//将括号内的字母出栈,并顺序入队
		if ( n ==')')
		{
			Pop(S,n1);
			while(n1 !='(')
			{	
				EnQueue(Q,n1);
				Pop(S,n1);
			}	
			ch =Q.rear->data;//提取队尾
			DeQueue(Q,n2);//出队			
			while(n2 !=ch)//入新的栈,按照规则(2)的要求除第一个字母ch,每俩个第一个字母之间安顺序插入剩余字母ch
			{			
				Push(S1,ch);//循环时在字母之前插入ch				
				Push(S1,n2);			
				DeQueue(Q,n2);			
			}          

			Push(S1,ch);//在最后插入ch,满足要求
		}
		else Push(S1,n);
	}
	DestroyStack(S);
	DestroyQueue(Q);
	return OK;
}

void PrintLanguage(SqStack &S)
{
	char e;
	SqStack S2;
	LinkQueue Q1;
	InitStack(S2);
    InitQueue(Q1);
	while(!StackEmpty(S))
	{
		Pop(S,e);
		if(e=='A')
		{
			Push(S2,'e');Push(S2,'a');Push(S2,'s');
		}
		else if(e=='B')
		{
			Push(S2,'e');Push(S2,'a');Push(S2,'s');
			Push(S2,'d');
			Push(S2,'e');Push(S2,'a');Push(S2,'s');
			Push(S2,'t');
		}
		else Push(S2,e);
	}
	cout<<"解释成：";
	while(!StackEmpty(S2))
	{
		Pop(S2,e);
		EnQueue(Q1,e);//将字母入队，保证汉字输出正确
		cout<<e;
	}
	cout << endl;


	cout<<"魔王说的话是："<<endl;
	while(Q1.front!=Q1.rear)
	{
		DeQueue(Q1,e);
		switch(e)
		{
            case 't':cout<<"天";break;
			case 'd':cout<<"地";break;
			case 's':cout<<"上";break;
			case 'a':cout<<"一只";break;
			case 'e':cout<<"鹅";break;
			case 'z':cout<<"追";break;
			case 'g':cout<<"赶";break;
			case 'x':cout<<"下";break;
			case 'n':cout<<"蛋";break;
			case 'h':cout<<"恨";break;
			default:cout<<"ERROR";
		}
	}
	cout << endl;
	DestroyStack(S2);
	DestroyQueue(Q1);
}
	



int main()
{
	char str[INIT_SIZE];
	SqStack S,S1;
	InitStack(S);
	InitStack(S1);
	cout << "输入魔王语言：";
	cin >>  str;
	int len = strlen(str);
	for( int i=0;i<len;i++) Push (S,str[i]);
	MagicLanguage(S,S1);
	PrintLanguage(S1);
	DestroyStack (S1);
	return 0; 
}