mowang.h

数据结构中的魔王语言解释算法

#include<iostream.h>
#include <stdio.h>
#include<stdlib.h>
	
#define OK 1
#define OVERFLOW -2
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define INFERSIBLE -1
	
typedef int Status;

//以下是栈的ADT的实现
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

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

Status InitStack(SqStack &s)      //构造一个空栈
{
    s.base=(char*)malloc(STRACK_LIST_SIZE*sizeof(char));
    if(!s.base) exit(OVERLFLOW);
    s.top=s.size;
    s.stacksize=STRACK_LIST_SIZE;
    return ok;
}

Status DestroyStack(SqStack &s)   //销毁栈
{
	return ok;
}

Status ClearStack(SqStack &s)
{
	return ok;
}

Status StackEmpty(SqStack s)
{
	return s.top==s.base;
}

int StackLength(SqStack s)   //求出栈的长度
{
	return s.top-s.base;
}

Status GetTop(SqStack s,char e)  //如果栈不为空用e返回s的栈顶元素
{
	if(s.top==s.base) return ERROR;
	e=*(s.top-1);
	return ok;
}

Status Push(SqStack s,char e)   //插入元素为e的新的栈顶元素
{
	if(s.top-s.base>=s.stacksize){
		s.base=(char*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(char));
		if(!base)  exit(OVERFLOW);
		s.top=s.base+s.stacksize;
		s.stacksize+=STACKINCREMENT;
	}
	*s.top++=e;
	return ok;
}

Status Pop(SqStack s,char e)    //若栈不为空,则删除s的栈顶元素，并且用e返回其值；
{
	if(s.top==s.base) return ERROR;
	e=*--s.top;
	return ok;
}

Status Reserve(SqStack &s)  //将栈就地逆置
{
int i,n=0;
char a[];
while(!StackEmpty(s))
 	{
 		n++;
 		Pop(s,a[n]);
 	}
 for(i=1;i<=n;i++)
 	 {
 	 	Push(s,a[i]);
 	 }
}
//以下是循环队列的ADT实现
#define MAXSIZE  100

typedef struct{
	char *base;
	int front;
	int rear;
}SqQueue;

Status InitQueue(SqQueue &q)
{
	q.base=(char*)malloc(MAXSIZE*sizeof(char));
	if(!q.base) exit(OVERFLOW);
	Q.base=Q.rear=0;
	return ok;
}

int QueueLength(SqQueue q)       //求出队列的长度
{
	return(q.rear-q.front+MAXSIZE)%MAXSIZE;
}

Status QueueEmpty(SqQueue q)
{
	return q.rear==q.front;
}

Status EnQueue(SqQueue &q,char e)                   //进队
{
	if((q.rear+1)%MAXSIZE==q.front) return ERROR;//队列满
	q.base[q.rear]=e;
	q.rear=(q.rear+1)%MAXSIZE;
}

Status DeQueue(SqQueue &q,char e)
{
	if(q.front==q.rear)  return  ERROR;
	e=q.base[q.front];
	q.front=(q.front+1)%MAXSIZE;
}

////////////////////////////////////////////////
//利用入栈将A,B转换为相对应的语言
void  PushA(SqStack &s1) 
{
	Push(s1,'s');
	Push(s1,'a');
	Push(s1,'e');
}

void PushB(SqStack &s1)
{
	Push(s1,'t');
	PushA(s1);
	Push(s1,'d');
	PushA(s1);
}

//////////////////////////////////////////////////////