Stack

Fundamentals

Implementation

  • I will implement a stack with the help of the dynamic array I built before

Dynamic Array Code

class Array:
    def __init__(self, arr=None, capacity=10):
        if isinstance(arr, list):
            self._data = arr[:]
            self._size = len(arr)
            return
        self._data = [None] * capacity
        self._size = 0

    def get_size(self):
        return self._size

    def get_capacity(self):
        return len(self._data)

    def is_empty(self):
        return self._size == 0

    def add_last(self, e):
        self.add(self._size, e)

    def add_first(self, e):
        self.add(0, e)

    def add(self, index, e):
        """delete from back to front"""
        if not 0 <= index <= self._size:
            raise ValueError(
                'add failed. Require index >= 0 and index <= array sise.')
        if self._size == len(self._data):
            if self._size == 0:
                self._resize(1)
            else:
                self._resize(2 * len(self._data))
        for i in range(self._size - 1, index - 1, -1):
            self._data[i + 1] = self._data[i]
        self._data[index] = e
        self._size += 1

    def get(self, index):
        if not 0 <= index < self._size:
            raise ValueError('get failed. Index is illegal.')
        return self._data[index]

    def get_max(self):
        res = max(self._data[:self.get_size()])
        return res

    def get_max_index(self):
        return self.find_index(self.get_max())

    def get_last(self):
        return self.get(self._size - 1)

    def get_first(self):
        return self.get(0)

    def set(self, index, e):
        if not 0 <= index < self._size:
            raise ValueError('set failed. Index is illegal.')
        self._data[index] = e

    def contains(self, e):
        for i in range(self._size):
            if self._data[i] == e:
                return True
        return False

    def find_index(self, e):
        for i in range(self._size-1,-1,-1):
            if self._data[i] == e:
                return i
        return -1

    def remove(self, index):
        if not 0 <= index < self._size:
            raise ValueError('remove failed. Index is illegal.')
        ret = self._data[index]
        for i in range(index + 1, self._size):
            self._data[i - 1] = self._data[i]
        self._size -= 1
        # if len(self._data) = 1,len(self._data) // 2=0 not valid
        if (self._size == len(self._data) // 4 and len(self._data) // 2 != 0):
            self._resize(len(self._data) // 2)
        return ret

    def remove_first(self):
        return self.remove(0)

    def remove_last(self):
        return self.remove(self._size - 1)

    def remove_max(self):
        return self.remove(self.get_max_index())

    def peek_max(self):
        return self._data[self.get_max_index()]

    def remove_element(self, e):
        index = self.find_index(e)
        if index != -1:
            self.remove(index)

    def _resize(self, new_capacity):
        new_data = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[i]
        self._data = new_data

    def swap(self, i, j):
        if i < 0 or i >= self._size or j < 0 or j >= self._size:
            raise ValueError('Index is illegal.')
        self._data[i], self._data[j] = self._data[j], self._data[i]

    def __str__(self):
        return str('Array : {}, capacity: {}'.format(self._data[:self._size], self.get_capacity()))

    def __repr__(self):
        return self.__str__()

arr = Array()
arr.add_last(0)
arr.add_last(1)
arr.add_last(-1)
arr.add_last(4)
arr.add_last(5)
arr.add_last(4)
print(arr._data)
print(arr.get_max())
print(arr.find_index(4))

[0, 1, -1, 4, 5, 4, None, None, None, None] 5 5

Stack Code

class ArrayStack:
    """
    implement stack with dynamic array
    """
    def __init__(self, capacity = 0):
        """
        initialize stack with a dynamic array of the same capacity
        """
        self._array = Array(capacity=capacity)

    def get_size(self):
        """
        get the stack size
        """
        return self._array.get_size()

    def is_empty(self):
        """
        check if the current stack is empty
        """
        return self._array.is_empty()

    def push(self, ele):
        """
        push an element to the top of the stack
        """
        self._array.add_last(ele)

    def pop(self):
        """
        pop out the element at the top
        """
        res = self._array.remove_last()
        return res

    def peek(self):
        """
        check what's the element at the top
        """
        return self._array.get_last()

def is_valid(input_str):
    left_ = set(['(', '[', '{'])
    hash_ = {
        ')': '(',
        ']': '[',
        '}': '{',
    }
    stack = ArrayStack()
    for ch in input_str:
        if ch in left_:
            stack.push(ch)
        else:
            if stack.get_size() == 0 or hash_[ch] != stack.pop():
                return False
    return stack.is_empty()

input_str1 = '[{(())}]'
print(is_valid(input_str1))

input_str1 = '[{(())})'
print(is_valid(input_str1))

True False