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

This article mainly explains "how to solve the bracket matching problem," interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Let's let Xiaobian take you to learn "how to solve the bracket matching problem"!

problem description

Suppose we have a complex string containing multiple nested parentheses, as shown below:

At this time, it is a very troublesome thing to judge whether the brackets match artificially with the naked eye. It is not only time-consuming, but also very accurate. So, what methods can help us to judge efficiently? According to the characteristics of the stack, we can easily think of using the list in python to simulate the stack structure to judge.

Examples:

Input: (ABCD(x)

Output: False

Input: {[(rttyy)]sss}

Output: True

solutions

We use a stack to hold unmatched left parenthesis, and we use a for loop to traverse each element of the string from left to right. When traversing to a left parenthesis, push it onto the stack; when traversing to a right parenthesis, remove a left parenthesis from the top of the stack. If there is a match, continue iterating through the rest of the string. If you encounter a right parenthesis that cannot be paired during traversal, or there is no data in the stack, it means that the parenthesis of the string matches incorrectly and returns False directly. When all parentheses are scanned, if the stack is empty, it means that all parentheses of the string match correctly, and returns True; if the stack is not empty, it means that there are unmatched left parentheses, and returns False.

# coding:utf-8

def BracketMatch(str):

#Put the left parenthesis and right parenthesis in one group

LeftBrackets = '{[('

RightBrackets = '}])'

#Create a dictionary according to the matching relationship of parentheses, right parenthesis when key, left parenthesis when value

Brackets = {'}':'{',']':'[',')':'('}

#Create a stack, the initial value is an empty list

Stack = [ ]

for char in (str):

if char in LeftBrackets:

Stack.append(char)

if char in RightBrackets:

if Stack == [ ]:

return False

else:

if Brackets[char] == Stack[-1]:

Stack.pop()

else:

return False

if Stack == [ ]:

return True

else:

return False

str = input ('Please input characters')

print(BracketMatch(str))

The operation result is as follows:

At this point, I believe everyone has a deeper understanding of "how to solve the bracket matching problem," so let's actually operate it! Here is the website, more related content can enter the relevant channels for inquiry, pay attention to us, continue to learn!

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.