#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();
}