Стеки в 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()