LeetCode 算法：有效的括号 c++

原题链接🔗：有效的括号
难度：简单⭐️

题目

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

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”
输出：true

示例 2：

输入：s = “()[]{}”
输出：true

示例 3：

输入：s = “(]”
输出：false

提示：

• 1 <= s.length <= 104
• s 仅由括号 ‘()[]{}’ 组成

栈

数据结构中的栈（Stack）是一种遵循后进先出（Last In First Out，LIFO）原则的线性数据结构。在栈中，数据的添加和删除都发生在栈顶。栈的两个主要操作是：

1. 压栈（Push）：将一个元素添加到栈顶。
2. 弹栈（Pop）：移除栈顶的元素，并返回它。

此外，栈还可能支持以下操作：

• 查看栈顶元素（Peek/Top）：返回栈顶元素，但不从栈中移除它。
• 检查栈是否为空（IsEmpty）：判断栈是否没有任何元素。
• 获取栈的大小（Size）：返回栈中元素的数量。

栈在计算机科学中有着广泛的应用，例如：

• 函数调用和返回的实现：每次函数调用时，其返回地址和局部变量会被压入调用栈。
• 括号匹配问题：使用栈来检查字符串中的括号是否正确闭合。
• 撤销操作（Undo）：在编辑器或绘图软件中，用户的操作可以被压入栈中，以便随时撤销。
• 深度优先搜索（DFS）：在图或树的遍历中，使用栈来存储待访问的节点。

栈的实现可以基于数组或链表。数组实现的栈具有固定的大小，而链表实现的栈则可以动态地增长和收缩。

栈的 C++ 实现示例

以下是使用 C++ 标准模板库（STL）中的 std::stack 容器实现栈的一个简单示例：

#include <iostream>
#include <stack>

int main() {
    std::stack<int> myStack;

    // 压栈操作
    myStack.push(10);
    myStack.push(20);
    myStack.push(30);

    // 查看栈顶元素
    std::cout << "Top element is: " << myStack.top() << std::endl;

    // 弹栈操作
    myStack.pop();
    std::cout << "Top element after one pop is: " << myStack.top() << std::endl;

    // 检查栈是否为空
    if (!myStack.empty()) {
        std::cout << "Stack is not empty." << std::endl;
    }

    // 获取栈的大小
    std::cout << "Size of stack: " << myStack.size() << std::endl;

    return 0;
}

这个示例展示了如何创建一个整数类型的栈，执行压栈和弹栈操作，查看栈顶元素，检查栈是否为空，以及获取栈的大小。

题解

1. 解题思路：

LeetCode 上的 “有效的括号”（Valid Parentheses）问题是一个经典的栈（Stack）应用问题。这个问题要求判断一个字符串中的括号是否正确配对。

• 问题描述： 给定一个字符串 s，判断它是否是有效的括号序列。有效的括号序列需要满足以下条件：

  • 左括号必须有对应的右括号与之配对。
  • 括号必须按照正确的顺序配对。

  括号包括圆括号 ()、方括号 [] 和花括号 {}。

• 解题思路 ：

  • 使用栈结构：栈是一种后进先出（LIFO）的数据结构，非常适合处理配对问题。
  • 遍历字符串：逐个字符遍历字符串 s。
  • 遇到左括号：如果是左括号（(, [, {），则将其推入栈中。
  • 遇到右括号：如果是右括号（), ], }）：
    • 检查栈顶是否有对应的左括号：
      • 如果栈为空或者栈顶元素与当前右括号不匹配，说明括号序列无效，返回 False。
      • 如果匹配，将栈顶元素弹出。
  • 遍历结束：遍历完成后，检查栈是否为空：
    • 如果栈为空，说明所有括号都正确配对，返回 True。
    • 如果栈不为空，说明有未配对的左括号，返回 False。

2. c++ demo：

#include <iostream>
#include <stack>
#include <string>
#include <map>

using namespace std;

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        // 定义括号的映射关系
        map<char, char> brackets = { {')', '('}, {']', '['}, {'}', '{'} };
        for (char c : s) {
            if (c == '(' || c == '[' || c == '{') {
                // 如果是左括号，压入栈中
                st.push(c);
            }
            else {
                // 如果栈为空或者栈顶元素与当前右括号不匹配，返回false
                if (st.empty() || brackets[c] != st.top()) {
                    return false;
                }
                // 匹配则弹出栈顶元素
                st.pop();
            }
        }
        // 如果栈为空，则所有括号都正确配对
        return st.empty();
    }
};

int main() {
    Solution solution;
    // 测试用例
    string test1 = "()";
    string test2 = "()[]{}";
    string test3 = "(]";
    string test4 = "([)]";
    string test5 = "{[()]}()";

    // 执行测试并打印结果
    cout << "Test 1: " << (solution.isValid(test1) ? "True" : "False") << endl;
    cout << "Test 2: " << (solution.isValid(test2) ? "True" : "False") << endl;
    cout << "Test 3: " << (solution.isValid(test3) ? "True" : "False") << endl;
    cout << "Test 4: " << (solution.isValid(test4) ? "True" : "False") << endl;
    cout << "Test 5: " << (solution.isValid(test5) ? "True" : "False") << endl;

    return 0;
}

• 输出结果：

Test 1: True
Test 2: True
Test 3: False
Test 4: False
Test 5: True

3. 代码仓库地址：isValid