python数据结构之堆栈

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
#                     _ooOoo_
#                   o8888888o
#                    88" . "88
#                 ( | -  _  - | )
#                     O\ = /O
#                 ____/`---'\____
#                  .' \\| |// `.
#                 / \\|||:|||// \
#               / _|||||-:- |||||- \
#                | | \\\ - /// | |
#              | \_| ''\---/'' | _/ |
#               \ .-\__ `-` ___/-. /
#            ___`. .' /--.--\ `. . __
#         ."" '< `.___\_<|>_/___.' >'"".
#       | | : `- \`.;`\  _ /`;.`/ - ` : | |
#          \ \ `-. \_ __\ /__ _/ .-` / /
#      ==`-.____`-.___\_____/___.-`____.-'==
#                     `=---='
'''
@Project ：pythonalgorithms 
@File ：stackdatastructure.py
@Author ：不胜人生一场醉
@Date ：2021/7/15 16:07 
'''


class Stack(object):
    # 堆栈初始化
    def __init__(self):
        # 用list存储栈元素
        self.items = []

    # 判断是否为空
    def isempty(self):
        return self.items == []

    # 加入元素
    def push(self, item):
        self.items.append(item)

    # 弹出元素
    def pop(self):
        if self.items == []:
            raise IndexError("Stack top is not exist!")
        return self.items.pop()

    # 返回栈顶元素
    def peek(self):
        if self.items == []:
            raise IndexError("Stack top is not exist!")
        return self.items[- 1]

    # 返回栈的大小
    def size(self):
        return len(self.items)

    def __str__(self):
        return str(self.items)


def check_flag(text):
    stack = Stack()
    left_flag = "([{<"
    right_flag = ")]}>"
    flags = {")": "(", "]": "[", "}": "{", ">": "<"}
    for i in text:
        # 左右都是成对出现的，但'需要特殊判断
        if i in ["'"] and stack.peek() not in ["'"]:
            stack.push(i)
        elif i in ["'"] and stack.peek() in ["'"]:
            stack.pop()
            return True

        # 如果为左边的符号，则把左边的符号放到堆栈中
        if i in left_flag:
            stack.push(i)
        # 如果为右边的符号
        elif i in right_flag:
            # 如果堆栈为空，返回False
            if stack.isempty():
                return False
            # 如堆栈弹出值不为右边符号的字典值，返回False
            if flags[i] != stack.pop():
                return False
    # 堆栈为空，则表示全部消费完成，所以为True
    if stack.isempty():
        return True
    return False


if __name__ == "__main__":
    stack = Stack()
    # print(stack.pop())
    # IndexError: Stack top is not exist!
    stack.push("hello")
    stack.push("world")
    stack.push("helloworld")
    print(stack)
    print(stack.size())
    print(stack.peek())
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())

    # 一个基于堆栈的样例
    print(check_flag("['d']"))
    print(check_flag("[{12()3<dd>'d'2}]"))
    print(check_flag("[{12(32})]"))
    print(check_flag("[{12'32}']"))

C:\python\pyproject\pythonalgorithms\venv\Scripts\python.exe C:/python/pyproject/pythonalgorithms/stackdatastructure.py
['hello', 'world', 'helloworld']
3
helloworld
helloworld
world
hello
True
True
False
False