Python栈的顺序存储结构,顺序栈类的实现,以及使用栈判断输入括号是否匹配算法

废话不多说,直接上代码

更多源码分享请关注

小星博博Giteehttps://gitee.com/xiaoxingbobo-personalicon-default.png?t=LA92https://gitee.com/xiaoxingbobo-personal

1、首先添加SqStack顺序栈类

class SqStack:
    # 构造函数
    def __init__(self):
        self.data = []  # 声明空列表,作为栈的存放元素

    # 判断栈是否为空
    def empty(self):
        if len(self.data) == 0:
            return True
        return False

    # 进栈
    def push(self, item):
        self.data.append(item)

    # 出栈
    def pop(self):
        assert not self.empty()  # 判断栈是否为为空
        return self.data.pop()  # pop() 函数用于移除列表中的一个元素(默认最后一个元素),并且返回该元素的值。

    # 取栈顶元素
    def get_top(self):
        assert not self.empty()
        return self.data[-1]  # data[-1]取出倒数第一个数

 2、判断括号是否匹配的算法

实现原理

  1. 遇到左括号先进栈
  2. 遇到右括号时,取出栈顶元素,进行匹配是否时另外一半括号,不是则直接返回false,方法执行完毕
  3. 如果栈顶元素和左括号匹配时,则使栈顶元素出栈,依次进行下一个元素判断
# 导入SqStack
from SqStack import SqStack


def is_match(st):  # 判断表达式的括号是否匹配的算法
    sq = SqStack()  # 创建一个空栈
    i = 0  # 栈的下标
    # while循环栈元素次数
    while i < len(st):
        e = st[i]  # 取出用户输入的元素
        if e == "(" or e == "[" or e == "{":  # 进栈
            sq.push(e)
        else:  # 遇到右括号
            if e == ")":
                if not sq.empty() or sq.get_top() == "(":
                    sq.pop()
                return False
            if e == "]":
                if not sq.empty() or sq.get_top() == "[":
                    sq.pop()
                return False
            if e == "}":
                if not sq.empty() or sq.get_top() == "{":
                    sq.pop()
                return False
        i += 1
    return sq.empty()


def print_info(value):
    if is_match(value):
        print(value + "匹配")
    else:
        print(value + "不匹配")


if __name__ == '__main__':
    ipt = input("输入要判断的括号(只支持英文状态):")
    print_info(ipt)

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>