Python使用連結清單實作:鍊式棧(link_stack)檢查括号

'''
Python使用連結清單實作:鍊式棧(link_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 Node:
    def __init__(self, data):
        self.data = data
        self.next = None
    def __str__(self):
        return str(self.data)

class link_stack:
    def __init__(self):
        self.top = None
        self.length = 0

    def size(self):
        return self.length
    def isempty(self):
        return self.length == 0
    def push(self, data):
        p = Node(data)
        p.next = self.top
        self.top = p
        self.length += 1
    def pop(self):
        if self.isempty():
            raise IndexError("Stack Underflow!")
        ele = self.top.data
        self.top = self.top.next
        self.length -= 1
        return ele
    def peek(self):
        if self.isempty():
            raise IndexError("Stack Underflow!")
        return self.top.data


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

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 = link_stack()
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}',缺少右括弧")