Shulou(Shulou.com)06/01 Report--

This article mainly introduces "how to realize the stack in the Python data structure and algorithm". In the daily operation, I believe that many people have doubts about how to realize the stack in the Python data structure and algorithm. Xiaobian consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for everyone to answer the doubt of "how to realize the stack in the Python data structure and algorithm". Next, please follow the editor to study!

Match parentheses

Next, we use stacks to solve practical computer science problems.

For example, we have all written arithmetic expressions like this, (5: 6) ∗ (7: 8) / (4: 3) (5: 6) * (7: 8) / (4: 3) (5: 6) ∗ (7: 8) / (4: 3), where the parentheses are used to change the order of calculation or to raise the priority of the operation.

Matching parentheses means that each left parenthesis has a corresponding right parenthesis, and the parenthesis pair has the correct nesting relationship.

Correct nesting relations: (()), (()) ((())) ((())), (() ()) (()))

Wrong nesting relationship: ()), () ()) ()))

Our challenge is to write an algorithm that reads a string of parentheses from left to right (excluding other numbers and operators) and then determines whether the parentheses match.

In order to solve this problem, we need to pay attention to an important phenomenon. When processing parentheses from left to right, the rightmost unmatched left parenthesis must match the first right parenthesis encountered next. Also, the left parenthesis in the first position may not match until the closing parenthesis in the last position is processed. And the order of occurrence of the right parenthesis is opposite to that of the matching left parenthesis. This law implies that the stack can be used to solve the problem of parenthesis matching.

Once you realize that you use stacks to hold parentheses, the algorithm is easy to write.

Starting with an empty stack, parentheses are processed from left to right. If you encounter a left parenthesis, it is added to the stack through the stack's push operation, indicating that a matching right parenthesis is needed later.

Conversely, if a closing parenthesis is encountered, the pop operation of the stack is invoked. As long as all the left parentheses in the stack can encounter a matching right parenthesis, the whole parenthesis string matches; if any of the left parentheses in the stack cannot find a matching right parenthesis, the parenthesis string does not match. After processing the matching parenthesis strings, the stack should be empty.

To put it simply: scan the parenthesis string, put the left parenthesis into the stack, meet the right parenthesis, take a left parenthesis pair from the top of the stack, and cancel each other out until the end. If the parentheses match, the stack should be empty at the end, and the parenthesis string is just scanned.

The code is implemented as follows:

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 parChecker (symbolString): s = Stack () # Construction Stack balanced = True # matching flag defaults to True indicating matching index = 0 # index is used to fetch characters # when the index is less than the length of the string and the matching flag is True While index < len (symbolString) and balanced: # take the leading character of the string symbol = symbolString [index] # if the current character is left parenthesis, if symbol = ='(': s.push (symbol) # if the current character is not left parenthesis (then it is right parenthesis) else: # and the stack is empty if s.isEmpty (): # the match flag is set to False to indicate match failure (lone right parenthesis) balanced = False # Stack is not empty offset top left parenthesis else: s.pop () # Index moves backward An index = index + 1 # loop ends if the match is successful and the stack is empty if balanced and s.isEmpty (): return True else: return False

Note that the initial value of balanced is True, because there is no reason to assume that it is False at first. If the current symbol is a left parenthesis, it is pushed into the stack (line 27). Notice line 36, where only one element is removed from the top of the stack through pop (). Since the removed element must be the left parenthesis encountered earlier, the return value of pop () is not used. In lines 42-45, the function returns True as long as all the parentheses match and the stack is empty, otherwise it returns False.

Matching symbol

Symbol matching is a common problem in many programming languages, and parenthesis matching is only a special case. We've learned how to match parentheses, so now let's try matching symbols.

Matching symbols refer to the correct matching and nesting of left and right corresponding symbols.

For example, in Python, square brackets "[" and "]" are used for lists; curly braces "{" and "}" are used for dictionaries; and parentheses "(" and ")" are used for tuples and arithmetic expressions. As long as you ensure that the left and right symbols match, you can mix these symbols. The following symbol strings match, in which not only each left symbol has a right symbol corresponding to it, but also the type of the two symbols is the same.

{{([] [])} ()}

[[{{()}}]]

[] () {}

The following symbols do not match:

([)]

()])

[{()]

To deal with new types of symbols, we extend the parenthesis match detection code above.

That is, each left symbol will be pushed into the stack so that the corresponding right symbol appears later.

The only difference is that when a right symbol appears, you must first check whether its type matches the left symbol type at the top of the stack. If the two symbols do not match, then the entire symbol string does not match. Similarly, if the entire string of symbols is processed and the stack is empty, then all symbols match correctly.

The code is implemented as follows:

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 parChecker (symbolString): s = Stack () # Construction Stack balanced = True # matching flag defaults to True indicating matching index = 0 # index is used to fetch characters # when the index is less than the length of the string and the matching flag is True While index < len (symbolString) and balanced: # take the leading character of the string symbol = symbolString [index] # if the current character belongs to the left bracket set then stack if symbol in'([{': s.push (symbol) # if the current character is not the left parenthesis (then the current is the right parenthesis) else: # and the stack is empty if s.isEmpty (): # the matching flag is set to False to indicate match failure (lone right parenthesis) balanced = False # Stack is not empty take out the left parenthesis at the top of the stack for type matching else: top = s.pop () # Type matching failed if not matches (top Symbol): balanced = False # Index moves backward one bit index = index + 1 # Loop ends if the match is successful and the stack is empty if balanced and s.isEmpty (): return True else: return Falsedef matches (left, right): lefts = "([{" rights = ")]}" # call the index method of the string The index () method looks for the first occurrence of the specified value and returns the index. # the corresponding index indicates that the symbol matches return lefts.index (left) = = rights.index (right)

The test results are shown in the following figure:

The above two examples show that the stack is a very important data structure when dealing with the syntax structure of a programming language. Almost all notation has some kind of symbol that needs to be correctly matched and nested. In addition, there are some other important application scenarios of stack in computer science, let's continue to explore.

At this point, the study of "how to implement the stack in the Python data structure and algorithm" is over. I hope to be able to solve everyone's doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.