ubuntuusers.de

NIL = ()


def create_stack():
    """
    Creates an empty stack.
    
    >>> create_stack()
    ()
    """
    return NIL


def push(stack, value):
    """
    Pushes given `value` to `stack` and returns the stack with that value on
    top.
    
    >>> push(create_stack(), 42)
    ((), 42)
    """
    return (stack, value)


def is_empty(stack):
    """
    Return `True` if given `stack` is empty, `False` otherwise.
    
    >>> is_empty(create_stack())
    True
    >>> is_empty(push(create_stack(), 23))
    False
    """
    return stack == NIL


def pop(stack):
    """
    Pop top of given `stack` and return a tuple with the stack and the popped
    value.
    
    Raises `ValueError` when trying to `pop()` from an empty stack.
    
    >>> pop(create_stack())
    Traceback (most recent call last):
      ...
    ValueError: Stack is empty
    >>> stack, value = pop(push(create_stack(), 4711))
    >>> value
    4711
    """
    if is_empty(stack):
        raise ValueError("Stack is empty")
    return stack


def insert_at_bottom(stack, value):
    """
    Return stack with the given `value` inserted at the bottom.
    
    >>> stack = insert_at_bottom(create_stack(), 42)
    >>> stack
    ((), 42)
    >>> stack = insert_at_bottom(stack, 23)
    >>> stack
    (((), 23), 42)
    >>> stack = insert_at_bottom(stack, 4711)
    >>> stack
    ((((), 4711), 23), 42)
    """
    if is_empty(stack):
        return push(stack, value)
    
    stack, temporary = pop(stack)
    stack = insert_at_bottom(stack, value)
    return push(stack, temporary)


def reverse(stack):
    """
    Returns a reversed stack.
    
    >>> reverse(create_stack())
    ()
    >>> reverse((((), True), False))
    (((), False), True)
    >>> reverse(((((), 4711), 23), 42))
    ((((), 42), 23), 4711)
    """
    if is_empty(stack):
        return stack

    stack, value = pop(stack)
    return insert_at_bottom(reverse(stack), value)

class Stack:
    def __init__(self):
        self.items = []
    
    def __len__(self):
        return len(self.items)
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        self.items.pop()
    
    def insert_at_bottom(self, item):
        self.items.insert(0, item)
    
    def reverse(self):
        self.items.reverse()