要解决具有嵌套圆括号的问题,可以使用栈数据结构来跟踪圆括号的嵌套层级。以下是一个示例代码来验证一个字符串中的圆括号是否具有正确的嵌套结构:
def check_parentheses(expression):
stack = []
for char in expression:
if char == '(':
stack.append(char)
elif char == ')':
if len(stack) == 0 or stack[-1] != '(':
return False
stack.pop()
return len(stack) == 0
# 测试示例
expression1 = "((2 + 3) * (4 - 5))"
print(check_parentheses(expression1)) # 输出: True
expression2 = "(3 + 4) * (5 - 6))"
print(check_parentheses(expression2)) # 输出: False
expression3 = "((1 + 2) * (3 - 4)"
print(check_parentheses(expression3)) # 输出: False
在上述代码中,我们使用一个列表作为栈来跟踪圆括号的嵌套层级。当遇到左括号时,我们将其添加到栈中;当遇到右括号时,我们检查栈顶元素是否为左括号,并将其从栈中弹出。如果右括号的数量大于左括号的数量或者栈为空时,说明圆括号的嵌套结构不正确。最后,如果栈为空,表示所有的圆括号都正确地匹配了。
这个方法的时间复杂度是O(n),其中n是字符串的长度。