魔王1.cpp

魔王语句,数据结构实验做的程序!就是清华的那本书的作业

#include<iostream.h>
#include<malloc.h>
#include<string.h>
typedef char   selemtype; 
typedef char   qelemtype; 
typedef char   elemtype; 
#define Null 0
#define MAXSIZE 100
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
char e;
char demon[MAXSIZE];

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


 stack initstack()
{/*建立一个空栈*/
	 stack st;
	st.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));
	if(!st.base)cout<<"error";
	st.top=st.base;
	st.stacksize=STACK_INIT_SIZE;
	return(st);
}
int push (stack *s,selemtype e) 
  { 
  if(s->top-s->base>=s->stacksize) 
    { 
    s->base=(elemtype *) realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(elemtype)); 
    if(!s->base) return 0; 
    s->top=s->base+s->stacksize; 
    s->stacksize+=STACKINCREMENT; 
    } 
  *(s->top++)=e; 
  return 1; 
  }/*入栈*/ 
char pop(stack *s,selemtype *e) 
  { 
  if(s->top==s->base) return 0; 
  *e=*(--(s->top)); 
  return 1; 
  }/*出栈*/ 
  typedef struct qnode 
  { 
qelemtype   data; 
  struct qnode   *next; 
  }qnode,*queueptr; 
typedef struct 
  { 
  queueptr front; 
  queueptr rear; 
  }linkqueue; 
int initqueue(linkqueue *q) 
  { 
  q->front=q->rear=(queueptr)malloc(sizeof(qnode)); 
  if(!q->front) return  0; 
  q->front->next=NULL; 
  return 1; 
  }/*创建队列*/ 
int enqueue(linkqueue *q,qelemtype e) 
  { 
  queueptr p; 
  p=(queueptr)malloc(sizeof(qnode)); 
  if(!p) return 0; 
  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(q->rear==p) 
    { 
    q->rear=q->front; 
    } 
  free(p); 
  return 1; 
  }/*出队*/ 

void tempstack(stack  *temps) 
  { 
  int  i=0; 
  char   t; 
  char   c; 
  c=demon[i ]; 
  for(i=0;c!='#';i++)/*遍历数组*/ 
    { 
    c=demon[i ]; 
    if(c=='(')/*遇到开括号*/ 
      { 
      t=demon[i+1];/*取括号中的首字母*/ 
      push(temps,t);/*入栈*/ 
      i++;/*指向首字母*/ 
      do 
        { 
        i++; 
        c=demon[i ]; 
        push(temps,c)/*第一次循环将次字母入栈*/; 
        push(temps,t);/*再将首字母进栈*/ 
        } 
      while(c!=')');/*直到括号中元素全部进栈*/ 
      pop(temps,&t);/*将多余进栈的首字母t出栈*/ 
      pop(temps,&t); /*将多余进栈的’)’出栈*/ 
      } 
    } 
  }/*临时栈*/ 

void spenqueue(linkqueue *q,char key) 
  { 
  int j=0; 
  char a[5]; 
  switch(key) /*判断大写字母对应的字符串*/ 
    { 
    case'A':strcpy(a,"ase");break; 
    case'B':strcpy(a,"tAdA");break; 
    default:strcpy(a,"???"); /*不能翻译的魔王语言以”???”输出*/ 
   
    } 
  while(a[j]!='\0') /*如果数组还有字母*/ 
    { 
    enqueue(q,a[j]);/*进队*/ 
    j++; 
    } 
  }/*特殊入队*/ 
int sort(stack *s,linkqueue *q) 
  { 
  qnode   b; 
  int  flag=0;/*大写字母监视哨置零*/ 
  int i; 
  for(i=0;demon[ i]!='\0';i++)/*遍历数组*/ 
    { 
    b.data=demon[ i]; 
    if( ('a'<=b.data&&b.data<='z')|| b.data=='?' ) /*如果是小写字母或者’?’则直接进栈*/ 
      { 
      enqueue(q,b.data); 
      } 
    else 
      { 
      if('A'<=b.data&&b.data<='Z') /*如果是大写字母,则调用特殊进栈函数,*/ 
        { 
        spenqueue(q,b.data); 
        flag=1; /*发现大写字母监视哨置1*/ 
        } 
      else 
        { 
        if(b.data=='(')/*如果是括号*/ 
          { 
          do 
            { 
            pop(s,&e); 
            enqueue(q,e); 
            } 
          while(!(s->top==s->base)); /*只要栈不为空,则出栈进队*/ 
          while (b.data!=')') /*只要还指向括号内元素,就继续往后移,保证原括号内的元素不再进栈*/ 
            { 
            i++; 
            b.data=demon[ i]; 
            } 
          } 

        } 
      } 
    } 
  return  flag; 
  }/*排序*/ 
void main()
{
	stack s1;
	linkqueue q1;
	int k=0;
	int flag=1;
	cout<<"\n\n\n***************************************\n"; 
	cout<<"请输入魔王语句:"<<endl;
	cout<<"----少于100个字符！"<<endl;
	cout<<"----输入#表示输入完毕！"<<endl;

	cin>>demon;

	cout<<"\n\n\n***************************************\n";
	s1=initstack();
	initqueue(&q1);
	tempstack(&s1);
    while (flag==1)
		while (flag==1) /*如果有大写字母*/ 
        { 
        k=0; 
        flag=sort(&s1,&q1); 
        while(q1.front!=q1.rear) /*重写demon[i ]*/ 
            { 
            dequeue(&q1,&e); 
            demon[k]=e; 
            k++; 
            } 
        demon[k]='#'; 
        } 
    demon[k]='\0'; 

	cout<<"翻译为人类语言为:"	<<endl;
	cout<<demon<<endl;
	
    cout<<"\n***************************************";
}