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(lastin 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

Decimal > Binary: bin(999)

Decimal > Octal: oct(999)

Decimal > Binary: hex(999)
Other bases > decimal
 Binary > Decimal: int("10",2)
 Octal to decimal: int("0o13",8) (prefix can be omitted)
 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  postorder expression 

A + B  + A B  A B + 
Here's how to convert infix expressions to other expressions: