一、问题引入
在学习栈的过程中，教材有一个案例：利用栈结构解析括号的匹配问题。括号问题：[({}{})]，说明 [] 、() 、{} 称为一对且满足就近匹配。
号码位置对应的括号之间进行匹配，结果：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语言版 【严蔚敏】