讲解LeetCode第20题：有效的括号（完整代码）

📱博主会继续更新关于LeetCode的习题

😽如果你觉得内容还不错，请多多点赞​

🐶如果你觉得对你有帮助，请多多收藏（防止以后找不到了）

👨‍👩‍👧‍👦如果你想学习更多的LeetCode习题，请多多关注博主。

题目介绍

方法：栈​​

完整代码展示

//有效的括号——栈
#include<iostream>
#include<string>
#include<unordered_map>
#include<stack>
using namespace std;

class Solution
{
public:
    bool isValid(string s)
    {
        int n = s.size();
        if (n % 2 == 1) 
        {
            return false;
        }

        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'},
        };
        stack<char> stk;

        for (char ch : s)
        {
            if (pairs.count(ch))
            {
                if (stk.empty() || stk.top() != pairs[ch])
                {
                    return false;
                }
                stk.pop();
            } 
            else 
            {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};

int main()
{
	string test = "([]{})";
    
	Solution judge;
	bool result = judge.isValid(test);

	if (result)
	{
		cout << "test是有效括号" << endl;
	}
	else
	{
		cout <<"test不是有效括号" << endl;
	}
    
	return 0;
}

核心原理演示

代码片段解释

片段一：

 unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'},
        };

unordered_map是C++标准库中的一个容器，它存储的是键值对（key-value pairs）

unordered_map<char, char> pairs这行代码创建了一个unordered_map对象pairs

pairs是一个unordered_map<char, char>，意味着它存储的键和值都是字符类型。

= { {')', '('}, {']', '['}, {'}', '{'} };表示对象pairs初始化了三个键值对

• ‘)’ 作为键，对应值 ‘(’
• ‘]’ 作为键，对应值 ‘[’
• ‘}’ 作为键，对应值 ‘{’

这些键值对表示的是右括号到左括号的映射关系。

即，pairs被定义为一个从右括号),],}到对应左括号(,[,{的映射。

这样当我们遇到一个右括号时，可以快速地查找它应该匹配的左括号。

片段二：

pairs.count(ch)
pairs[ch]

count是unordered_map的一个成员函数，他接受一个键作为参数，并返回该键在unordered_map中出现的次数。对于unordered_map来说一个键：

• 要么出现0次，即不存在。
• 要么出现1次，因为unordered_map不允许有重复的键。

pairs[ch]用于访问一个名为pairs的unordered_map中与键ch相关联的值。

片段三：

stk.empty()
stk.top()
stk.pop()
stk.push(ch)

stk.empty()是一个成员函数，用于检查栈是否为空。

• 如果栈为空，返回 true；
• 如果栈不为空，返回 false。

stk.top()是一个成员函数，用于返回栈顶元素的引用。

stk.pop()是一个成员函数，用于移除栈顶元素。（它不接受任何参数，也不返回任何值）

stk.push(ch)是一个成员函数，用于将元素 ch 压入栈顶。