栈和队列oj题——20. 有效的括号

个人主页：晓风飞
专栏：数据结构|Linux||C语言

---

要做题目的点击这里–>栈和队列oj题——20. 有效的括号

解题核心思路

当解决使用栈来检查字符串中括号平衡的问题时，主要思路是遵循左括号与右括号的配对规则。我们使用一个栈来跟踪所有未闭合的左括号，并在遇到相应的右括号时检查是否有匹配的左括号。以下是详细的解题思路：

使用STInit(&st);初始化栈。

这是为了存储遇到的左括号。

 ST st;
    STInit(&st); // 初始化栈

遍历字符串：

创建一个空栈，用于存储遇到的左括号。
遍历字符串中的每个字符：
while(*s)循环遍历字符串中的每个字符。

处理左括号：

if(*s == ‘{’ || *s == ‘[’ || *s == ‘(’)检查当前字符是否为左括号。
如果是，使用STPush(&st, *s);将其压入栈中。

if(*s == '{' || *s == '[' || *s =='(')
            {
                STPush(&st,*s);// 如果是左括号，压入栈
            }

处理右括号：

如果当前字符是右括号，首先检查栈是否为空：if(STEmpty(&st))。
如果栈为空，使用STDestroy(&st);销毁栈并返回false。这表示没有相应的左括号与之匹配。
如果栈不为空，使用char top = STTop(&st);获取栈顶元素（最近的未匹配左括号），然后用STPop(&st);弹出它。接下来，检查栈顶元素是否与当前的右括号匹配。如果不匹配，销毁栈并返回false。

 else
            {
                if(STEmpty(&st))
                {
                    return false;// 如果栈为空，则说明没有相匹配的左括号，返回false
                    STDestroy(&st);
                }

                char top = STTop(&st);// 获取栈顶元素
                STPop(&st); // 弹出栈顶元素
                if
                (
                    (*s == '}' && top!= '{') ||
                    (*s == ']' && top!= '[') ||
                    (*s == ')' && top!= '(') 
                )
                {
                    return false;// 如果栈顶元素与当前右括号不匹配，返回false
                    STDestroy(&st);          
                }
            }
            s++;// 移动到下一个字符
   		   

字符串遍历完成：

当遍历完整个字符串后，使用bool ret = STEmpty(&st);检查栈是否为空。
如果栈为空，返回true，表示所有的括号都已正确匹配。
如果栈不为空，表示有未匹配的左括号，返回false。

 bool ret = STEmpty(&st);// 检查栈是否为空，即所有括号是否都已匹配

使用STDestroy(&st);销毁栈，释放资源。

在返回最终结果之前，销毁栈以释放分配的资源。

STDestroy(&st); // 销毁栈

这个方法的关键在于利用栈的特性——后进先出（LIFO）——确保我们总是检查最近的未匹配左括号与当前右括号是否匹配。这种方式能有效地处理所有嵌套和顺序相关的括号匹配问题。

以下是栈的实现:

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

void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst,STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);

// 初始化栈
void STInit(ST* pst)
{
  assert(pst);
  pst->a = NULL;       // 初始时，数组指针为空
  pst->top = 0;        // 栈顶指针初始为0，表示栈为空
  pst->capacity = 0;   // 初始容量为0
}

// 销毁栈
void STDestroy(ST* pst)
{
  assert(pst);
  free(pst->a);        // 释放栈内部的数组空间
  pst->a = NULL;       // 将数组指针置为空
  pst->top = 0;        // 栈顶指针重置为0
  pst->capacity = 0;   // 容量重置为0
}

// 检查并扩展栈的容量
void SLCheckCapacity(ST* pst)
{
  assert(pst);
  if (pst->top == pst->capacity)
  {
    int newCapacity = (pst->capacity == 0) ? 4 : pst->capacity * 2;
    STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newCapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(1); // 如果内存分配失败，则退出程序
    }

    pst->a = tmp;
    pst->capacity = newCapacity;
  }
}

// 向栈中推入一个元素
void STPush(ST* pst, STDataType x)
{
  assert(pst);
  SLCheckCapacity(pst); // 检查并扩展容量
  pst->a[pst->top] = x; // 存放元素
  pst->top++;           // 栈顶指针增加
}

// 从栈中弹出一个元素
void STPop(ST* pst)
{
  assert(pst);
  assert(pst->top > 0); // 确保栈不为空
  pst->top--;           // 栈顶指针减少
}

// 获取栈顶元素
STDataType STTop(ST* pst)
{
  assert(pst);
  assert(pst->top > 0); // 确保栈不为空
  return pst->a[pst->top - 1]; // 返回栈顶元素
}

// 检查栈是否为空
bool STEmpty(ST* pst)
{
  assert(pst);
  return pst->top == 0; // 如果栈顶指针为0，则栈为空
}

// 获取栈的大小
int STSize(ST* pst)
{
  assert(pst);
  return pst->top; // 返回栈顶指针的位置，即栈的大小
}

以下是本题的实现:

    bool isValid(char* s) 
    {
        ST st;
        STInit(&st);// 初始化栈
        while(*s)// 遍历字符串
        {
            if(*s == '{' || *s == '[' || *s =='(')
            {
                STPush(&st,*s);// 如果是左括号，压入栈
            }
            else
            {
                if(STEmpty(&st))
                {
                    return false;// 如果栈为空，则说明没有相匹配的左括号，返回false
                    STDestroy(&st);
                }

                char top = STTop(&st);// 获取栈顶元素
                STPop(&st); // 弹出栈顶元素
                if
                (
                    (*s == '}' && top!= '{') ||
                    (*s == ']' && top!= '[') ||
                    (*s == ')' && top!= '(') 
                )
                {
                    return false;// 如果栈顶元素与当前右括号不匹配，返回false
                    STDestroy(&st);          
                }
            }
            s++;// 移动到下一个字符
        }
        bool ret = STEmpty(&st);// 检查栈是否为空，即所有括号是否都已匹配
        STDestroy(&st); // 销毁栈
        return ret;
    }