栈和队列的应用—魔王语言

发布网友发布时间：2022-03-29 17:16

共1个回答

热心网友时间：2022-03-29 18:45

虽然这个实验是"栈和队列"这章的,但并不表示你的程序中一定要用到队列啊.
把程序中的队列改成另一个栈就行了.

修改后的程序如下:

#include <stdio.h>
#include <malloc.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

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

void InitStack(SqStack &S); //构造一个新栈S
bool StackEmpty(SqStack &S);
void Push(SqStack &S, char e); //把e入栈
void Pop(SqStack &S, char &e); //把栈顶元素出栈，赋值给e

void InitStack(SqStack &S) //这里你原来写的是InitSack，要改过来
{
S.base = (int *)malloc(STACK_INIT_SIZE * sizeof(int));
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
}

bool StackEmpty(SqStack &S)
{
return S.top == S.base;
}

void Push(SqStack &S, char e)
{
if(S.top - S.base >= S.stacksize)
{
S.base = (int *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(int));
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*(S.top++) = e;
}

void Pop(SqStack &S, char &e)
{
if(S.top != S.base)
{
e = *(--S.top);
}
}

int main()
{
char e, h, eve, cs, css[100];
int k = 0;
SqStack S;
InitStack(S);

while(scanf("%c", &cs) != EOF)
{
if(cs == '#')
break;
else
{
css[k] = cs;
k++;
}
}

for(int i = k - 1; i >= 0; i--)
{
if(')' == css[i])
{
//这里把临时队列改成临时栈，下面相应的队列操作都改成栈操作
SqStack temp;
InitStack(temp);
i--;
while('(' != css[i])
{
Push(temp, css[i]);
i--;
}
Pop(temp,eve);
while(!StackEmpty(temp))
{
Push(S, eve);
Pop(temp, h);
Push(S, h);
}
Push(S, eve);
i--;
if('A' == css[i])
{
Push(S, 'e');
Push(S, 'a');
Push(S, 's');
}
if('B' == css[i])
{
Push(S, 'e');
Push(S, 'a');
Push(S, 's');
Push(S, 'd');
Push(S, 'e');
Push(S, 'a');
Push(S, 's');
Push(S, 't');
}
}
else
{
if('A' == css[i])
{
Push(S, 'e');
Push(S, 'a');
Push(S, 's');
}
if('B' == css[i])
{
Push(S, 'e');
Push(S, 'a');
Push(S, 's');
Push(S, 'd');
Push(S, 'e');
Push(S, 'a');
Push(S, 's');
Push(S, 't');
}
}
}

while(!StackEmpty(S))
{
Pop(S, e);
printf("%c", e);
}
printf("\n");
return 0;
}