魔王语言.txt

数据结构实习作业 魔王与语言 栈的应用

#include <iostream>
using namespace std;
#include <string>
typedef struct Stack
{ char c;
  struct Stack *next;
}Stack,*LinkStack;
typedef struct
{ LinkStack base;
  LinkStack top;
}LStack;
typedef struct Queue
{ char c;
  struct Queue *next;
}Queue,*LinkQueue;
typedef struct 
{ LinkQueue front;
  LinkQueue rear;
}LQueue;
void Init_stack(LStack&S)
{ S.base=S.top=new Stack;
  S.base->next=NULL;
}
void push_stack(LStack&S,char t)
{ LinkStack p;
  p=new Stack;
  S.top->c=t;p->next=S.top;
  S.top=p;
}
void Init_queue(LQueue&Q)
{ Q.front=Q.rear=new Queue;
  Q.rear->next=NULL;
}
void EnQueue(LQueue&Q,char t)
{ LinkQueue p;
  p=new Queue;p->next=NULL;
  Q.rear->c=t;
  Q.rear->next=p;
  Q.rear=p;
}
void DeQueue(LQueue&Q,char &t)
{ LinkQueue p;
  p=Q.front;
  t=Q.front->c;
  Q.front=Q.front->next;
  delete p;
}
void print_stack(LStack&S)
{   LinkStack p=S.top;
    S.top=S.top->next;
 delete p;
 while(S.top!=S.base){
 cout<<S.base->c<<S.top->c;
 p=S.top;
 S.top=S.top->next;
 delete p;}
 cout<<S.base->c;
 delete S.base;
}
int main()
{ string sa,sb,s;LStack S;LQueue Q;char t;
  Init_stack(S);Init_queue(Q);
  cout<<"B:";cin>>sb;
  cout<<"A:";cin>>sa;
  cout<<"enter sentence:";cin>>s;
  for(int i=0;s[i]!='\0';i++)
   EnQueue(Q,s[i]);
  while(Q.front!=Q.rear)
  {   DeQueue(Q,t);
   if(t=='A')cout<<sa;
   else if(t=='('){
    DeQueue(Q,t);
    while(t!=')'){push_stack(S,t);DeQueue(Q,t);}
    if(S.base!=S.top)print_stack(S);}
   else if(t>=97&&t<=122)cout<<t;
   else for(i=0;sb[i]!='\0';i++){
          if(sb[i]=='A')cout<<sa;
    else cout<<sb[i];}
  }
  cout<<endl;
  return 0;
}