Стеки в Python
Создание класса стека с помощью объекта List
Использование list
объект можно создать полностью функциональный универсальный стек с вспомогательными методами , такими как заглядывать и проверять , если стек пуст. Проверьте официальный питон документы для использования list
в качестве Stack
здесь .
#define a stack class
class Stack:
def __init__(self):
self.items = []
#method to check the stack is empty or not
def isEmpty(self):
return self.items == []
#method for pushing an item
def push(self, item):
self.items.append(item)
#method for popping an item
def pop(self):
return self.items.pop()
#check what item is on top of the stack without removing it
def peek(self):
return self.items[-1]
#method to get the size
def size(self):
return len(self.items)
#to view the entire stack
def fullStack(self):
return self.items
Пример выполнения:
stack = Stack()
print('Current stack:', stack.fullStack())
print('Stack empty?:', stack.isEmpty())
print('Pushing integer 1')
stack.push(1)
print('Pushing string "Told you, I am generic stack!"')
stack.push('Told you, I am generic stack!')
print('Pushing integer 3')
stack.push(3)
print('Current stack:', stack.fullStack())
print('Popped item:', stack.pop())
print('Current stack:', stack.fullStack())
print('Stack empty?:', stack.isEmpty())
Выход:
Current stack: []
Stack empty?: True
Pushing integer 1
Pushing string "Told you, I am generic stack!"
Pushing integer 3
Current stack: [1, 'Told you, I am generic stack!', 3]
Popped item: 3
Current stack: [1, 'Told you, I am generic stack!']
Stack empty?: False
Парсинг скобок
Стеки часто используются для разбора. Простая задача синтаксического анализа заключается в проверке соответствия строки скобок.
Например, строка ([])
является соответствие, потому что внешние и внутренние скобки образуют пары. ()<>)
Не соответствует заданному, потому что последний )
не имеет никакого партнера. ([)]
Также не соответствует, потому что пар должен быть либо полностью внутри или снаружи других пар.
def checkParenth(str):
stack = Stack()
pushChars, popChars = "<({[", ">)}]"
for c in str:
if c in pushChars:
stack.push(c)
elif c in popChars:
if stack.isEmpty():
return False
else:
stackTop = stack.pop()
# Checks to see whether the opening bracket matches the closing one
balancingBracket = pushChars[popChars.index(c)]
if stackTop != balancingBracket:
return False
else:
return False
return not stack.isEmpty()