魔王语言gjnl.cpp

2． 进入程序后

#include<stdlib.h>
#include<malloc.h>
#include<stdio.h>
#include<ctype.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0

#define OVERFLOW -1

typedef char status;
typedef char ElemType;
typedef char SElemType;

#define STACK_INIT_SIZE 21//定义栈的初始长度
#define STACKINCREMENT 10  //定义栈每次追加分配的长度
//实现栈的数据类型

typedef struct{
    SElemType *base;
    SElemType *top;
    int stacksize;
    }Stack;
//-----------------------------------------------------

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

typedef struct
{
    QueuePtr front;//队头指针
    QueuePtr rear;//队尾指针
}LinkQueue;
//-------------------------------------------------


status InitQueue(LinkQueue &Q)
{
    //构造一个空队列Q
    Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
    if(!Q.front)exit(OVERFLOW);
    Q.front->next=NULL;
    return OK;
}
//-------------------------------------------------
status DestroyQueue(LinkQueue &Q)
{
    //销毁队列Q
    while(Q.front)
    {
        Q.rear=Q.front->next;
        free(Q.front);
        Q.front=Q.rear;
    }
    return OK;
}
//-------------------------------------------------
status EnQueue(LinkQueue &Q,ElemType &e)
{
    //插入元素e为Q的新的队尾元素
    QueuePtr 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;
}
//-------------------------------------------------
status DeQueue(LinkQueue &Q,ElemType &e)
{
    //若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；
    //否则返回ERROR
    QueuePtr p;
    if(Q.front==Q.rear)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;
}
//-------------------------------------------------
status QueueEmpty(LinkQueue Q)
{
    //若队列Q为空队列，则返回TRUE，否则返回FALSE
    if(Q.front==Q.rear)return TRUE;
    return FALSE;
}
//-------------------------------------------------

//栈的各项操作的实现
status InitStack(Stack &s)
{
    //初始化栈
    s.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
    if (!s.base) return OVERFLOW;
    s.top=s.base;
    s.stacksize=STACK_INIT_SIZE;
    return OK;
}
//-----------------------------------------------------
status StackEmpty(Stack &s){
    //判断栈空与否，空时返回TRUE，否则返回ERROR.
    //当栈不存在时返回出错信息
    if (!s.base) return ERROR;
    if (s.top==s.base) return TRUE;
    return FALSE;
    }
//-----------------------------------------------------
status GetTop(Stack s,SElemType &e)
{
    //当栈存在且不空时返回栈顶元素
    //当栈不存在或栈空时返回出错信息
    if (s.base==s.top) return ERROR;
        e=*(s.top-1);
    return OK;
}
//-----------------------------------------------------
status Push(Stack &s,SElemType e)
{
    //插入元素e为新的栈顶元素
    if(s.top-s.base>=s.stacksize)//栈满，追加存储空间
    {
        s.base=(ElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(ElemType));
        if(!s.base)exit(OVERFLOW);//存储分配失败
        s.top=s.base+s.stacksize;
        s.stacksize+=STACKINCREMENT;
    }
    *s.top++=e;
    return OK;
}
//-----------------------------------------------------
status Pop(Stack &s,SElemType &e){
    //若栈不空，则删除s的栈顶元素，用e返回其值，并返回OK；
    //否则返回ERROR.
    if(s.top==s.base)return ERROR;
    e=* (--s.top);
    return OK;
    }
//-----------------------------------------------------
status DestroyStack(Stack &s)
{
    //销毁栈s，s不再存在
    free(s.base);
    s.top=s.base;
    s.stacksize=0;
    return OK;

}

int Translate(char expression[26][6],ElemType Fiend_lang[21])
{
    int i;
    ElemType e;
    ElemType Q_head;
    Stack S1;
//----------------------------------------------------
    InitStack(S1);
    //魔王语言进栈(从右到左)
    for(i=0;Fiend_lang[i]!='\0';i++);
    while(i>0)         //i不可等于0
    {
        i--;
        Push(S1,Fiend_lang[i]);
    }
    /*出栈并处理栈顶元素*/
    while(Pop(S1,e))//魔王语言只能是大写，魔王词汇是小写
    {   
        if(e>='A'&&e<='Z')
    	{
            //expression[e-'A']中的数组从右到左入栈
            for(i=0;(*(expression[e-'A']+i))!='\0';i++);//探测数组expression[e-'A'][i]既第二维中有多少元素
														//expression[e-'A']是计算Fiend_lang[i]所对应的词汇首地址
            for(i--;i>=0;Push(S1,*(expression[e-'A']+i)),i--);//将第二维元素从右到左进栈，保证输入时的序列是原来序列的从左到右			
        }      //?? 
        else if(e=='(')
            {   
                LinkQueue Q;
                InitQueue(Q);
                Pop(S1,e);                  
                while(e!=')')
        		{
                    EnQueue(Q,e); 
                	Pop(S1,e);
        		}
                DeQueue(Q,e);
                Q_head=e;
                Push(S1,e);
                while(!QueueEmpty(Q))
        		{
                    DeQueue(Q,e);
                    Push(S1,e);
                    Push(S1,Q_head);//魔王语言规则，每次都需将Q_head再进栈
        		}
             //   Push(S1,Q_head);
                DestroyQueue(Q);
            }
        else//若是小写字母则输出，所以程序只需要一个栈即可
            printf("%c",e);
    }
    printf("\n");
    /*处理完毕*/
    return 0;	
}
//---------------------------------------------------------------------
int New_Exp( char expression[26][6])//词汇储存在数组中，每个词汇不超过5个字母
{
    int i,j;  
    printf("Please input the expressions.\n");
    for(i=0;i<26;i++)
    {
		printf("%d",i+1); 
		printf(":");
        for(j=0;j<6;j++)
		{
			expression[i][j]=getchar();
			if(isspace(expression[i][j]))
				{expression[i][j]='\0';j=0;break;}
		}
    }
    return OK;
}
//---------------------------------------------------------------------

void main()
{
    char e;

	int i=0;
    ElemType expression[26][6]={"sae","tAdA","sce","sde"};  //默认的魔王词汇（只有A,B,C,D）
                                                            //每个词汇最多只能有5个字符	
    ElemType Fiend_lang[21]; //魔王的一句话最多只能有20个字符（可改）
    //询问是否要创建新的魔王词汇
    printf("\n\n\n你想创建一个新的魔王表达法则吗?(y/N):");
    e=getchar();getchar();
    if(e=='y')
	{New_Exp(expression);}
    printf("\t********************************************\n");
    printf("\n\n\n\n");
    printf("\t  请输入魔王语言：\n");
    printf("\t  :");
	for(i=0;i<21;i++)
	{
		Fiend_lang[i]=getchar();
		if(isspace(Fiend_lang[i]))//=='\r'||Fiend_lang[i]=='\n'
		{Fiend_lang[i]='\0';break;}
	}
    printf("\t  解释后为 :");
    Translate(expression,Fiend_lang);
    printf("\n\n\n\n\n");
    printf("\t*****************************************************\n");
    printf("\t\t 计算机科学与技术9班 郭剑楠 3106006799\n");
    printf("\t*****************************************************\n");
    getchar();
    getchar();
}