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

LC20. 有效的括号

news 2024/10/30 23:45:58

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

题目链接

下面是大致思路
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;elsestk.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;elsereturn 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; //最后应该都出栈了
}//总结：其实就是把哪些不成立的条件先列出来，还有注意各种边界条件，然后理解了算法原理，就能写出代码了