20. 有效的括号（力扣）

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
 

示例 1：

输入：s = "()"
输出：true
示例 2：

输入：s = "()[]{}"
输出：true
示例 3：

输入：s = "(]"
输出：false
示例 4：

输入：s = "([)]"
输出：false
示例 5：

输入：s = "{[]}"
输出：true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses

---

 思路一（利用栈）

对字符串从左到右进行处理

如果是左括号（包括 ( , [ , {  ），则入栈；

如果是右括号，则判断栈顶元素是否与右括号匹配

1. 栈空，右括号无法匹配--则直接可以得到结果--false
2. 栈顶元素与右括号不匹配--则直接可以得到结果--false
3. 栈顶元素与右括号匹配--则弹出栈顶元素

处理完字符串后，再判断栈是否为空

• 栈空--说明字符串中的左右括号刚好匹配
• 栈不空--说明左括号有剩余

class Solution {
public:bool isValid(string s) {stack<char> v;for (int i = 0; i < s.size(); i++){if (s[i] == '(' || s[i] == '[' || s[i] == '{'){v.push(s[i]);}else if (s[i] == ')' || s[i] == ']' || s[i] == '}'){if (v.empty()) { return false; }switch (s[i]){case ')':{if (v.top() == '('){v.pop();}elsereturn false;break;}case ']':{if (v.top() == '['){v.pop(); }elsereturn false;break;}case '}':{if (v.top() == '{'){v.pop();}elsereturn false;break;}}}}if (v.empty())return true;elsereturn false;}
};

题目

问题描述

现在，有一行括号序列，请你检查这行括号是否配对。

输入

第一行输入一个数N

输出

每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No

样例输入 复制

3
[(])
(])
([[]()])

样例输出 复制

No
No
Yes

解法二（利用数组）

感觉我好像写复杂了

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
bool f(char a, char b)
{if (( a == '(' && b == ')' )|| (a == '{' && b == '}') || ( a == '[' && b == ']'))return true;elsereturn false;
}
int main()
{char ch[100];int n;cin >> n;while (n--){ch[0] = '1';cin >> &ch[1];int len = strlen(ch);for (int i = 2; i <=len; i++){while(f(ch[i-1],ch[i])==true){for (int j = i - 1; j <=len - 1; j++)  //括号匹配时--覆盖匹配的元素{ch[j] = ch[j + 1];   }ch[len-1] = '\0';  //处理字符串结尾len--;             //数组长度减小if (i == 0){cout << "YES" << endl;break;}for (int j = i - 1; j <=len - 1; j++){ch[j] = ch[j + 1];}ch[len-1] = '\0';   //处理字符串结尾len--;i--;}}if (strlen(ch) == 1)cout << "Yes" << endl;elsecout << "No" << endl;}return 0;
}