苗火 Nicholas

[Data structures]Stack

2019-8-30 萧 写技术

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 1024

typedef struct _SqStack{
	int *base;
	int *top;
	int stackSize;
}SqStack;

int InitStack(SqStack *S)
{
	S->base = (int *)malloc(MAX*sizeof(int));
	S->top = S->base;
	S->stackSize = MAX;	
	return 1;
}

int GetTop(SqStack *S, int *e)
{
	if(S->top == S->base){
		return 0;
	}else{
		*e = *(S->top - 1);
		return 1;
	}
}

int Push(SqStack *S, int e)
{
	if(S->top - S->base >= S->stackSize){
		return 0;
	}
	*(S->top++) = e;
}

int Pop(SqStack *S, int *e)
{
	if(S->top == S->base){
		return 0;
	}else{
		*e = *(--S->top);
		return 1;
	}
}

int StackEmpty(SqStack *S)
{
	if(S->top == S->base){
		return 1;
	}else{
		return 0;
	}
}

int ClearStack(SqStack *S)
{
	S->top = S->base;
	return 1;
}

int PrintStack(SqStack *S)
{
	int *p = S->base;
	while(p != S->top){
		printf("%c", (char)*p);
		p++;
	}
	printf("\n");
	return 1;
}

void Conversion()
{
	SqStack S;
	int N;
	InitStack(&S);
	scanf(" %d", &N);
	printf("Decimal:%d, \nOctonary:", N);
	while(N){
		Push(&S, N%8);
		N /= 8;
	}
	while(!StackEmpty(&S)){
		Pop(&S, &N);
		printf("%d", N);
	}
	printf("\n");
}

void Brackets()
{
	SqStack S;
	char str[MAX];
	int i=-1;
	int t;

	InitStack(&S);
	scanf(" %s", str);
	printf("Input:%s, \nMatching result:", str);
	while(str[++i] != 0){
		GetTop(&S, &t);
		if(str[i] == '(' || str[i] == '['){
			Push(&S, (int)str[i]);
		}else if(str[i] == ')'){
			if((char)t != '('){
				printf("Not match:%d\n", i);
				return;
			}else{
				Pop(&S, &t);
			}
		}else if(str[i] == ']'){
			if((char)t != '['){
				printf("Not match:%d\n", i);
				return;
			}else{
				Pop(&S, &t);
			}
		}
	}
	printf("Match ok.\n");
	return;
}

void LineEdit()
{
	SqStack S;
	char ch;
	int t;
	getchar();//Delete last '\n'
	InitStack(&S);
	while((ch = getchar()) != '$'){
		if(ch != '\n'){
			switch(ch){
				case '#':
					Pop(&S, &t);
					break;
				case '@':
					ClearStack(&S);
					break;
				default:
					Push(&S, (int)ch);
					break;
			}
		}else{
			PrintStack(&S);
			ClearStack(&S);
		}
	}
}


void main()
{
	printf("log.anycle.com\n\n");

	printf("Conversion:\n");
	Conversion();
	printf("\n");

	printf("Brackets matching:\n");
	Brackets();
	printf("\n");

	printf("Line edit:\n");
	LineEdit();
	printf("\n");
}

标签: Data Structures data_structures