LC20. 有效的括号

用来熟悉一下栈的应用之括号匹配

题目链接

下面是大致思路
1.初始化:创建一个空栈,用于存储左括号。（LC这题不用，自己写完整的需要）
2.遍历字符串:从左到右依次扫描字符串中的每个字符。
3.处理左括号:如果是左括号,将其压入栈中。
4.处理右括号:如果是右括号,检查找顶元素是否与其匹配:

如果匹配,弹出栈顶元素。
如果不匹配,返回false,表示括号不匹配。

5.检查栈是否为空:

遍历结束后,检查找是否为空。
如果栈为空,表示所有括号匹配;否则,返回false。
（还有就是一开始可以直接排除掉奇数个的情况，不可能匹配

可运行版

下面就是注意一个地方

pairs函数，在扫描的时候如果发现是左括号，那么会进入后面的else逻辑，让左括号入栈
如果发现是右括号
那么会返回与之匹配的左括号，去和当前栈顶的左括号匹配

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

// 定义一个函数 pairs，用于返回与右括号对应的左括号
char pairs(char a)
{
    if (a == '}')
        return '{';
    if (a == ']')
        return '[';
    if (a == ')')
        return '(';
    return 0;
}

// 检查括号是否匹配的函数
bool isValid(char *s)
{
    int n = strlen(s); // 获取字符串的长度
    if (n % 2 == 1)
    { // 如果字符串长度是奇数，不可能匹配
        return false;
    }

    int *stk = (int *)malloc((n + 1) * sizeof(int)); // 动态分配栈的大小
    if (stk == NULL)
    {
        printf("Memory allocation failed\n");
        return false;
    }

    int top = 0; // 初始化栈顶指针
    int i;       // 将变量声明移到循环外部
    for (i = 0; i < n; i++)
    {
        char ch = pairs(s[i]); // 获取与当前字符对应的左括号
        if (ch)
        { // 如果当前字符是右括号
            if (top == 0 || stk[top - 1] != ch)
            {              // 检查栈是否为空或栈顶元素是否匹配
                free(stk); // 释放动态分配的内存
                return false;
            }
            top--; // 弹出栈顶元素
        }
        else
        {                      // 如果当前字符是左括号
            stk[top++] = s[i]; // 将左括号压入栈中
        }
    }

    bool result = (top == 0); // 如果栈为空，表示所有括号匹配
    free(stk);                // 释放动态分配的内存
    return result;
}

// 示例使用
int main()
{
    printf("%d\n", isValid("()"));     // 输出: 1 (true)
    printf("%d\n", isValid("()[]{}")); // 输出: 1 (true)
    printf("%d\n", isValid("(]"));     // 输出: 0 (false)
    printf("%d\n", isValid("([)]"));   // 输出: 0 (false)
    printf("%d\n", isValid("{[]}"));   // 输出: 1 (true)
    // 复杂的例子
    printf("%d\n", isValid("{[()]}"));       // 输出: 1 (true)
    printf("%d\n", isValid("{[(])}"));       // 输出: 0 (false)
    printf("%d\n", isValid("{{[[(())]]}}")); // 输出: 1 (true)
    return 0;
}

cpp


#include <iostream>
#include <stack>
#include <string>
using namespace std;
class Solution
{
public:
    bool isMatch(char a, char b)
    {
        if ((a == '(' && b == ')') || (a == '[' && b == ']') || (a == '{' && b == '}'))
        {
            return true;
        }
        return false;
    }
    bool isValid(string s)
    {
        stack<char> stk; // 定义一个栈，用来存放左括号
        // stack是一个容器适配器，它提供了一种先进后出的数据结构，即栈。只能在栈顶进行插入和删除操作。
        if (s.size() % 2 == 1)
            return false; // 如果字符串长度为奇数则不可能有效，直接返回false；
        for (int i = 0; i < s.size(); i++)
        {   
            // 扫描字符串，遇到左括号入栈，遇到右括号则与栈顶元素匹配；
            if (s[i] == '(' || s[i] == '[' || s[i] == '{')
                stk.push(s[i]); // 遇到左括号入栈；
            // 下面的两个else if 和 else都是对右括号情况的处理
        
            else if (stk.empty())
                return false; // 如果遇到了右括号但是栈已经空了，说明不是有效的括号,直接返回false;
            else if (!isMatch(stk.top(), s[i]))
                return false; // 如果遇到右括号且栈不为空，但是栈顶不是相匹配的左括号，返回false;
            else
                stk.pop(); // 当前遍历到的右括号与栈顶左括号相匹配，弹出栈顶元素继续遍历；
        }
        return stk.empty(); // 遍历结束后，栈为空则为有效，否则无效；
    }
};

int main()
{
    Solution s;
    cout << s.isValid("()") << endl;     // 输出: 1 (true)
    cout << s.isValid("()[]{}") << endl; // 输出: 1 (true)
    cout << s.isValid("(]") << endl;      // 输出: 0 (false)
    return 0;
}

LC版

C++版
在这里插入图片描述
注意两个empty的不同
比如具体的例子如下

在这里插入图片描述

class Solution {
public:
    bool isMatch(char a,char b)
    {
        if(a == '(' && b == ')' ||a == '[' && b == ']'||a == '{' && b == '}')
            return true;
        else
            return false;
    }
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }

        stack<char> stk;
        for(int i = 0; i < n ; i++)
        {
            if(s[i]=='(' || s[i]=='[' || s[i]=='{' )
                stk.push(s[i]);
        
            else if(stk.empty())
                return false;
            else if(!isMatch(stk.top(),s[i]))
                return false;
            else if(isMatch(stk.top(),s[i]))
                stk.pop();
            
        }
        return stk.empty(); // 遍历结束后，栈为空则为有效，否则无效；

    }

      

};

C版

char pairs(char a) {
    if (a == '}') return '{';
    if (a == ']') return '[';
    if (a == ')') return '(';
    return 0;
}

bool isValid(char* s) {
    int n = strlen(s);
    if (n % 2 == 1){
        return false;
    }

    int stk[n + 1], top = 0;
    for (int i = 0; i < n; i++)
    {
        char ch = pairs(s[i]);
        if(ch) // 如果是右括号
        {
            if ( top == 0 || stk[top - 1] != ch) {
                // 如果是空栈或者不匹配
                return false;
            }

            top --; // 匹配了就要出栈了（top--指向新的位置）
        }
        else  //如果是左括号就入栈
        {
            //一开始top是0，那么先赋值再移动指针指向下一个位置
            stk[top] = s[i];
            top++;
        }

    }

    return top == 0; //最后应该都出栈了
}

//总结：其实就是把哪些不成立的条件先列出来，还有注意各种边界条件，然后理解了算法原理，就能写出代码了