魔王语言2.cpp

魔王语言翻译

#include <iostream.h>
#include <malloc.h>
#include <string.h>
const int STACK_INIT_SIZE=100;
const int MAXQSIZE=100;
typedef char SElemType,QElemType;
typedef struct
{
	SElemType *base; //顺序栈的栈底指针
	SElemType *top; //顺序栈的栈顶指针
	int StackSize; //栈元素空间的大小 //栈元素实际个数
}SqStack; //结构体类型顺序栈
//---------------------顺序栈的接口函数声明-----------------------//
//构造一个空栈
bool InitStack(SqStack &S);
//把S置为空栈
bool StackEmpty(SqStack &S);
//返回栈S的元素个数,即栈的长度
int StackLength(SqStack &S);
//若栈不空,则用e返回S的栈顶元素,并返回ok;否则返回error
bool GetTop(SqStack &S,SElemType &e);
//插入新元素e为新的栈顶元素
bool Push(SqStack &S,SElemType e);
//若栈不空,删除S的栈顶元素,并用e返回其值,并返回true,否则返回false
bool Pop(SqStack &S,SElemType& e);
//输出结果栈
void PrintStack(SqStack &S,SElemType e);
//---------------抽象数据类型队的定义------------------//
typedef struct
{
	QElemType *base; //指向队列元素存储空间的指针
	int front; //队列的队头指针
	int rear; //队列的队尾指针
}SqQueue; //结构体类型循环队列
//---------------------循环队的接口函数声明-----------------------//
//初始化队
bool InitQueue(SqQueue &Q);
//返回Q的元素个数,即队列的长度
int QueueLength(SqQueue &Q);
//插入新元素e为Q的新队尾元素
bool EnQueue(SqQueue &Q, QElemType e);
bool EmptyQueue(SqQueue &Q);
//若队列不空,则删除Q的队头元素,用e返回其值,并返回true,否则返回false;
bool DeQueue(SqQueue &Q, QElemType &e);
/*----------------------------------------------------------------------*/
/*----------------------------------------------------------------------*/
bool InitStack(SqStack &S)
{
	S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if(S.base)
	{
		S.top=S.base;
		S.StackSize=0;
		return true;
	}
	else
		return false;
}
/*----------------------------------------------------------------------*/
bool StackEmpty(SqStack &S)
{
	if(S.base==S.top)
		return true;
	else
		return false;
}
/*----------------------------------------------------------------------*/
int StackLength(SqStack &S)
{
	return S.StackSize;
}
/*----------------------------------------------------------------------*/
bool GetTop(SqStack &S,SElemType &e)
{
	if(!StackEmpty(S))
	{
		e=*(S.top-1);
		S.StackSize=S.StackSize-1;
		return true;
	}
	else
	{
		cout<<"栈空！"<<endl;
		return false;
	}
}
/*----------------------------------------------------------------------*/
bool Push(SqStack &S,SElemType e)
{
	*S.top++=e;
	S.StackSize++;
	return true;
}
/*----------------------------------------------------------------------*/
bool Pop(SqStack &S,SElemType& e)
{
	if(!StackEmpty(S))
	{
		e=*--S.top;S.StackSize--;
		return true;
	}
	else
	{
		cout<<"栈空！"<<endl;
		return false;
	}
}
/*----------------------------------------------------------------------*/
void PrintStack(SqStack &S,SElemType e)
{
	if(!StackEmpty(S))
	{
		while(!StackEmpty(S))
		{
			Pop(S,e);
			cout<<e;
		}
		cout<<endl;
	}
	else
		cout<<"*栈空！"<<endl;
}
/*----------------------------------------------------------------------*/
bool InitQueue(SqQueue &Q)
{
	Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
	if(!Q.base)
		return false;
	else
	{
		Q.front=Q.rear=0;
		return true;
	}
}
/*----------------------------------------------------------------------*/
bool EmptyQueue(SqQueue &Q)
{
	if(Q.front==Q.rear-1)return true;
	else return false;
}
/*----------------------------------------------------------------------*/
int QueueLength(SqQueue &Q)
{
	return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
/*----------------------------------------------------------------------*/
bool EnQueue(SqQueue &Q, QElemType e)
{
	if((Q.rear+1)%MAXQSIZE==Q.front)return false;
	Q.base[Q.rear]=e;
	Q.rear=(Q.rear+1)%MAXQSIZE;
	return true;
}
/*----------------------------------------------------------------------*/
bool DeQueue(SqQueue &Q, QElemType &e)
{
	if(QueueLength(Q))
	{
		e=Q.base[Q.front++];/*Q.front++;*/return true;
	}
	else
		return false;
}
/*----------------------------------------------------------------------*/
int main()
{
	SElemType LangB[5]="tAdA",LangA[4]="sae";
	SElemType Magical_Language[80]="";
	SqStack ChStack; //定义一个字符栈变量ChStack
	SqQueue ChQueue; //定义一个字符队列变量ChQueue
	SqStack TransLang;
	InitStack(ChStack);
	InitQueue(ChQueue);
	InitStack(TransLang);
	cout<<"请输入魔王语言！"<<endl;
	cin>>Magical_Language;
	//将魔王语言串按照自左向右顺序进栈
	for(int i = 0; i<strlen(Magical_Language); i++)
		Push(ChStack,Magical_Language[i]);
	SElemType e,ReserveLetter;
//栈ChStack不空, 按照预先定义好的产生式规则翻译魔王语言
	while(!StackEmpty(ChStack))
	{
		Pop(ChStack,e);
		switch( e ) //分以下几种情况对魔王语言串按照产生式进行翻译
		{
		case 'B':
			{
				for(int k=0;k<4;k++)//如果栈顶元素是非终结符B,则将产生式B..tAdA中符号‘..’
					Push(ChStack,LangB[k]);//右边的字符串按照自左至右顺序逐一进栈
				break;
			}//end case
		case 'A':
			{
				for(int t=0;t<3;t++)//如果栈顶元素是非终结符A,则将产生式A..sae中，符号..右边字符串
					Push(ChStack,LangA[t]); //按照自左至右顺序进栈
				break;
			}//end case
		case ')':
			{
				while(e!='(')//说明需要处理（……..）的内容
				{//如果栈顶元素是终结符),则连续出栈,将每个出栈的元素进队
					Pop(ChStack,e);
					if(e!='(')
					{
						EnQueue(ChQueue, e);
						ReserveLetter=e;
					}
				} //将最后出栈的元素作为ReverseFirstElem；//先压ReverseFirstElem到栈中；
				while(!EmptyQueue(ChQueue))
				{//////////////////////////////
					DeQueue(ChQueue,e);
					Push(ChStack,ReserveLetter);
					Push(ChStack,e);
				}
				Push(ChStack,ReserveLetter);
				break;//将队列中的其余元素进栈,生成新序列；
			}//end case
		default:
			{
				//如果不是上述几种情况，则将字符入队列TransLang
				Push(TransLang,e);
				break;
			}
		}//end switch
	}//end while
	cout<<"魔王语言经过翻译后是："<<endl;
	PrintStack(TransLang,e);
	return 0;
}
/*----------------------------------------------------------------------*/
/*----------------------------------------------------------------------*/