考研复习（4）-栈操作

终于把栈搞定了，还是自己太懒。

主要的算法是1）数的的进制转换2）括号匹配3）行编辑

迷宫那个还是先放一下吧。。。。

#include<stdio.h>

#include<stdlib.h>
#define MAXSIZE 100
#define STACK_INCREASE 10
typedef char ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
int stacksize;
} Sstack;
void Init(Sstack *S)
{
S->base=(ElemType *)malloc(MAXSIZE*sizeof(ElemType));
if(!S->base)
exit(0);
S->top=S->base;
S->stacksize=MAXSIZE;
}
ElemType Gettop(Sstack S)
{
if(S.base==S.top)
printf("No Element!\n");
else
return(*(--S.top));
}
void push(Sstack *S,ElemType x)
{
if(S->top-S->base>=S->stacksize)
{
S->base=(ElemType *)realloc(S->base,(S->stacksize+STACK_INCREASE)*sizeof(ElemType));
if(!S->base)
exit(0);
else
S->stacksize+=STACK_INCREASE;


}


*(S->top)=x;
S->top++;


}
ElemType pop(Sstack *S)
{
ElemType c;
if(S->top==S->base)
exit(0);
else
{
c=Gettop(*S);
S->top--;
return c;
}


}
void ClearStack(Sstack *S)
{
while(!StackEmpty(*S))
{
pop(S);
}
}
void show(Sstack S)
{
while(S.top!=S.base)
{
printf("%5c",*(S.base));
S.base++;
}
printf("\n");


}
//实例，十进制输入，八进制输出
//N=(N div d)*d+N mod d
void conversion()
{
int i;
Sstack S;
Init(&S);
printf("Please input a decimal numbel:\n");
scanf("%d",&i);
while(i)
{
push(&S,i%8);
i=i/8;
}
while(S.top!=S.base)
{
printf("%d",Gettop(S));
S.top--;
}
printf("\n");
}
int StackEmpty(Sstack S)
{
if(S.top==S.base) return 1;
else return 0;
}
//括号匹配，遇左括号进栈，遇有括号出栈，开始与最后都为空栈
int match(char *exp)
{
Sstack S;
Init(&S);
int i=0,j=1,b=1;
printf("exp:%c\n",exp[3]);
char c=NULL;
while(exp[i]!='\0'&&b==1)
{
//printf("exp[i]:%c\n",exp[i]);
if(exp[i]=='(') push(&S,exp[i]);
if(exp[i]==')')
{
c=pop(&S);
if(c!='(') b=0;
}


i++;
}
return(b&&StackEmpty(S));


}


void LineEdit()
{
Sstack S;
Init(&S);
char ch=getchar();
while(ch!=EOF)
{
while(ch!=EOF&&ch!='\n')
{
switch(ch)
{
case '#':pop(&S); break;
case '@':ClearStack(&S); break;
default:push(&S,ch); break;
}
ch=getchar();
}
show(S);
//do some action to transmit the data
ClearStack(&S);
if(ch!=EOF) ch=getchar();
}
//DestroyStack();
}
main()
{
LineEdit();
char *ex="(())";
printf("ex:%c\n",ex[3]);
printf("Is Matched?%d",match(ex));
Sstack S;
Init(&S);
printf("Is empty?%d",StackEmpty(S));
printf("Push three!\n");
push(&S,'a');
push(&S,'s');
push(&S,'w');


show(S);
printf("Pop one!\n");
pop(&S);
show(S);
printf("十进制输入，八进制输出\n");
conversion();




Gettop(S);
printf("Hello!\n");
}