借助Python的栈实现括号匹配算法

发布时间：2021-11-09 10:11:37 所属栏目：PHP教程来源：互联网

导读：利用Python列表实现一个栈的结构，再使用栈实现括号匹配的算法，所谓的括号匹配是指在编程语言中，括号是成对出现的，最先出现的左括号，对应于最后的右括号，后出现的左括号对应于最新右括号，符合栈的特征写一个栈的类：stack.py class Stack: def __init

利用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}))]"))

（编辑：云计算网_泰州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

php批量命名文件技巧	php读取文件内容几种正
php中读取大文件实现方	php打开远程文件的方法