魔王语言.cpp

数据结构中的魔王语言大家都知道吧

#include<iostream.h>
#include<stdlib.h>
//#include<stdio.h>
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT  10
#define OVERFLOW          1
#define OK                1
#define ERROR			  0
#define TRUE			  1
#define FALSE			  0
typedef char      SElemType;
typedef char      QElemType;
typedef int       Status;
typedef struct{
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;

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

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

Status InitStack(SqStack &S)
{
	S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(char));
	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=(SElemType *)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(char));
			if(!S.base)
				exit (OVERFLOW);
			S.top=S.base+S.stacksize;
			S.stacksize+=STACK_INCREMENT;
		 }
	*(S.top)=e;
	S.top++;
 return OK;
}

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

Status StackEmpty(SqStack S)
{
	if(S.base==S.top)
	return 0;
	else
	return 1;
} 

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));
	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(p==Q.rear)
		Q.rear=Q.front;
	free(p);
	return OK;
}

Status QueueEmpty(LinkQueue Q)
{
	if(Q.rear==Q.front)
		return FALSE;
	else
		return TRUE;
}

void GetInStack(char fiend[],SqStack &S)
{
	int m,i=0;
	for(;fiend[i]!='\0';i++);
		for(m=i-1;m>=0;m--)
			Push(S,fiend[m]);
}

void main()
{
	char e,a,b;
	char B[]="tAdA";
	char *mowang;
	mowang=(char*)malloc(100*sizeof(char));
	SqStack s1,s2;
	LinkQueue Q;
	InitQueue(Q);
	
	cout<<"请输入你想要翻译的魔王语言：";
		cin>>mowang;

	InitStack(s1);
	InitStack(s2);
	GetInStack(mowang,s1);

	cout<<mowang<<"解释成:";

	while(StackEmpty(s1))
	{
		Pop(s1,e);
		if(e=='B')
			cout<<"tsaedsae";
			//GetInStack(B,s2);
		else if(e=='(')
		{
			while(Pop(s1,e)&&e!=')')
			{
				EnQueue(Q,e);
			}
			DeQueue(Q,a);
			while(QueueEmpty(Q))
			{
				DeQueue(Q,b);
				Push(s2,a);
				Push(s2,b);
			}
			Push(s2,a);
			while(StackEmpty(s2))
			{
				Pop(s2,a);
				if(a=='A')
					cout<<"sae";
				else
					cout<<a;
			}
		}

	}
	//cout<<mowang<<"解释成:";
	//while(StackEmpty(s2))
	//{
	//	Pop(s2,a);
	//	if(a=='A')
	//		cout<<"sae";
	//	else
	//		cout<<a;
	//}
	cout<<endl;
}