Python使用list實作:順序棧(array_stack)檢查括号

'''
Python使用list實作:順序棧(array_stack)檢查括号

參考：《Python資料結構之棧詳解》
https://www.jb51.net/article/239930.htm


基本操作：
1. __itit__(): 初始化棧
建立一個空棧
2. size(): 求取并傳回棧中所含元素的個數 n
若棧為空，則傳回整數0
3. isempty(): 判斷是否為空棧
判斷棧中是否存儲元素
4. push(data): 入棧
将元素 data 插入棧頂
5. pop(): 出棧
删除并傳回棧頂元素
4. peek(): 取棧頂元素
傳回棧頂元素值，但并不删除元素
'''

class array_stack:
    def __init__(self, max_size=10):
        self.__max_size = max_size
        self.__stack = self.__max_size * [None]
        self.__top = -1

    def size(self):
        return self.__top + 1
    def isempty(self):
        return self.size() == 0
    def isfully(self):
        return self.size() == self.__max_size
    def __resize(self):
        new_size = 2 * self.__max_size
        new_stack = [None] * new_size
        for i in range(self.size()):
            new_stack[i] = self.__stack[i]
        self.__stack = new_stack
        self.__max_size = new_size
    def push(self, data):
        if self.isfully():
            self.__resize()
        self.__top += 1
        self.__stack[self.__top] = data
    def pop(self):
        if self.isempty():
            raise IndexError('Stack Underflow!')
        else:
            result = self.__stack[self.__top]
            self.__top -= 1
            return result
    def peek(self):
        if self.isempty():
            raise IndexError('Stack Underflow!')
        else:
            return self.__stack[self.__top]


# 初始化一個最大長度為4的棧
s = array_stack(4)
print('棧空?', s.isempty())
for i in range(4):
    print('入棧元素：', i)
    s.push(i)
print('棧滿?', s.isfully())

print('棧頂元素：', s.peek())
print('棧長度為：', s.size())
while not s.isempty():
    print('出棧元素：', s.pop())

print('--------------------------------')
'''
假設表達式中允許包含3種括号()[]{},其嵌套順序是任意的.
例如：
{()[()]}，[{({})}]這樣的格式是正确的.
[。),[()),(()}這樣的格式是不正确的.
編寫一個函數，判斷一個表達式字元串，括号比對是否正确
'''

left=list('([{')
right=list(')]}')

op=list('{()[()]}')
tip=[' ']*len(op)

ok=True
stack = array_stack(len(op))
for i,it in enumerate(op):
    if it in left:
        stack.push(it)
    elif it in right:
        if stack.size()==0:
            print(f'err：{it}缺少左括弧')
            tip[i]='↑'
            print(''.join(op))
            print(''.join(tip))
            ok = False
            break
        cl = stack.pop()
        if left.index(cl)!=right.index(it):
            print(f"err：'{cl}'與'{it}',左右括弧不比對")
            tip[i]='↑'
            print(''.join(op))
            print(''.join(tip))
            ok = False
            break

if ok:
    if stack.size() == 0:
        print('ok')
    else:
        s=''
        while not stack.isempty():
            s+=f'{stack.pop()}'

        print(f"err：'{s}',缺少右括弧")