栈的实现：括号的解析

一、问题引入

在学习栈的过程中，教材有一个案例：利用栈结果解析括号的匹配问题。括号问题：[({}{})]，说明 [] 、() 、{} 称为一对。

号码位置对应的括号之间进行匹配，结果：0-7、 1-6、 2-3、 4-5

二、过程记录

???? 基于顺序栈实现

利用栈的特性：先进后出 ，对括号进行匹配输出

对栈的基本操作进行抽象定义函数：

栈初始化
入栈
出栈
栈销毁

2-1 数据结构定义

#define MAXSIZE 100 // 顺序栈存储空间的初始分配量

#define ERROR -1
#define OK 0
#define OVERFLOW 1

typedef struct
{
	char bracket;  // 存储括号字符
	int  idx;      // 存储括号字符索引
}BracketInfo;

typedef struct
{
	BracketInfo *base;      // 栈底指针
	BracketInfo *top;       // 栈顶指针
	int  stack_size;        // 栈可用的最大容量
}SqStack_T;

2-2 栈操作定义

栈初始化

static int stack_init(SqStack_T *sq_stack_pt)
{
	/* base为栈底指针，初始化完成后，栈底指针base始终指向栈底位置.
	 * 若base的值为NULL，则表明栈结构不存在。 
	*/
	sq_stack_pt->base = (BracketInfo *)malloc(MAXSIZE * sizeof(BracketInfo));
	if (NULL == sq_stack_pt->base)
	{
		printf("malloc memory fail\n");
		exit(OVERFLOW); // 退出程序
	}
	sq_stack_pt->top = sq_stack_pt->base;
	sq_stack_pt->stack_size = MAXSIZE;
	return OK;
}

入栈

static int stack_push(SqStack_T *sq_stack_pt, BracketInfo elem)
{
	// 入栈前，先判断是否栈满
	if (sq_stack_pt->base - sq_stack_pt->top == sq_stack_pt->stack_size)
		return ERROR;
	// 元素入栈，栈顶指针top+1
	*(sq_stack_pt->top) = elem;
	(sq_stack_pt->top)++;
	return OK;
}

出栈

static int stack_pop(SqStack_T *sq_stack_pt, BracketInfo *elem)
{
	// 出栈前，先判断是否栈空
	if (sq_stack_pt->top == sq_stack_pt->base)
	{
		
		return ERROR;
	}
	// 元素出栈，栈顶指针top-1
	sq_stack_pt->top--;
	*elem = *(sq_stack_pt->top);
	return OK;
}

取栈顶元素

static BracketInfo stack_top_element_get(SqStack_T sq_stack_t)
{
	BracketInfo elem = { 0 };
	if (sq_stack_t.top != sq_stack_t.base)
		elem = *(sq_stack_t.top - 1);
	return elem;
}

栈销毁

static int stack_destory(SqStack_T *sq_stack_pt)
{
	if (sq_stack_pt->base != NULL)
		free(sq_stack_pt->base);
	return OK;
}

2-3 main函数

???? 数据结构的定义和栈操作的定义都放在文件 sq_stack.h 和 sq_stack.c 中

#include "sq_stack.h"
#include <stdio.h>

int main(void)
{
	SqStack_T sq_stack_t;
	stack_init(&sq_stack_t);
	char buffer[50] = { "[({}{})]" };
	int buffer_len = strlen(buffer);
	for (int i = 0; i < buffer_len; i++)
	{
		if (buffer[i] == '[' || buffer[i] == '(' || buffer[i] == '{')
		{
			BracketInfo elem = { 0 };
			elem.idx = i;
			elem.bracket = buffer[i];
			if (ERROR == stack_push(&sq_stack_t, elem)) // 入栈
				printf("stack full\n");
		}
		else
		{
			BracketInfo elem_top, elem;
			elem_top = stack_top_element_get(sq_stack_t);
			if (buffer[i] == ']')
			{
				if (elem_top.bracket == '[')
				{
					if (ERROR == stack_pop(&sq_stack_t, &elem)) // 出栈
						printf("stack empty\n");
				}
			}
			else if (buffer[i] == ')')
			{
				if (elem_top.bracket == '(')
				{
					if (ERROR == stack_pop(&sq_stack_t, &elem)) // 出栈
						printf("stack empty\n");
				}
			}
			else if (buffer[i] == '}')
			{
				if (elem_top.bracket == '{')
				{
					if (ERROR == stack_pop(&sq_stack_t, &elem)) // 出栈
						printf("stack empty\n");
				}
			}
			printf("%c %c (%d,%d)\n", elem.bracket, buffer[i], elem.idx, i);
		}
	}
	stack_destory(&sq_stack_t);
	return 0;
}