mowang.cpp

利用栈来完成数据结构实习的魔王语言.完成基本内容.

#include<malloc.h>
#include <stdlib.h>
#include<string.h>
#include <iostream.h>
      
#define TRUE       1
#define FALSE       0
#define  OK         1
#define ERROR       0
#define NULL        0
#define OVERFLOW     -2
#define MAXSIZE       100
#define stack_init_size  100
#define stackincrement   10

typedef char   selemtype;
typedef char   qelemtype;
typedef char   elemtype;
typedef int   status;

char   e;
char   mowang[MAXSIZE];



typedef struct
  {
  selemtype   *base;
  selemtype   *top;
  int     stacksize;
  }sqstack;

status initstack (sqstack *s)
  {
  s->base=(selemtype *)malloc(stack_init_size*sizeof(selemtype));
  if(!s->base) exit (OVERFLOW);
  s->top=s->base;
  s->stacksize=stack_init_size;
  return OK;
  }

status push (sqstack *s,selemtype e)
  {
  if(s->top-s->base>=s->stacksize)
    {
    s->base=(elemtype *) realloc(s->base,(s->stacksize+stackincrement)*sizeof(elemtype));
    if(!s->base) exit(OVERFLOW);
    s->top=s->base+s->stacksize;
    s->stacksize+=stackincrement;
    }
  *(s->top++)=e;
  return OK;
  }

status pop(sqstack *s,selemtype *e)
  {
  if(s->top==s->base) return ERROR;
  *e=*(--(s->top));
  return OK;
  }


typedef struct qnode
  {
  qelemtype   data;
  struct qnode   *next;
  }qnode,*queueptr;
typedef struct
  {
  queueptr front;
  queueptr rear;
  }linkqueue;

status initqueue(linkqueue *q)
  {
  q->front=q->rear=(queueptr)malloc(sizeof(qnode));
  if(!q->front) exit(OVERFLOW);
  q->front->next=NULL;
  return OK;
  }

status enqueue(linkqueue *q,qelemtype e)
  {
  queueptr p;
  p=(queueptr)malloc(sizeof(qnode));
  if(!p) exit(OVERFLOW);
  p->data=e;
  p->next=NULL;
  q->rear->next=p;
  q->rear=p;
  return OK;
  }

status dequeue(linkqueue *q,qelemtype *e)
  {
  queueptr p;
  if(q->front==q->rear) return ERROR;
  p=q->front->next;
  *e=p->data;
  q->front->next=p->next;
  if(q->rear==p)
    {
    q->rear=q->front;
    }
  free(p);
  return OK;
  }


void lishistack(sqstack  *temps)//临时栈
  {
  int  i=0;
  char   t;
  char   c;
  c=mowang[i ];
  for(i=0;c!='#';i++)/*遍历数组*/
    {
    c=mowang[i ];
    if(c=='(')/*遇到开括号*/
      {
      t=mowang[i+1];/*取括号中的首字母*/
      push(temps,t);/*入栈*/
      i++;/*指向首字母*/
      do
        {
        i++;
        c=mowang[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,"sae");break;
    case'B':strcpy(a,"tAdA");break;
   
    default:strcpy(a,"???"); /*不能翻译的魔王语言以”???”输出*/
    }
  while(a[j]!='\0') /*如果数组还有字母*/
    {
    enqueue(q,a[j]);/*进队*/
    j++;
    }
  }

void chinese(char key2)
{
	
	switch(key2)
	{
	case't':cout<<"天";break;
	case'd':cout<<"地";break;
	case's':cout<<"上";break;
	case'a':cout<<"一只";break;
	case'e':cout<<"鹅";break;
	case'z':cout<<"追";break;
	case'g':cout<<"赶";break;
	case'x':cout<<"下";break;
	case'n':cout<<"蛋";break;
	case'h':cout<<"恨";break;
	default:cout<<'?';
	}
}

status sort(sqstack *s,linkqueue *q)
  {
  qnode   b;
  int  t1=0;/*大写字母监视哨置零*/
  int i;
  for(i=0;mowang[ i]!='#';i++)/*遍历数组*/
    {
    b.data=mowang[ 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);
        t1=1; /*发现大写字母监视哨置1*/
        }
      else
        {
        if(b.data=='(')/*如果是括号*/
          {
          do
            {
            pop(s,&e);
            enqueue(q,e);
            }
          while(!(s->top==s->base)); /*只要栈不为空,则出栈进队*/
          while (b.data!=')') /*只要还指向括号内元素,就继续往后移,保证原括号内的元素不再进栈*/
            {
            i++;
            b.data=mowang[ i];
            }
          }

        }
      }
    }
  return  t1;
  }

void PrintInterface()
{//打印用户办面
	cout<<"                  *************************************"<<endl;
	cout<<"                  *  魔王语言解释                     *"<<endl;
	cout<<"                  *                                   *"<<endl;
	cout<<"                  *         设计者；                  *"<<endl;
	cout<<"                  *         班级：                    *"<<endl;
	cout<<"                  *         学号：                    *"<<endl;
   	cout<<"                  *                                   *"<<endl;
	cout<<"                  *                                   *"<<endl;
	cout<<"                  *************************************"<<endl;
}

void main()
    {
    sqstack s;
    linkqueue q;
    int k=0;
    int t1=1;
	PrintInterface();
	cout<<"                                               "<<endl;
    cout<<"请输入魔王语言,并以#号结束：(例如：B(ehnxgz)B#)"<<endl;
    cin>>mowang;
    
    initstack(&s); /*创建栈*/
    initqueue(&q); /*创建队*/
    lishistack(&s); /*调用函数*/
    while (t1==1) /*如果有大写字母*/
        {
        k=0;
        t1=sort(&s,&q);
        while(q.front!=q.rear) /*重写mowang[i ]*/
            {
            dequeue(&q,&e);
            mowang[k]=e;
            k++;
            }
        mowang[k]='#';
        }
    mowang[k]='\0';
	cout<<"              "<<endl;
	cout<<"人类的语言是:"<<endl;
    cout<<mowang<<endl;
	cout<<"                  "<<endl;
	cout<<"人类的语言解释是："<<endl;
	for(int i=0;mowang[i]!='\0';i++)
	{ chinese(mowang[i]);
	}
	cout<<"  "<<endl;
	cout<<"              "<<endl;

}