时间戳

首页 > 解决方案 > 查找以列表形式给出的匹配圆括号对

python - 查找以列表形式给出的匹配圆括号对

问题描述

我有一个元组列表，如下所示：

[(' ( ', 0),
 (' ) ', 4),
 (' ( ', 5),
 (' ( ', 6),
 (' ) ', 10),
 (' ) ', 11)]

我需要得到一个看起来像这样的列表：

[(​ 0 ​ , ​ 4 ​ ), (​ 5 ​ , ​ 11​ ), (​ 6 ​ , ​ 10​ )]

主要任务是在给定的元组列表中找到所有圆括号对（括号）。细绳。

标签： pythonlisttuples

解决方案

配对括号的惯用方法是使用堆栈数据结构。

每当你看到一个左括号，你就将值压入堆栈，每当你看到一个右括号，你就从堆栈中弹出一个值以匹配它：

brackets = [(' ( ', 0), (' ) ', 4), (' ( ', 5), (' ( ', 6), (' ) ', 10), (' ) ', 11)]

stack = []
solution = []
for bracket, num in brackets:
    if '(' in bracket:
        stack.append((bracket, num))
    elif ')' in bracket:
        solution.append((stack.pop()[1], num))

print(solution)

这是由于堆栈和括号的LIFO （后进先出）性质。

含义 - 右括号应该关闭遇到的最后一个左括号。

推荐阅读