#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;
}

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

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,ch;
  printf("魔王說話了：");
  int i=0,n;
  stack s;
  LinkQueue Q;
  Initstack(s);
  initQueue(Q);
  //for(;;i++)
	  //scanf("%c",a);
  cin>>a;
  while(a[i])i++;
  n=i;
  for(int k=i;k>=0;k--)
	  push(s,a[k]);
  while(!IsEmpty(s))
  {
	  while(!IsEmpty(s))
	  {
		  pop(s,e);
		   if(e=='B')
			   printf("tsaedsae");
		   else if(e=='A')
			   printf("sae");
		   else if(e>='a'&&e<='z')
		   {
			   ch=e;
			   break;
		   }
		   else continue;
      }

		while(!IsEmpty(s))
		{
			EnQueue(Q,ch);
			pop(s,e);
			while(e!=')')
			{
		    	if(e>='a'&&e<='z')
				{
			    	EnQueue(Q,e);
				    EnQueue(Q,ch);
				}
					pop(s,e);
			}

			 push(s,e);

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

			break;
		}

		while(!IsEmpty(s))
		{ 
			pop(s,e);
			if(e==')')break;
			else
			printf("%c",e);
		}
	  }
}