Python implements a method to solve the bracket matching problem

This article mainly introduces Python's method of solving bracket matching problems, involving Python's stack-based string traversal, judgment, and operation skills to solve bracket matching problems. Friends in need can refer to it

The example in this article describes the method of solving the bracket matching problem in Python. I share it with you for your reference. The details are as follows:

I have been exposed to this a lot when I was studying data structure in my undergraduate degree. The mainstream idea is to use stack pushing and popping to perform matching. As for python, you can use lists. To complete this operation, because the append method of the list is equivalent to the push method of the stack, and the pop method of the list is equivalent to the pop of the stack method.

The main idea:

First set up two lists to store the opening brackets and closing brackets of various brackets, and then traverse the given string and divide it into The following situations:

1. The first character of the string appears in the closed bracket list, ends directly, and outputs an error

2. The length of the string is not an even number, ends directly, and outputs an error

3. Deduplicate the original string into a list. If the length of the deduplicated list is not an even number, it will end directly and an error will be output.

4. Traverse the string and remove the brackets that belong to the set of open brackets. Add it to the list. When encountering a closed bracket, calculate whether the index of the closed bracket in the closed bracket list is consistent with the index of the last open bracket in the current list in the open bracket list. If they are consistent, continue, otherwise it will end directly and output The error

is mainly because when the length is very large, some obvious error patterns can be determined as soon as possible to save time. According to this simple idea, the following is the specific implementation:

#!usr/bin/env python
#encoding:utf-8
'''''
__Author__:沂水寒城
功能：括号匹配的相关问题
'''
def bracket_mathch(one_str):
 '''''
 括号匹配
 '''
 tmp_list=[]
 open_bracket_list=[&#39;(&#39;,&#39;[&#39;,&#39;{&#39;,&#39;<&#39;,&#39;《&#39;]
 close_bracket_list=[&#39;)&#39;,&#39;]&#39;,&#39;}&#39;,&#39;>&#39;,&#39;》&#39;]
 one_str_list=list(one_str)
 length=len(one_str_list)
 set_list=list(set(one_str_list))
 num_list=[one_str_list.count(one) for one in set_list]
 if one_str[0] in close_bracket_list:
  return False
 elif length%2!=0:
  return False
 elif len(set_list)%2!=0:
  return False
 else:
  for i in range(length):
   if one_str[i] in open_bracket_list:
    tmp_list.append(one_str[i])
   elif one_str[i] in close_bracket_list:
    if close_bracket_list.index(one_str[i])==open_bracket_list.index(tmp_list[-1]):
     tmp_list.pop()
    else:
     return False
     break
 return True
if __name__ == &#39;__main__&#39;:
 one_str_list=[&#39;({})&#39;,&#39;({[<《》>]})&#39;,&#39;[(]){}&#39;,&#39;{{{{{{&#39;,&#39;([{}])&#39;,&#39;}{[()]&#39;]
 for one_str in one_str_list:
  if bracket_mathch(one_str):
   print one_str, &#39;正确&#39;
  else:
   print one_str, &#39;错误&#39;
 tmp=&#39;{}[{()()[]<{{[[[[(())()()(){}[]{}[]()<>]]]]}}>}]&#39;
 print bracket_mathch(tmp)

The results are as follows:

##

The above is the detailed content of Python implements a method to solve the bracket matching problem. For more information, please follow other related articles on the PHP Chinese website!