题目描述

给定一个只包含以下两种字符的字符串：'('和')'请判断这个字符串是否是一个合法的括号序列。一个合法的括号序列必须满足以下条件：

1. 左括号必须有对应的右括号。
2. 每个右括号必须在其对应的左括号之后出现。
3. 括号必须是成对的，且嵌套的括号必须是有效的。

例如，字符串 "()"和"(())是合法的括号序列，而 "(()" 和 "(((" 则不是。

输入

输入包含一个字符串 $s$，长度 $|s|$ $(2 \leq |s| \leq 10^5)$，字符串只包含以下字符：'(', ')'

输出

如果字符串是合法的括号序列，输出 "Yes"；否则，输出 "No".

示例

输入

(())

输出

Yes

输入

(((())

输出

No

【栈1】合法括号判断

前言

栈的定义

栈（Stack）是一种常见的线性数据结构，其特点是遵循“后进先出”（LIFO，Last In First Out）原则。也就是说，最后被压入栈中的元素会最先被弹出。

栈的基本操作包括：

1. 入栈（Push）：将一个元素添加到栈的顶部。
2. 出栈（Pop）：移除栈顶元素，并返回该元素。
3. 查看栈顶元素（Peek 或 Top）：返回栈顶的元素，但不移除它。
4. 判断栈是否为空（IsEmpty）：检查栈是否没有任何元素。

栈的特性：

• LIFO原则：栈中的元素是从栈顶添加和移除的，栈顶的元素是最先被访问的。
• 只能在一端操作：栈的操作只能在栈顶进行。

栈的应用：

1. 函数调用管理：在程序运行过程中，函数调用的顺序和返回都由栈来管理。每次函数调用时，程序会把当前函数的信息压入栈中，函数执行完成后会从栈中弹出，返回到调用函数的位置。
2. 表达式求值：栈常用于数学表达式的求值，尤其是处理括号匹配和运算符优先级时。
3. 浏览器的历史记录：浏览器在你浏览网页时会将每个页面的链接压入栈中，这样你按回退按钮时就可以弹出最近访问的页面。

栈的实现：

栈可以通过数组或链表来实现。常见的实现方式有：

• 数组实现：使用数组来存储栈的元素，栈顶指针记录栈顶元素的位置。
• 链表实现：通过链表的头结点来表示栈顶，头结点指向栈顶元素。

栈的操作时间复杂度通常是 O(1)，即每次操作的时间是常数级别的，因为它只涉及栈顶元素。

示例：

例如，我们有一个栈，初始为空。我们依次执行以下操作：

• 入栈 1 -> 栈变为 [1]
• 入栈 2 -> 栈变为 [1, 2]
• 入栈 3 -> 栈变为 [1, 2, 3]
• 出栈 -> 弹出栈顶元素 3，栈变为 [1, 2]
• 查看栈顶元素 -> 返回 2，但栈不变。

通过栈的结构和操作，程序可以方便地处理许多递归或后进先出的任务。

栈的演示图：

题解

题面分析

给定一个只包含以下两种字符的字符串：'(' 和 ')'，请判断这个字符串是否是一个合法的括号序列。一个合法的括号序列必须满足以下条件：

1. 左括号必须有对应的右括号。
2. 每个右括号必须在其对应的左括号之后出现。
3. 括号必须是成对的，且嵌套的括号必须是有效的。

例如，字符串 "()" 和 "(())" 是合法的括号序列，而 "(()" 和 "(((" 则不是。

思路分析

这道题的核心是判断一个字符串是否是合法的括号序列。一个合法的括号序列应该满足以下条件：

1. 在遍历过程中，当前的左括号 ( 必须有一个对应的右括号 ) 与其匹配。
2. 右括号 ) 不能先于左括号 ( 出现。
3. 左括号和右括号必须成对出现。

我们可以利用栈来判断括号是否匹配。具体步骤如下：

• 当我们遇到左括号 ( 时，就将其压入栈中。
• 当我们遇到右括号 ) 时，我们从栈中弹出一个元素，表示匹配到一个左括号。
• 如果栈为空时遇到右括号，或者遍历完成后栈中还有剩余的左括号，说明括号不匹配。

步骤

1. 初始化栈：创建一个空栈。

stack = []  # 创建一个空栈

2. 遍历字符串：逐个遍历字符串中的每个字符：
   • 如果字符是左括号 (，将其压入栈。
   • 如果字符是右括号 )，从栈中弹出一个元素，表示该右括号与栈顶的左括号匹配。如果此时栈为空，说明没有匹配的左括号，返回 No。

for char in s:
    if char == '(':  # 遇到左括号，压入栈
        stack.append(char)
    elif char == ')':  # 遇到右括号
        if not stack:  # 如果栈为空，说明没有匹配的左括号
            print("No")
            exit(0)  # 立即结束程序
        stack.pop()  # 弹出栈顶元素，匹配对应的左括号

3. 最终检查栈：遍历结束后，检查栈是否为空。如果栈为空，说明所有的左括号都有对应的右括号，字符串是合法的；如果栈不为空，说明还有未匹配的左括号，字符串不合法。

if not stack:  # 如果栈为空，说明所有的左括号都有匹配
    print("Yes")  # 输出 Yes
else:
    print("No")  # 如果栈不为空，输出 No

代码

# 读取输入
s = input().strip()  # 输入括号字符串
stack = []  # 创建一个栈

# 遍历字符串
for char in s:
    if char == '(':  # 遇到左括号，将其压入栈
        stack.append(char)
    elif char == ')':  # 遇到右括号
        if not stack:  # 如果栈为空，说明没有匹配的左括号
            print("No")
            exit(0)  # 立即结束程序
        stack.pop()  # 弹出栈顶元素，匹配对应的左括号

# 如果栈为空，说明所有的左括号都有匹配
if not stack:
    print("Yes")  # 如果栈为空，输出 Yes
else:
    print("No")  # 如果栈不为空，输出 No

代码解释

1. 栈的初始化：我们使用一个空列表 stack = [] 来模拟栈的功能。
2. 遍历字符串：通过 for char in s: 遍历字符串中的每个字符：
   • 当遇到左括号 ( 时，将其压入栈，表示待匹配的括号。
   • 当遇到右括号 ) 时，检查栈是否为空。如果栈为空，说明没有匹配的左括号，直接返回 No。如果栈不为空，则弹出栈顶的左括号，表示匹配成功。
3. 最终判断：遍历结束后，若栈为空，表示所有的括号配对成功，返回 Yes；若栈不为空，说明有未匹配的左括号，返回 No。