[問題描述]
有一個魔王總是使用自己的一種非常精練而又抽象的語言講話，沒有人能聽得懂，但他的語言是可以逐步解釋成人能聽懂的語言，因為他的語言是由以下兩種形式的規則由人的語言逐步抽象上去的：
（1） α －> β1β2…βm
（2）（θδ1δ2…δn)－>θδnθδn－1… θδ1θ
在這兩種形式中，從左到右均表示解釋。試寫一個魔王語言的解釋系統，把他的話解釋成人能聽得懂的話。
[基本要求]
用下述兩條具體規則和上述規則形式（2）實現。設大寫字母表示魔王語言的詞匯；小寫字母表示人的語言詞匯；希臘字母表示可以用大寫字母或小寫字母代換的變量。魔王語言可含人的詞匯。
（1）B －> tAdA
（2）A －> sae
[測試數據]
B(ehnxgz)B解釋成tsaedsaeezegexenehetsaedsae

解題思路：

將魔王語言作為一個字符串讀入進來，首先檢查括號是否匹配，如果不匹配就無法解釋。如果匹配，然后將字符串從尾到頭依次壓入棧S中，將棧S中的內容依次彈出壓入棧S2中，直至遇到右括號，將其壓入棧S1中，并將棧S2彈出依次壓入棧S1中，直至遇到左括號壓入棧S1中，這樣棧S1中存放的內容就是匹配的第一個內重括號，將棧S1棧頂元素左括號彈出，將左括號下面的那個元素保存在e1變量中，然后將其他元素彈出依次壓入棧S3中，在將e1與棧S3中依次彈出的元素壓入棧S2中，重復這個過程，直至將魔王語言中所有的括號都處理完為止，所以這個思路可以處理多重括號嵌套的問題。。

完整的實現代碼如下：

    #include "iostream"
#include "string"
using namespace std;

class SqStack    //使用鏈表實現棧類
{
private:
	struct Node
	{
		int content;
		char word;
		Node *next;
	}   ;
	Node *top,*base;
public:
	SqStack();
	virtual ~SqStack();
	bool push(char e);
	bool pop(char &e);
	bool StackEmpty();
};

//棧的基本操作
SqStack::SqStack()
{
	top=base=new Node;
}

SqStack::~SqStack()
{

}

bool SqStack::push(char e)    //壓棧操作
{
	Node *p=new Node;
	if(p==NULL)
	{
		cout<<"Stack is overflow"<<endl;
		return false;
	}
	else
	{
		p->word=e;
		p->next=top;
		top=p;
		return true;
	}
}

bool SqStack::pop(char &e)    //出棧操作
{   
	if(top==NULL)
	{
		cout<<"Stack is empty"<<endl;
		return false;
	}
	else
	{
		if(top==base)
			return false;
		Node *p=top;
		top=top->next;
		e=p->word;
		delete p;
		return true;
	}
}

bool SqStack::StackEmpty()  //判斷是否為空棧
{
	return top==base;
}

class SqQueue    //使用鏈表實現隊列類
{
private:
	struct Node
	{
		int content;
		char word;
		Node *next;
	}   ;
	Node *head,*last;
public:
	SqQueue();
	virtual ~SqQueue();
	bool EnQueue(char e);
	bool DeQueue(char &e);
	bool QueueEmpty();
	void OutQueue();
	void EnQueue_A();
	void EnQueue_B();
};

//隊列的基本操作
SqQueue::SqQueue()
{
	head=last=new Node;
}

SqQueue::~SqQueue()
{

}

bool SqQueue::EnQueue(char e)    //入隊列
{
	Node *p=new Node;
	if(p==NULL)
	{
		cout<<"Queue is overflow"<<endl;
		return false; 
	}
	else
	{
		p->word=e;
		last->next=p;
		last=p;
		p->next=NULL;
		return true;
	}
}
bool SqQueue::DeQueue(char &e)    //出隊列
{
	if(head==NULL)
	{
		cout<<"Queue is empty"<<endl;
		return false;
	}
	else
	{
		Node *p=head;
		head=head->next;
		e=p->word;
		delete p;
		return true;
	}
}

void SqQueue::OutQueue()    //輸出隊列中的數據
{
	for(Node *p=head->next;p!=NULL;p=p->next)
		cout<<p->word;
	cout<<endl;
}

bool SqQueue::QueueEmpty()
{
	return head==last;
}

void SqQueue::EnQueue_A()
{
	EnQueue('s');
	EnQueue('a');
	EnQueue('e');
}

void SqQueue::EnQueue_B()
{
	EnQueue('t');
	EnQueue_A();
	EnQueue('d');
	EnQueue_A();
}

bool read_language(SqStack &S)        //將魔王語言倒置壓入棧中
{
	int i,n,left=0,right=0;
	string m; 
	cout<<"請輸入魔王語言:"<<endl;
	cin>>m;
	n=m.length();      //求字符串長度
	for(i=0;i<n;i++)
	{
		if(m[i]=='(')
			left++;
		else if(m[i]==')')
			right++;
	}
	if(left!=right)
		return false;
	for(i=n-1;i>=0;i--)
	{
		S.push(m[i]);
	}
	return true;
}

void push_and_pop(SqStack &S1,SqStack &S2)      //處理規則2
{
	char e,e1;
	SqStack S3;    //棧S3作為進行轉換的中間變量
	SqStack();
	while(!S1.StackEmpty())
	{
		S1.pop(e);
		if(e=='(')
		{
			S1.pop(e);
			e1=e;       //e1中保存的就是魔王語言中（右邊的第一個字母，就是第二種規則中的θ
			if(e!=')')
				S1.pop(e);
			while(e!=')')
			{
				S3.push(e);      
				S1.pop(e);
			} 
			while(!S3.StackEmpty())
			{
				S2.push(e1);    //根據第二種解釋規則，將θ進行多次壓棧操作
				S3.pop(e);
				S2.push(e);
			}
			S2.push(e1);
		}
	}
}


int main(void)
{
	char e;
	bool flag;
	SqStack S,S1,S2;
	SqQueue Q;
	SqStack();
	SqQueue();
	flag=read_language(S);     //讀入魔王語言
	if(!flag)
	{
		cout<<"括號不匹配，無法解釋！"<<endl;
		system("pause");
		return 0;
	}
	while(!S.StackEmpty())
	{
		S.pop(e);
		if(e==')')
		{
			S1.push(e);
			S2.pop(e);
			while(e!='(')
			{
				S1.push(e);
				S2.pop(e);
			}
			if(e=='(')
				S1.push(e);
			push_and_pop(S1,S2);
		}
		else
			S2.push(e);
	}
   //魔王語言的前面部分在棧S2的底部，后面部分在棧S2的頂部，需要轉換一下
	while(!S2.StackEmpty())
	{
		S2.pop(e);
		S.push(e);    //魔王語言的后面部分在棧S的底部，前面部分在棧S的頂部
	}

	//上面的操作進行的是第二種解釋規則
	//下面的操作進行的是第一種解釋規則
	while(!S.StackEmpty())
	{
		S.pop(e);
		if(e=='A')
			Q.EnQueue_A();
		if(e=='B')
			Q.EnQueue_B();
		else
			Q.EnQueue(e);
	}
	cout<<"魔王語言可以解釋為:"<<endl;
	Q.OutQueue();
	system("pause");
	return 0;
}
  

運行結果如下：

一重括號：

多重括號：

括號不匹配：

數據結構課程設計---魔王語言解釋