|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef char ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
int stacksize;
}stack;
void initstack(stack &s) // 创建一个栈
{
s.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if(!s.base)
{
exit(0);
}
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
}
void push(stack &s, ElemType e) //入栈
{
if(s.top - s.base >= s.stacksize)
{
s.base=(ElemType *)realloc(s.base,(s.stacksize + STACKINCREMENT) * sizeof(ElemType) );
if( !s.base)
exit(0);
s.top=s.base+s.stacksize;
s.stacksize+=STACKINCREMENT;
}
*(s.top)=e;
s.top++;
}
void pop(stack &s, ElemType &e) // 出栈
{
if(s.top==s.base)
return;
e=*--(s.top);
}
typedef struct QNode //生成结点
{
ElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct LinkQueue
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
void initQueue(LinkQueue &q) // 创建队列
{
q.front = q.rear = (QueuePtr)malloc(sizeof(QNode));
if(!q.front)
exit(0);
q.front->next=NULL;
}
void InsertQueue(LinkQueue &q,ElemType e) //入队
{
struct QNode* p;
p=(QueuePtr)malloc(sizeof(QNode));
if(p==NULL)
exit(0);
p->data=e;
p->next=NULL;
q.rear->next=p;
q.rear=p;
}
void DeleteQueue(LinkQueue *q, ElemType *e) // 出队
{
QueuePtr p;
if(q->front==q->rear)
return;
p=q->front->next;
*e=p->data;
q->front->next=p->next;
if(q->rear==p)
q->rear=q->front;
free(p);
}
void Instack(ElemType *ch, stack &s)
{
int i,L=0;
while(ch[L]!='\0') L++;
for(i=L-1; i>=0; i--)
push(s,ch[i]);
}
int QueueEmpty(LinkQueue q)
{
if(q.front=q.rear)
return 1;
else return 0;
}
int stackempty(stack *s)
{
if(s->top=s->base)
return 1;
else return 0;
}
int main()
{
printf("请输入你想要解释的魔王语言:\n");
while(1)
{
ElemType flag='0';
ElemType e1,key,e2,e,a,b;
int mark=1;
int f=1;
ElemType mowang[100]="\0";
stack s,temp,A,B;
initstack(s);
initstack(A);
initstack(B);
initstack(temp);
LinkQueue Q;
initQueue(Q);
gets(mowang);
push(B,'t');
push(B,'A');
push(B,'d');
push(B,'A');
push(A,'s');
push(A,'a');
push(A,'e');
Instack(mowang,s);
while(!stackempty(&s))
{
pop(s,e1);
if(e1=='B')
{
while(!stackempty(&B))
{
pop(B,b);
push(temp,b);
}
}
else if(e1=='A')
{
while(!stackempty(&A))
{
pop(A,a);
push(temp,a);
}
}
else if(e1=='(')
{
push(temp,flag);
pop(s,e1);
while(e1!=')')
{
InsertQueue(Q,e1);
pop(s,e1);
}
if(!QueueEmpty(Q))
DeleteQueue(&Q,&key);
}
else {push(temp,e1);
f=0;}
}
while(!stackempty(&temp))
{
pop(temp,e1);
if(e1!=flag) {push(s,e1);}
else{
while(!QueueEmpty(Q))
{
DeleteQueue(&Q,&e2);
push(s,key);
push(s,e2);
}
if(f!=0)
{
push(s,key);
}
}
}
printf("解释后的语言为:\n");
while(!stackempty(&s))
{
pop(s,e);
printf("%c",e);
}
}
printf("\n");
system("pause");
return 0;
}
|
|