C语言数据结构严蔚敏版魔王语言

//该程序思路需要两个栈和一个队列，可以解决括号嵌套问题。 #include"c1.h"//此头文件及下面四个包含所有需要的函数，并有栈和队列所有基本操作集。 typedef char QElemType; typedef char SElemType; #include"c3-1.h" #include"c3-2.h" #include"bo3-1.cpp" #include"bo3-2.cpp" using namespace std; void main() { int i,j,flag; flag=0; char str[100],ch1[100],ch2[100],e; cin>>str; //输入魔王语言。 int len=strlen(str); //得到长度。 SqStack S1,S2; InitStack(S1); InitStack(S2); for(i=len-1;i>=0;i--) //从右到左依次进栈s1。 Push(S1,str[i]); LinkQueue Q; InitQueue(Q); while(!StackEmpty(S1)) { Pop(S1,e); if(isalpha(e)) { if(e=='A') { EnQueue(Q,'s'); EnQueue(Q,'a'); EnQueue(Q,'e'); } else if(e=='B') { EnQueue(Q,'t'); EnQueue(Q,'s'); EnQueue(Q,'a'); EnQueue(Q,'e'); EnQueue(Q,'d'); EnQueue(Q,'s'); EnQueue(Q,'a'); EnQueue(Q,'e'); } else EnQueue(Q,e); } else if(e=='(') //遇左括号开始处理，此过程一直进行处理到与该左括号对应的右括号，所以这里e不可能为右括号。 { flag++; Push(S2,e); Pop(S1,e); while(flag!=0) //如有括号嵌套情况，则flag++，当flag为0时，结束处理。 { if(e=='(') { flag++; Push(S2,e); } else if(e==')') //遇到第一个右括号开始处理，将这个右括号之前到最后一个左括号的内容放入ch1。 { flag--; Pop(S2,e); j=0; while(e!='(') { ch1[j++]=e; Pop(S2,e); } for(i=0;i<=j*2-2;i++) //对ch1处理得到ch2，ch2即为括号中内容的所需处理结果。 { if(i%2==0) ch2[i]=ch1[j-1]; else ch2[i]=ch1[i/2]; Push(S2,ch2[i]); } } else { Push(S2,e); } Pop(S1,e); } while(!StackEmpty(S2)) //在s2是对遇到的第一个左括号到与之对应的右括号之间全部内容的处理，但顺序是反的，所以需要压回s1再进队列。 { Pop(S2,e); Push(S1,e); } } } while(!QueueEmpty(Q)) //从队列中输出结果 { DeQueue(Q,e); cout<<e; } cout<<endl; }