算法与Python

算法与Python 知识量:10 - 40 - 100

5.3 合法的括号><

问题- 5.3.1 -

小源学校的计算机课正在学习racket编程语言,这门语言是函数式编程语言。所谓函数式编程,就是几乎所有的语句都是通过函数来完成的,例如在racket里没有循环,循环是通过递归调用函数来实现的,也就是说,代码里面充满了括号。老师每次在判作业的时候,都发现同学对于括号的运用没有掌握好,总是会有左右括号不匹配的问题。

问题求解- 5.3.2 -

解决括号匹配问题的一个常见方法是使用栈数据结构。当遇到左括号时,将其压入栈中;当遇到右括号时,检查栈顶的左括号是否与之匹配。如果匹配,则从栈中弹出该左括号;否则,说明括号不匹配。

以下是一个使用Python实现的算法:

def check_matching_brackets(s):  
    stack = []  
    mapping = {")": "(", "}": "{", "]": "["}  
  
    for char in s:  
        if char in mapping:  
            top = stack.pop() if stack else '#'  
            if mapping[char] != top:  
                return False  
        else:  
            stack.append(char)  
  
    return not stack

这个函数接受一个字符串s作为输入,其中包含要检查的括号序列。函数使用一个栈来跟踪遇到的左括号,并使用一个映射来检查右括号是否与栈顶的左括号匹配。如果遇到右括号并且它与栈顶的左括号不匹配,函数返回False。如果遍历完整个字符串后栈为空,则所有括号都匹配,函数返回True;否则,返回False。

可以使用以下代码来测试该函数:

s = "{(hello)}"  
print(check_matching_brackets(s))  # 输出: True  
  
s = "{(hello"  
print(check_matching_brackets(s))  # 输出: False

这个算法的时间复杂度是O(n),其中n是字符串的长度。它只遍历字符串一次并使用常数额外空间来维护栈。