栈(顺序)的实现：括号的解析

一、问题引入

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

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

源码链接https://github.com/caojun97/Bracket_Match

二、过程记录

2-1 栈的介绍

栈按照存储结构可以划分为：顺序栈 和 链栈。 顺序栈空间是固定上限的，入栈到固定上限就不能再执行入栈操作。而链栈就没有这种固定上限，上限取决与系统内存上限。

定义：栈(stack) 是限定仅在表尾进行插入或删除操作的线性表。
因此，对栈来说，表尾端有其特殊含义，称为栈顶(top), 相应地，表头端称为栈底(bottom)。不含元素的空表称为空栈

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

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

• 栈初始化

• 入栈

• 出栈

• 栈销毁

2-2 数据结构定义

#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;        // 栈可用的最大容量
	int  num_of_elem;       // 栈中元素数量
}SqStack_T;

2-3 栈操作定义

• 栈初始化

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;
	sq_stack_pt->num_of_elem = 0;
	return OK;
}

• 入栈

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

• 出栈

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

• 取栈顶元素

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;
}

• 栈销毁

void stack_destory(SqStack_T *sq_stack_pt)
{
	if (sq_stack_pt->base != NULL)
		free(sq_stack_pt->base);
	sq_stack_pt->base = NULL;
	sq_stack_pt->top = NULL;
	sq_stack_pt->num_of_elem = 0;
}

2-4 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];
			stack_push(&sq_stack_t, elem); // 入栈
		}
		else if (buffer[i] == ']' || buffer[i] == ')' || buffer[i] == '}')
		{
			BracketInfo elem_top = { 0 }, elem = {0};
			elem_top = stack_top_element_get(sq_stack_t);
			if (buffer[i] == ']')
			{
				if (elem_top.bracket == '[')
				{
					stack_pop(&sq_stack_t, &elem); // 出栈
				}
			}
			else if (buffer[i] == ')')
			{
				if (elem_top.bracket == '(')
				{
					stack_pop(&sq_stack_t, &elem); // 出栈
				}
			}
			else if (buffer[i] == '}')
			{
				if (elem_top.bracket == '{')
				{
					stack_pop(&sq_stack_t, &elem); // 出栈	
				}
			}
			if(elem.bracket == 0)
				printf("  %c    (-1,%d)\n", buffer[i], i);
			else
				printf("%c %c    (%d,%d)\n", elem.bracket, buffer[i], elem.idx, i);
		}
	}
	stack_destory(&sq_stack_t);
	return 0;
}

• 修改输入buffer

char buffer[50] = { "[a*(b+c)-d*(e-f)]" };

三、反思总结

将数据结构结合实际项目进行学习和理解才能事半功倍。栈-数据结构是固定，思考应用场景能否利用栈结构实现。

四、参考引用

数据结构第二版：C语言版 【严蔚敏】

原文链接：https://www.cnblogs.com/caojun97/p/17246869.html