当前位置：首页 > article >正文

C语言实现括号匹配检查及栈的应用详解

article 2025/3/15 15:59:47

栈数据结构简介

C语言实现栈

栈的初始化

栈的销毁

栈的插入

栈的删除

栈的判空

获取栈顶数据

利用栈实现括号匹配检查

总结

在编程中，经常会遇到需要检查括号是否匹配的问题，比如在编译器中检查代码的语法正确性，或者在文本处理中确保括号的正确使用。本文将通过C语言实现一个括号匹配检查的程序，并详细介绍栈数据结构在其中的应用。

栈数据结构简介

栈是一种后进先出（LIFO, Last In First Out）的数据结构。它就像一个放盘子的栈，最后放上去的盘子总是最先被拿下来。在栈中，有几个基本操作：

- 初始化（Init）：创建一个空栈。

- 销毁（Destroy）：释放栈占用的内存。

- 插入（Push）：将元素添加到栈顶。

- 删除（Pop）：从栈顶移除元素。

- 判空（Empty）：检查栈是否为空。

- 获取元素个数（Size）：返回栈中元素的数量。

- 获取栈顶数据（Top）：返回栈顶的元素，但不删除它。

C语言实现栈


c
  
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef char typestk;
typedef struct Stack
{
    typestk* a;
    int top;
    int capacity;
} ST;

这里定义了一个栈的结构体 Stack ，包含一个字符类型的指针 a 用于存储栈中的元素， top 表示栈顶的位置， capacity 表示栈的容量。

栈的初始化


c
  
// 栈的初始化
void STInit(ST* ps)
{
    assert(ps);

    ps->a = (typestk*)malloc(sizeof(typestk) * 4);
    if (ps->a == NULL)
    {
        perror("malloc");
        return;
    }
    ps->top = 0;
    ps->capacity = 4;
}

STInit 函数用于初始化栈。首先通过 malloc 分配4个字符大小的内存空间给栈的数组 a ，如果分配失败，使用 perror 打印错误信息。然后将栈顶位置 top 设为0，栈容量 capacity 设为4。

栈的销毁


c
  
// 栈的销毁
void STDestory(ST* ps)
{
    // 查空
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

STDestory 函数用于销毁栈。先使用 free 释放栈数组 a 占用的内存，然后将指针 a 设为 NULL ，并将栈顶位置 top 和栈容量 capacity 都设为0。

栈的插入

 
c
  
// 栈的插入
void STPush(ST* ps, typestk x)
{
    assert(ps);

    if (ps->top == ps->capacity)
    {
        typestk* tmp = (typestk*)realloc(ps->a, sizeof(typestk) * ps->capacity * 2);
        if (tmp == NULL)
        {
            perror("realloc error");
            return;
        }
        ps->a = tmp;
        ps->capacity *= 2;
    }

    ps->a[ps->top] = x;
    ps->top++;
}

STPush 函数用于将元素插入栈顶。首先检查栈是否已满（即 top 等于 capacity ），如果已满，使用 realloc 将栈的容量扩大为原来的2倍。如果内存重新分配失败，打印错误信息并返回。然后将元素 x 插入到栈顶位置，并将栈顶位置 top 加1。

栈的删除

 
c
  
// 栈的删除
void STPop(ST* ps)
{
    assert(ps);
    assert(!STEmpty(ps));    ps->top--;
}

STPop 函数用于从栈顶删除元素。首先检查栈是否为空，如果为空则使用 assert 断言报错。然后将栈顶位置 top 减1，相当于删除了栈顶元素。

栈的判空

 
c
  
// 栈的判空
bool STEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}
 
 
 STEmpty 函数用于检查栈是否为空。如果栈顶位置 top 为0，则返回 true ，否则返回 false 。
 
栈的元素个数
 
c
  
// 栈的元素个数
int STSize(ST* ps)
{
    assert(ps);
    return ps->top;
}

STSize 函数返回栈中元素的个数，即栈顶位置 top 的值。

获取栈顶数据


c
  
// 获取栈顶数据
typestk STTop(ST* ps)
{
    assert(ps);
    assert(!STEmpty(ps));
    return ps->a[ps->top - 1];
}

STTop 函数返回栈顶的元素，但不删除它。首先检查栈是否为空，如果为空则使用 assert 断言报错。然后返回栈顶位置 top - 1 处的元素。

利用栈实现括号匹配检查

 
c
  
bool isValid(char* s)
{
    ST st;
    STInit(&st);
    while (*s)
    {
        if (*s == '[' || *s == '(' || *s == '{')
        {
            STPush(&st, *s);
        }
        else
        {
            if (STEmpty(&st))
            {
                STDestory(&st);
                return false;
            }
            char top = STTop(&st);
            STPop(&st);
            if ((*s == ')' && top != '(') || (*s == ']' && top != '[') || (*s == '}' && top != '{'))
            {
                STDestory(&st);
                return false;
            }

        }
        ++s;
    }
    bool ret = STEmpty(&st);
    STDestory(&st);
    return ret;
}

isValid 函数用于检查给定字符串中的括号是否匹配。

初始化一个栈 st 。

遍历字符串 s ：

- 如果当前字符是左括号（ [ 、 ( 、 { ），将其压入栈中。

- 如果当前字符是右括号（ ] 、 ) 、 } ）：

- 检查栈是否为空，如果为空，说明没有匹配的左括号，返回 false 。

- 否则，获取栈顶元素并弹出栈，检查栈顶元素是否与当前右括号匹配。如果不匹配，返回 false 。

遍历结束后，如果栈为空，说明所有括号都匹配，返回 true ；否则返回 false 。最后销毁栈。