According to "Python Data Structure and Algorithm Analysis" and other network materials.

What is a stack?

A stack is an ordered collection where additions and removals happen at the same end.

The closer the elements in the stack are to the bottom, the longer the time in the stack, so the bottom of the stack has a very important meaning. Newly added elements will be removed first. This sorting principle is LIFO(last-in first out), last in first out

such as stacking of books

abstract data type of stack

The abstract data type of the stack is defined by the following structures and operations.

• Stack() creates an empty stack. No arguments are required, and an empty stack is returned.
• push(item) adds an element to the top of the stack. One parameter item is required, and no return value
• pop() removes the top element. No parameters are required, but there is a return value.
• peek() returns the element at the top of the stack. No parameters, and do not modify the contents of the stack.
• isEmpty() checks if the stack is empty. No arguments are required, a boolean is returned.
• size() returns the number of elements in the stack. No arguments are required, an integer is returned.

Implement stack in python

After explicitly defining the abstract data type of the stack, we implement it in Python. Implementations of abstract data types are called data structures.

Since a stack is a collection of elements, it can be implemented using the list provided by Python.

Implementation method one

Use the pop() and append() methods to use the head of the list as the bottom of the stack.

class Stack:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    def push(self,item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        return self.items[len(self.items) - 1]
    def size(self):
        return len(self.items)

Implementation method two

Use the tail of the list as the bottom of the stack, so the pop() and append() groups are no longer used. You should use pop(0) and insert(0,item) to access index 0, which is the first element.

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self,item):
        self.items.insert(0,item)

    def pop(self):
        self.items.pop(0)

    def peek(self):
        return self.items[0]

    def size(self):
        return len(self.items)

Both implementations above are possible, but there are definitely differences in performance between the two. The time complexity of append and pop() methods are both O(1), which means that push and pop in the first implementation will complete in constant time regardless of how many elements are in the stack. The performance of the second implementation is limited by the number of stacks, because the time complexity of insert(0) and pop(0) is O(n), the more elements the slower the time.

match symbol

matching parentheses

Matching parentheses are when each opening parenthesis has a corresponding closing parenthesis, and the parentheses are properly nested. Below is the correct matching bracket string.

(()()())

(((())))

The following is an unmatched parenthesis string

((()

((())

Let's write an algorithm that reads a string of parentheses from left to right and determines whether the parentheses in it match. In order to solve this problem, we need to pay attention to a very important phenomenon. . When processing parentheses from left to right, the rightmost unmatched opening parenthesis must match the first closing parenthesis encountered next. Also, an opening bracket in the first position may not complete a match until the closing bracket in the last position is processed. The matching closing parentheses appear in the reverse order of the opening parentheses. This pattern implies that the stack can be used to solve the bracket matching problem

Algorithms are easy to write once you realize that it makes sense to store parentheses on the stack. Starting with an empty stack, the parentheses are processed from left to right. If an opening parenthesis is encountered, it is pushed onto the stack via a push operation, indicating that a matching closing parenthesis is required later. Conversely, if a closing bracket is encountered, the pop operation is called. As long as all the left brackets in the stack can encounter the right bracket that matches them, the whole bracket string is matched. If any of the left parentheses in the stack cannot find a matching right parenthesis, the bracket string does not match of. After processing the matching bracket string, the stack should be empty.

# bracket matching
def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol == "(":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                s.pop()
        index += 1
    if balanced and s.isEmpty():
        return True
    else:
        return False

match symbol

For upgrades that match parentheses, for example:

[[('')]]

[{)']

The combination of various left and right symbols can be processed by adding [], {} to the above code.

# symbol match

def parChecker(symbolString):
    i = 1
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol in "{[(":
            s.push(symbol)

        else:
            if s.isEmpty():
                balanced = False
            else:
                top = s.pop()

                if not matches(top,symbol):
                    balanced = False
        index += 1

    if balanced and s.isEmpty():
        return True
    else:
        return False

def matches(left,right):

    lefts = "([{"
    rights = ")]}"
    return lefts.index(left) == rights.index(right)

base conversion

Decimal -> Binary

The way to convert from decimal to binary is to keep dividing by two until the quotient is 0. Then connect the remainders in reverse order, for example:

100/2 = 50...0

50/2 =25...0

25/2 = 12...1

12/2 = 6...0

6/2 = 3...0

3/2 = 1...1

1/2 = 0...1

So the final result is 1100100

The final procedure is as follows:

class Stack:
    def __init__(self):
        self.items = []
    def push(self,item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def isEmpty(self):
        return self.items == []
    def peek(self):
        return self.items[len(self.items)-1]
    def size(self):
        return len(self.items)
    def printf(self):
        print(self.items)

def divide_to_2(num):
    s = Stack()
    binStr = ""
    while num > 0:
        s.push(num % 2)
        num = num // 2
    while not s.isEmpty():
        binStr = binStr + str(s.pop())
    return binStr

num = int(input('type in data:'))
print(divide_to_2(num))

Decimal —> Arbitrary

def divide_to_base(num,base):
    s = Stack()
    baseStr = ""
    while num > 0:
        s.push(num % base)
        num = num // base
    while not s.isEmpty():
        baseStr = baseStr + str(s.pop())
    return baseStr

num,base = map(int,input('Enter number and destination base:').split())
print(divide_to_base(num,base))

Python base conversion

Considering the grammatical characteristics, Python has already encapsulated the functions of hex conversion.

Decimal -> other bases

1. Decimal -> Binary: bin(999)

2. Decimal -> Octal: oct(999)

3. Decimal -> Binary: hex(999)

Other bases -> decimal

1. Binary -> Decimal: int("10",2)
2. Octal to decimal: int("0o13",8) (prefix can be omitted)
3. Hexadecimal -> Decimal: int("0xaa",16) (prefix can be omitted)

Preorder, inorder and postorder expressions

In daily use, we use inorder expressions.

inorder expression	preorder expression	post-order expression
A + B	+ A B	A B +

Here's how to convert infix expressions to other expressions: