第十五届蓝桥杯大赛 国赛 pb组F题【括号与字母】(15分) 栈的应用

试题F:括号与字母

【问题描述】

        给定一个仅包含小写字母和括号的字符串 S ，保证括号可以两两匹配。 给出 Q 组询问，每组询问给出一个小写字母 ci 和一个数 xi ，询问 S 中有 多少对匹配的括号之间有不少于 xi 个 ci 。

【输入格式】

       输入的第一行包含一个字符串 S 。 第二行包含一个整数 Q 。 接下来 Q 行，每行包含一个小写字母 ci 和一个整数 xi 表示一组询问，用 一个空格分隔。

【输出格式】

        输出 Q 行，每行包含一个整数，依次表示每个询问的答案。

【样例输入】

((a)()((b)((c))))

3

a 2

b 1

c 1

【样例输出】

0

3

4

【评测用例规模与约定】

       对于 40% 的评测用例，|S |, Q ≤ 5000 ； 对于 70% 的评测用例，|S | ≤ 100000 ； 对于所有评测用例，1 ≤ |S | ≤ 106 ，1 ≤ Q ≤ 100000 ，0 ≤ xi < 106 。其中 |S | 表示 S 的长度。

分析问题：

       仔细读题，保证给的s中括号都两两匹配，那么这道题就相当于是在考察入栈和出栈的问题了，这里我们需要定义一个符号栈和一个字母栈。

• 符号栈：专门用来存储左括号，遇见左括号则入栈，遇见右括号则栈顶的左括号出栈。并且对加入的左括号所包含的字母个数做标记，记录出栈前的左括号和右括号之间有几个字母，最后可以通过字符串切割来找到这个括号内的字母。
• 字母栈：遇见字母则入栈，不需要出栈。用于储存字母。

代码实现：

s=str(input()) # 输入s
s0="abcdefghijklmnopqrstuvwxyz" # 一会判断字母要用
q=int(input())  # 输入询问次数q
for i in range(q): # q次循环，每次询问都有一个输出值
    s1,b1=map(str,input().split())  # 输入要询问的字母和被包括的个数
    b=int(b1)  # 转次数为int型
    v=s.count(s1) 
    if v<b:print(0)  # 此时总个数都小于要询问的个数b，一定没有符合题意的 返回0
    else:
        re=0 # 记录个数
        stick_1=[] # 符号栈
        stick_2=[] # 字母栈
        for j in s: # 遍历s
            if j=="(":  #遇见左括号则入栈
                stick_1.append([j,0]) # 后面的0 用于标记这个左括号与对应的右括号之间有几个字母
            elif j in s0:  # 如果是字母，则入字母栈
                stick_2.append(j)
                for w in range(len(stick_1)): 
                    stick_1[w][-1]+=1 # 对于所有的左括号对应的标记值，都加1，说明他们与对应的右括号之间多了一个字母
            else: # 否则则是右括号
                k_1,st=stick_1.pop() # 遇见右括号，则从符号栈出栈一个左括号
                if st==0: continue # 说明左括号右括号之间没有元素，直接跳
                ve=stick_2[-1:-st-1:-1] # 否则说明之间有元素，则找到这些元素
                if ve.count(s1)>=b:# 判断ve中要查询的字母个数是否合题意
                    re+=1 # 标记的个数+1
        print(re) # 对于每次询问都返回 res

总结：

以下是对这段代码的详细解释：

• s = str(input())：获取用户输入的字符串 s。
• s0 = "abcdefghijklmnopqrstuvwxyz"：定义了所有小写字母的字符串，用于后续判断字母。
• q = int(input())：获取询问的次数。
• 然后进入 q 次循环：

• s1, b1 = map(str, input().split())：分别获取要询问的字母和期望的包含个数，将 b1 转换为整数类型。
• v = s.count(s1)：计算字符串 s 中该字母出现的总次数。如果总次数小于期望个数，直接输出 0。
• 否则，进行复杂的处理：

• re = 0 用于记录符合条件的个数。
• stick_1 是符号栈，stick_2 是字母栈。
• 遍历字符串 s：

• 遇到左括号，将其及初始标记值 0 入栈。
• 遇到字母，入字母栈，并更新符号栈中每个左括号对应的标记值，表示它们之间多了一个字母。
• 遇到右括号，弹出符号栈中的一个左括号和标记值。如果标记值为 0，则直接跳过；否则，找到左括号和右括号之间的元素，判断其中要查询的字母个数是否满足条件，如果满足则增加标记个数 re。

• 最后输出每次询问对应的 re。

       总的来说，这段代码主要是通过栈的操作来处理字符串中括号内的子串，并判断其中特定字母的出现次数是否满足要求。

对于这道题的考点和反思如下:

考查内容：

1. 对字符串的处理和操作能力，包括字符的统计、遍历等。
2. 栈这种数据结构的运用，通过栈来处理括号内的内容和计数。
3. 逻辑思维和问题分析解决能力，需要仔细思考如何在复杂的条件下准确判断符合要求的情况。

学会的内容：

1. 更加深入地掌握了字符串处理的技巧和方法。
2. 熟悉了栈的实际应用场景，以及如何通过栈来解决特定问题。
3. 提升了面对复杂逻辑问题时设计算法和代码实现的能力。

反思：

1. 在处理复杂逻辑时，要更加仔细地设计算法和流程，避免遗漏特殊情况。
2. 对于数据结构的运用要更加灵活，根据具体问题选择合适的数据结构来优化解决方案。
3. 编写代码时要注意代码的可读性和可维护性，以便后续的理解和修改。同时要充分考虑代码的效率和性能。

      总之,这道题放在15分的位置，并不算是难题，主要还是考察对栈的应用熟练程度是否到位。 相关栈的篇章：栈的理解与应用

“甲之蜜糖，乙之砒霜。” ——《曼陀罗》