untitled1.cpp

实现魔王语言

#include<stdlib.h>
#include<stdio.h>
#include<iostream.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 struct{
	char *base;            //栈基址
	char *top;             //栈顶地址
	int stacksize;
}SqStack;
typedef struct QNode{
	char data;
	struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
	QueuePtr front;   //队头指针
	QueuePtr rear;    //队尾指针
}LinkQueue;
int InitStack(SqStack &S){
	//构造一个空栈
	S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char));
    if(!S.base)
		exit (OVERFLOW);//存储单元分配失败
	S.top=S.base;
    S.stacksize=STACK_INIT_SIZE;
	return ok;
}
int Push(SqStack &S,char e){
	//插入元素e栈顶单元
	if(S.top-S.base>=S.stacksize){
		//栈满，追加存储空间
		S.base=(char *)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;
}
int Pop(SqStack &S,char & e){
	//若栈不为空，则删除S的栈顶单元，用e返回其值
	if(S.base==S.top)
		return ERROR;
    S.top--;
    e=*(S.top);
	return ok;
}
int StackEmpty(SqStack S){
	////若栈S为空栈,则返回FALSE，否则返回TRUE
	if(S.base==S.top)
		return TRUE;
	else
		return FALSE;
}
void ClearStack(SqStack &s){

   s.top=s.base;

}
int InitQueue(LinkQueue &q){
	//构造一个空队列Q
	q.front=q.rear=(QueuePtr)malloc(sizeof (QNode));
	if(!q.front)
		exit (OVERFLOW);
	q.front->next=NULL;
	return ok;
}
int EnQueue (LinkQueue &q,char e){
	//插入元素e为Q的新的队尾元素
	struct QNode* 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;
}
int DeQueue (LinkQueue &q,char &e){
	//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK;
	//否则返回ERROR
	//QueuePtr p;
	struct QNode* 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;
}
int QueueEmpty(LinkQueue q){
	//若队列Q为空队列,则返回TRUE，否则返回FALSE
	if(q.rear==q.front)
		return TRUE;
	else
		return FALSE;
}
void InStack(char* mw,SqStack &s){//把字符数组从右至左压入栈中
	int i,n=0;
	while(mw[n]!='\0'){
		n++;
	}
	for(i=n-1;i>=0;i--){
		Push(s,mw[i]);
	}
}
int main(){
    cout<<"魔     王     语     言     解     释\n";
    cout<<"*************************************\n";
    SqStack S;
    SqStack temp;//用来处理括号外的元素
    InitStack(S);
    InitStack(temp);
    LinkQueue Q;
    InitQueue(Q);
    int i=0;
	char A[]="sae";
	char B[]="tsaedsae";
	char tag='0';//tag用来标记处理括号
	int sign=1;
	int fs=0;
	char e1,key,e2,e;
    int counter=0;//括号记数器,用来验证括号是否匹配
	char input[100]="\0";
    do
    {
        counter=0;
        cout<<"输  入  魔  王  的  语  言:\n";
        gets(input);
        int j=0;
        while(input[j]!='\0')
        {
            if(input[j]=='('){
				++counter;
			}
            if(input[j]==')') --counter;
            ++j;
        }
        if(counter!=0)
        {
            cout<<"左右括号不匹配!\n";
        }
        else InStack(input,S);//把要解释的魔王语言压入栈中
    }while(counter!=0);
    while(!StackEmpty(S)){
		Pop(S,e1);
		if(e1=='('){
			if(StackEmpty(S)){
				cout<<"这位魔王说错话了！"<<endl;
				sign=0;
				break;
			}
			while(!StackEmpty(S)){
				Pop(S,e1);
				if(e1==')'){
					fs=1;
					break;
				}
			    if(!(e1>='a'&&e1<='z')&&!(e1>='A'&&e1<='Z')){
					cout<<"这位魔王说错话了！"<<endl;
					sign=0;
					break;
				}
			}
			if(sign==0){
				break;
			}			
		}
		else if(!(e1>='a'&&e1<='z')&&!(e1>='A'&&e1<='Z')){
			cout<<"这位魔王说错话了！"<<endl;
			sign=0;
			break;
		}
	}
	if(sign==1&&fs==1){
		ClearStack(S);
		InStack(input,S);
		while(!StackEmpty(S)){//栈不空时
			Pop(S,e1);
			if(e1=='B'){
				Push(temp,e1);
			}
			else if(e1=='A'){
				Push(temp,e1);
			}
			else if(e1=='('){//用队存储括号中的元素
				Push(temp,tag);//有括号的话就用tag标记
				Pop(S,e1);
				while(e1!=')'){
					EnQueue(Q,e1);
					Pop(S,e1);
				}
				if(!QueueEmpty(Q)){
					DeQueue(Q,key);
				}
			}
			else{
				Push(temp,e1);
				fs=0;
			}
		}
		while(!StackEmpty(temp)){//边处理边进栈
			Pop(temp,e1);
			if(e1!=tag){//把括号外的元素压入中
				Push(S,e1);
			}
			else{
				while(!QueueEmpty(Q)){//处理括号中的元素进栈
					DeQueue(Q,e2);
					Push(S,key);
					Push(S,e2);
				}
				if(fs!=0){//最后还要压一个key
					Push(S,key);
				}
			}
		}
		cout<<"这位魔王的语言翻译成人类语言，其结果如下："<<endl;
		while(!StackEmpty(S)){//依次出栈输出处理后的元素
			Pop(S,e);
			if(e=='B'){
				printf("%s",B);
			}
			else if(e=='A'){
				printf("%s",A);
			}
			else{
				printf("%c",e);
			}
		}
		cout<<endl;
       cout<<"*************************************\n";
       cout<<endl;
	}
    return 0;
 }