[问题描述]
有一个魔王总是使用自己的一种非常精练而又抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：
（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;
}
运行结果如下：
一重括号：
多重括号：
括号不匹配：
