在 Python 中检查两个字符串的连接是否平衡
pythonserver side programmingprogramming
假设我们有两个括号序列 s 和 t，它们仅包含这两个字符 '(' 和 ')'。我们必须检查 s 和 t 的连接字符串是否平衡。连接可以通过 s | t 或 t | 来完成s。
因此，如果输入为 s = "()()))", t = "()(()("，则输出将为 True，因为如果我们连接 t | s，则将得到 "()(()(()()))"，这是平衡的。
为了解决这个问题，我们将遵循以下步骤 −
- 定义一个函数 is_balanced_parenthesis() 。这将采用字符串
- stack := a new list
- 对于范围从 0 到字符串大小的 i，执行
- 如果 string[i] 与 '(' 相同，则
- 将 string[i] 推入堆栈
- 否则，
- 如果堆栈为空，则
- 返回 False
- 否则，
- 从堆栈弹出
- 如果堆栈为空，则
- 如果 string[i] 与 '(' 相同，则
- 如果堆栈不为空，则
- 返回 False
- 返回 True
- 从主方法执行以下操作 −
- 如果 is_balanced_parenthesis(s + t) 为真，则
- 返回 True
- 返回 is_balanced_parenthesis(t + s)
让我们看看以下实现以获得更好的理解 −
示例
def is_balanced_parenthesis(string):
stack = []
for i in range(len(string)):
if string[i] == '(':
stack.append(string[i])
else:
if len(stack) == 0:
return False
else:
stack.pop()
if len(stack) > 0:
return False
return True
def solve(s, t):
if is_balanced_parenthesis(s + t):
return True
return is_balanced_parenthesis(t + s)
s = "()()))"
t = "()(()("
print(solve(s, t))
输入
"()()))", "()(()("
输出
True
