#include"stdio.h"
#include"stdlib.h"
#include <iostream.h> 

typedef struct
{
	char *base;
	char *top;
	int stacksize;
}stack;

typedef struct QNode
{
	char data;
	struct QNode *next;
}QNode,*LinkQueueNode;

typedef struct
{
	LinkQueueNode front;
	LinkQueueNode rear;
}LinkQueue;


int Initstack(stack &s)
{
  s.base=(char*)malloc(100*sizeof(char));
  if(!s.base)exit(0);
  s.top=s.base;
  s.stacksize=100;
  return 1;
}

int initQueue(LinkQueue &Q)
{
	Q.front=Q.rear=(LinkQueueNode)malloc(sizeof(LinkQueueNode));
	if(!Q.front)exit(-1);
	Q.front->next=NULL;
	return 1;
}

int IsEmpty(stack s)
{
    if(s.top==s.base)return 1;
	return 0;
}

int Isempty(LinkQueue Q)
{
	if(Q.front==Q.rear)return 1;
	return 0;
}

void push(stack &s,char e)
{
	if(s.top-s.base>=s.stacksize)
	{
		s.base=(char*)realloc(s.base,(s.stacksize+10)*sizeof(char));
		if(!s.base)exit(0);
		s.top=s.base+s.stacksize;
		s.stacksize+=10;
	}
	*s.top++=e;
}

int EnQueue(LinkQueue &Q,char e)
{
	LinkQueueNode p;
	p=(LinkQueueNode)malloc(sizeof(QNode));
	if(!p)exit(-1);
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return 1;
}

int pop(stack &s,char &e)
{
	if(s.top==s.base)exit(0);
	e=*--s.top;
	return 1;
}

char DeQueue(LinkQueue &Q,char &e)
{
    LinkQueueNode p;
	if(Q.front==Q.rear)return 0;
	p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p)Q.rear=Q.front;
	free(p);
	return e;
}

char gettop(stack &s)
{
	char e;
	if(s.top==s.base)exit(0);
	e=*(s.top--);
	return e;
}


void main()
{
  char a[100];
  char e,c;
  printf("魔王說話了：");
  int i=0,n;
  stack s,S;
  LinkQueue Q;
  Initstack(s);
  Initstack(S);
  initQueue(Q);
  //for(;;i++)
	  //scanf("%c",a);
  cin>>a;
  while(a[i])i++;
  n=i;
  for(int k=0;k<=i;k++)
	  push(s,a[k]);
	 
      printf("魔王要說的話是：");
      while(!IsEmpty(s))
	  {
		   pop(s,e);
		   if(e=='B')
			   printf("tsaedsae");
		   else if(e=='A')
			   printf("sae");
		   else if(e==')')
		   {
	           while(pop(s,e)&&e!='(')
			   {
                   push(S,e);
			   }

			   while(!IsEmpty(S))
			   {
				   pop(S,e);
                   EnQueue(Q,e);
			   }

			   DeQueue(Q,c);

               while(!Isempty(Q))
			  {
                   DeQueue(Q,e);
				   push(S,c);
				   push(S,e);
			  }

			  push(S,c);

			  while(!IsEmpty(S))
			  { 
			     pop(S,e);
			     printf("%c",e);
			  }
			 
		  }
	  }
	  printf("\n");

}