蓝桥杯正则问题

2026-05-04 暂无评论

全文共 506 字，阅读约 2 分钟

题目描述

考虑一种简单的正则表达式：只由 x ( ) | 组成的正则表达式。求这个正则表达式能接受的最长字符串的长度。

例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是 xxxxxx，长度是 6。

输入：一个由 x ( ) | 组成的正则表达式，长度不超过 100，保证合法。

输出：能接受的最长字符串的长度。

解题方法：栈模拟

核心思路是用栈来模拟正则表达式的求值过程。正则中的 | 表示"或"（取较长的那条路），() 表示分组，x 串联表示连接。

把 x 的连续个数压栈，| 和 ( 也作为标记入栈。遇到 ) 时出栈直到 (，收集所有 | 分隔的数字，取最大值，然后重新压入对应数量的 x。

最后处理栈中残余的 | 分隔，取最大值即为答案。

算法思路

遍历每个字符，用栈维护状态
x → 栈顶数字 +1（连续 x 计数），或者栈为空 / 栈顶不是数字 → 压入 1
| → 作为分隔标记入栈
( → 作为标记入栈
) → 出栈直到 (：收集过程中以 | 分隔的所有数字，取最大值，将对应数量的 x 重新压回栈
扫描结束后，栈中剩下的 | 分隔的各个数字取最大值

代码解析

s = input().strip()
stk = []

for ch in s:
    if ch == ')':
        # 收集当前括号组内的所有选项
        nums = []
        cur = 0
        while True:
            x = stk.pop()
            if x == 'x':
                cur += 1
            elif x == '|' or x == '(':
                nums.append(cur)
                cur = 0
                if x == '(':
                    break
        # 取最长选项，压回栈
        stk.extend(list('x' * max(nums)))
    else:
        stk.append(ch)

# 处理栈中剩余的 | 分隔
nums = []
cur = 0
for ch in stk:
    if ch == 'x':
        cur += 1
    elif ch == '|':
        nums.append(cur)
        cur = 0
nums.append(cur)

print(max(nums))

代码要点

栈的优势：用栈天然支持括号嵌套，遇到 ) 时栈顶到 ( 之间的内容就是当前分组
| 的处理：遇到 | 时先把当前累计的 cur 存起来，然后归零继续计数。最后 nums 里存的就是该组内所有 | 分支的 x 数量
合并逻辑：取 max 就是 | 的语义——选最长的那个分支