migong.cpp

约瑟夫环

#include<stdlib.h>
#include<stdio.h>
#define STACK_INIT_SIZE 100 
#define STACK_INCREMENT  10  


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

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

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

int InitStack(SqStack &S)

{
 S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char));
 if(!S.base)
  exit (1);
 S.top=S.base;
 S.stacksize=STACK_INIT_SIZE;
 return 1;
}
int Push(SqStack &S,char e)

{
 if(S.top-S.base>=S.stacksize)
 {
  S.base=(char *)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(char));
 if(!S.base)
  exit (1);
 S.top=S.base+S.stacksize;
 S.stacksize+=STACK_INCREMENT;
 }
 *(S.top)=e;
 S.top++;
 return 1;
}
int Pop(SqStack &S,char& e)

{
 if(S.base==S.top)
  return 0;
 S.top--;
 e=*(S.top);
 return 1;
}
int StackEmpty(SqStack S)
{
 if(S.base==S.top)
  return 0;
 else
  return 1;
} 

int InitQueue(LinkQueue &Q)

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

{
 if(Q.rear==Q.front)
  return 0;
 else
  return 1;
}
void InStack(char fiend[],SqStack &S)
{
 int m,i=0;
 for(;fiend[i]!='\0';i++);
 for(m=i-1;m>=0;m--)
  Push(S,fiend[m]);
}
void main()
{
 char e,c,d;
 SqStack S,stack;
 LinkQueue Q;
   InitQueue(Q);
   printf("请输入魔王语言：");
   
 char  mowang[]="B(ehnxgz)B";
 printf("你想要解释的魔王语言为：%s\n",mowang);
    char  B[]="tAdA";
 InitStack(S);
 InitStack(stack);
 InStack(mowang,S);
 while(StackEmpty(S))
 {
  Pop(S,e);
  if(e=='B')
  InStack(B,stack);
  else
if(e=='(')//如果为右括号，则输出括号中所有内容
   {
    while(Pop(S,e)&&e!=')')//当为左括号时停止
    {
     if(e!=')')
     EnQueue (Q,e);
    }
     DeQueue (Q,c);//读出队列中第一个元素
    while(QueueEmpty(Q))
    {
     DeQueue (Q,d);//取出元素
     Push(stack,c);
     Push(stack,d);
    }
    Push(stack,c);//再次压入第一个元素
  
   } 

 }
 printf("\n解释的结果为:  ");
    while(StackEmpty(stack))
 {
 
  Pop(stack,c);
  if(c=='A')
printf("sae");
        else
     printf("%c",c);
  }
  printf("\n");
}