問(wèn)題：

判斷一個(gè)有左括號(hào)和右括號(hào)、以及其他ASCII字符組成的表達(dá)式是合法。 判斷條件是左括號(hào)-右括號(hào)數(shù)目、次序配對(duì)，可多層嵌套。如果有*，則*可作為0個(gè)或者1個(gè)右括號(hào)，如果匹配則輸出ok,不匹配則輸出不匹配字符所在字符串中的具體位置

示例：

((((***********))(((**? ? ? ? ? ?不匹配字符位置：18 結(jié)果：NOK

((((***********))(((**))? ? ? ? ?結(jié)果：OK

(()())((()))(()***)? ? ? ? ? ? ? ? ?結(jié)果：OK

(()*)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??結(jié)果：OK

*(()*()()*(((*? ? ? ? ? ? ? ? ? ? ??不匹配字符位置：12 結(jié)果：NOK

(((())))*()(*((**? ? ? ? ? ? ? ? ??結(jié)果：OK

((()(())*? ? ? ? ? ? ? ? ? ? ? ? ? ??不匹配字符位置：1 結(jié)果：NOK

((**)(*())))? ? ? ? ? ? ? ? ? ? ? ??不匹配字符位置：12 結(jié)果：NOK

***(((()())**? ? ? ? ? ? ? ? ? ? ? ?結(jié)果：OK

(*))? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??不匹配字符位置：4 結(jié)果：NOK

()(())*(*)(? ? ? ? ? ? ? ? ? ? ? ? ??不匹配字符位置：11 結(jié)果：NOK

((((******))(((**? ? ? ? ? ? ? ? ? 不匹配字符位置：13 結(jié)果：NOK

分析：

在字符串中，如果有右括號(hào)，則優(yōu)先匹配右括號(hào)，再考慮是否要進(jìn)行通配符匹配。因此，可以先求出通配符*最少需要多少個(gè)才能滿足字符串中所有的的左括號(hào)匹配，計(jì)算公式為：

if? 左括號(hào)數(shù)量 <= 右括號(hào)數(shù)量://右括號(hào)大于等于左括號(hào)，不用通配符*替換

max_replace_num=0

else://右括號(hào)比左括號(hào)少，如果有*則需要用*進(jìn)行替換右括號(hào)

max_replace_num=左括號(hào)數(shù)量-右括號(hào)數(shù)量

因括號(hào)匹配問(wèn)題是優(yōu)先最近原則，因此，可以將左括號(hào)入棧，如果遇到右括號(hào)，從棧中彈出一個(gè)與之匹配，如果遇到通配符*，如果max_replace_num==0則直接跳過(guò)，否則先入隊(duì)列，優(yōu)先讓右括號(hào)先進(jìn)行匹配，等到再碰到下一個(gè)左括號(hào)時(shí)先讓隊(duì)列中的通配符*優(yōu)先匹配完棧中的左括號(hào)，再讓左括號(hào)入棧。

具體流程圖：

詳細(xì)代碼：

def append_list(i,ch):

ch_list = []

ch_list.append(i)

ch_list.append(ch)

return ch_list

def breaket_match(one_str):

'''

:param one_str: 需要匹配的字符串

:return: 返回－１則說(shuō)明匹配，否則返回不匹配位置

'''

left_len = one_str.count('(') #左括號(hào)個(gè)數(shù)

left_list = [] # 臨時(shí)存放左括號(hào)字符串列表

right_list=[] #保存*的隊(duì)列

if left_len <= one_str.count(')'): #右括號(hào)大于等于左括號(hào)，不用*替換

max_replace_num=0

else: #右括號(hào)比左括號(hào)少，如果有*則需要用*進(jìn)行替換右括號(hào)

max_replace_num=left_len-one_str.count(')') #替換個(gè)數(shù)為左括號(hào)減去右括號(hào)個(gè)數(shù)

for i in range(len(one_str)):

if one_str[i] == '(': #碰到第一個(gè)左括號(hào)，把標(biāo)志位設(shè)置為false，說(shuō)明從這里加上進(jìn)行正式匹配

flag=False

if len(right_list)==0:

left_list.append(append_list(i=i,ch=one_str[i])) #當(dāng)前左括號(hào)和左括號(hào)位置入棧

else: #*替換最大可替換個(gè)數(shù)

k=len(right_list)

tmp_replace = max_replace_num

for j in range(k):

if len(left_list)==0 or j >tmp_replace-1:

break

else:

left_list.pop()

max_replace_num -= 1

right_list.clear()

left_list.append(append_list(i=i, ch=one_str[i])) # 當(dāng)前*和*位置入棧

elif one_str[i] == ')':#如果當(dāng)前字符時(shí)右括號(hào)，出棧

if len(left_list) != 0: # 如果棧中有元素與之匹配，沒(méi)有元素，說(shuō)明不匹配，返回位置

left_list.pop()

else:

return i + 1 # 不匹配，返回位置信息

else: #如果當(dāng)前字符是*

if max_replace_num==0: #判斷*是否需要進(jìn)行右括號(hào)匹配，為０說(shuō)明不需要進(jìn)行替換

pass

else: #*需要替換為右括號(hào)

if len(left_list)!=0 : #如果棧中有元素與之匹配，沒(méi)有元素，說(shuō)明不匹配，返回位置,并且替*換個(gè)數(shù)－１

right_list.append(append_list(i=i, ch=one_str[i])) # 左括號(hào)和左括號(hào)位置入棧

else: #如果左括號(hào)個(gè)數(shù)為０，但是下一個(gè)與之匹配的為*,則跳過(guò)

pass

k = len(right_list)

tmp_replace=max_replace_num

for i in range(k):

if len(left_list) == 0 or i > tmp_replace-1:

break

else:

left_list.pop()

max_replace_num -= 1

if (len(left_list)!=0): #如果左括號(hào)棧中元素不為空，不匹配，返回位置信息

return left_list.pop()[0]+1

else:

return -1 #匹配，返回－１

def read_file(file_path):

'''

讀取文件

:param file_path:

:return: 返回list集合，里面包含文件每一行的字符

'''

lines = []

try:

file = open(file_path) #打開文件

line = file.readline() #讀取文件第一行

while 1:

line = line.strip('\n') #去掉換行符\n

lines.append(line) #把文件的每一行append到lines里面

line = file.readline()

if not line:

file.close()

break

except :

print("打開文件失敗，請(qǐng)確認(rèn)文件名和路徑是否正確！")

return lines

def main():

# print("請(qǐng)輸入文本文件路徑：")

#讀取文件

# filepath=input() #讀取控制臺(tái)誰(shuí)的文件路徑

lines=read_file("test.txt")

length_lines=len(lines)

#breaket_match(str)輸入?yún)?shù)str為需要匹配的字符串，如果匹配成功，則返回true,如果匹配不成功，則返回false

file=open("result.txt","w")

for i in range(length_lines): #對(duì)讀取出來(lái)的文件每一行進(jìn)行匹配

result=breaket_match(one_str=lines[i])

if result==-1:

file.write("行號(hào)：第"+str(i+1)+"行; "+"源字符串："+lines[i]+"; "+"結(jié)果："+"OK"+"\n")

print("行號(hào)：第"+str(i+1)+"行; "+"源字符串："+lines[i]+"; "+"結(jié)果："+"OK")

else:

file.write("行號(hào)：第" + str(i+1) + "行; " + "源字符串：" + lines[i] + "; " +"不匹配字符位置："+str(result)+ " 結(jié)果：" + "NOK"+"\n")

print("行號(hào)：第" + str(i+1) + "行; " + "源字符串：" + lines[i] + "; " +"不匹配字符位置："+str(result)+ " 結(jié)果：" + "NOK")

file.close()

if __name__ == '__main__':

main()

總結(jié)

以上是生活随笔為你收集整理的python括号匹配问题_支持通配符的括号匹配问题源码+详细流程代码（python）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。