手机版
你好,游客 登录 注册
背景:
阅读新闻

使用Python的栈实现括号匹配算法

[日期:2019-11-17] 来源:Linux社区  作者:wx5a4c600866558 [字体: ]

利用Python列表实现一个栈的结构,再使用栈实现括号匹配的算法,所谓的括号匹配是指在编程语言中,括号是成对出现的,最先出现的左括号,对应于最后的右括号,后出现的左括号对应于最新右括号,符合栈的特征

写一个栈的类:stack.py

class Stack:
    def __init__(self):
        self.items = []

    def is_Empty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(items)-1]
    def size(self):
        return len(self.items)

实现括号匹配的算法程序:

from stack import Stack
def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol == "(":
            s.push(symbol)
        elif symbol == ")":
            if s.is_Empty():
                balanced = False
            else:
                s.pop()

        index += 1
    if balanced and s.is_Empty():
        return True
    else:
        return False

print(parChecker("(((2356)))"))

输出结果:
True
再测试

print(parChecker("(()))"))

输出结果False

扩展

能够匹配多种括号,{},[]
只需要小小的改动代码:

from stack import Stack

def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol in "({[":
            s.push(symbol)
        elif symbol in ")}]":
            if s.is_Empty():
                balanced = False
            else:
                s.pop()

        index += 1
    if balanced and s.is_Empty():
        return True
    else:
        return False

print(parChecker("[(({fdf}))]"))
linux
相关资讯       Python算法 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款