Stack is a widely used set in the field of computer. Stack is a linear set, and access is strictly restricted to a segment, called the top. A stack, for example, is like a stack of washed dishes. Every time you take a new dish, you put it at the top of the stack. When you add dishes to it, you put them at the top. The most common operations on a stack are as follows:

push(a) # push, push a onto the stackPop ()Eject the last element of the stack
Copy the code

The disadvantage of using Python’s list data structure to simulate stack operations, append to simulate push, and list pop to simulate stack pop is that the list’s own operations can also be used, which can cause confusion.

  • A stack class is defined using Python’s list:
class Stack(object):
    "" implementing a stack using arrays ""
    def __init__(self):
        self.data = []

    def push(self, num):
        """ Stack pressing operation ""
        self.data.append(num)

    def pop(self):
        """ Returns the element popped from the stack, raising IndexError when the stack is empty.
        return self.data.pop()

    def peek(self):
        View the current element at the top of the stack. When the stack is empty, raise IndexError.
        return self.data[- 1]

    def __len__(self):
        Returns the stack length. Len (obj) automatically calls the __len__ method of the obj object.
        return len(self.data)

    def isEmpty(self):
        """ Determine if the stack is empty """
        return True if len(self.data)==0 else False

    def clear(self):
        """ Empty the stack """
        self.data = []

    def __repr__(self):
        """ The current representation of the object, called when the object is typed directly at the end
        return 'Stack_' + str(self.data)

    def __str__(self):
        """ string representation of the current object, called when print(obj) is used
        return 'Stack_' + str(self.data)
Copy the code

The above code implements a simple list-based stack.

  • A typical example of a stack application is to check whether parentheses match. For example: every beginning[After, should follow a position of the right]And every one of them(It should also be followed by a correctly positioned end).
  1. (...). . (...).matching
  2. (...). . (...Don’t match
  3. )... ((...).Mismatch as in the third example, the number of left and right parentheses is equal, but they also do not match, so parentheses cannot be detected simply by checking the number. A very effective solution is to use a stack:
  4. Scan the entire string, and if an opening parenthesis is encountered, push it onto the stack
  5. If a closing parenthesis is encountered, check the element at the top of the stack. If it is a closing parenthesis, push the current parenthesis onto the stack. If it is an opening parenthesis, check whether it matches the current parenthesis
  6. If a closing parenthesis is encountered and the current stack is empty, then this is also a mismatch. The code implementation is as follows:
def isBalance(text):
    "" stack application, check if parentheses are balanced """
    result_stack = Stack()
    for i in text:
        if i in ['{'.'['.'(']:
            result_stack.push(i)
        elif i in ['} '.'] '.') '] :A closing parenthesis is encountered
            if result_stack.isEmpty():
                If the current stack is empty and does not match, return False
                return False
            chFromStack = result_stack.pop()
            
            if not ((chFromStack == '{' and i == '} ' )
                    or (chFromStack == '[' and i == '] ')
                    or (chFromStack == '(' and i == ') ')) :If no match condition is met, return False
                return False

    If the stack is empty, the parentheses match. If the stack is not empty, the parentheses do not match
    return result_stack.isEmpty()

Copy the code