做动画在线观看网站,邢台网站定制,宁德蕉城住房和城乡建设部网站,同学录网站建设问题#xff1a;判断一个有左括号和右括号、以及其他ASCII字符组成的表达式是合法。 判断条件是左括号-右括号数目、次序配对#xff0c;可多层嵌套。如果有*#xff0c;则*可作为0个或者1个右括号#xff0c;如果匹配则输出ok,不匹配则输出不匹配字符所在字符串中的具体位…问题判断一个有左括号和右括号、以及其他ASCII字符组成的表达式是合法。 判断条件是左括号-右括号数目、次序配对可多层嵌套。如果有*则*可作为0个或者1个右括号如果匹配则输出ok,不匹配则输出不匹配字符所在字符串中的具体位置示例((((***********))(((** 不匹配字符位置18 结果NOK((((***********))(((**)) 结果OK(()())((()))(()***) 结果OK(()*) 结果OK*(()*()()*(((* 不匹配字符位置12 结果NOK(((())))*()(*((** 结果OK((()(())* 不匹配字符位置1 结果NOK((**)(*()))) 不匹配字符位置12 结果NOK***(((()())** 结果OK(*)) 不匹配字符位置4 结果NOK()(())*(*)( 不匹配字符位置11 结果NOK((((******))(((** 不匹配字符位置13 结果NOK分析在字符串中如果有右括号则优先匹配右括号再考虑是否要进行通配符匹配。因此可以先求出通配符*最少需要多少个才能满足字符串中所有的的左括号匹配计算公式为if 左括号数量 右括号数量://右括号大于等于左括号不用通配符*替换max_replace_num0else://右括号比左括号少如果有*则需要用*进行替换右括号max_replace_num左括号数量-右括号数量因括号匹配问题是优先最近原则因此可以将左括号入栈如果遇到右括号从栈中弹出一个与之匹配如果遇到通配符*如果max_replace_num0则直接跳过否则先入队列优先让右括号先进行匹配等到再碰到下一个左括号时先让队列中的通配符*优先匹配完栈中的左括号再让左括号入栈。具体流程图详细代码def append_list(i,ch):ch_list []ch_list.append(i)ch_list.append(ch)return ch_listdef breaket_match(one_str)::param one_str: 需要匹配的字符串:return: 返回则说明匹配否则返回不匹配位置left_len one_str.count(() #左括号个数left_list [] # 临时存放左括号字符串列表right_list[] #保存*的队列if left_len one_str.count()): #右括号大于等于左括号不用*替换max_replace_num0else: #右括号比左括号少如果有*则需要用*进行替换右括号max_replace_numleft_len-one_str.count()) #替换个数为左括号减去右括号个数for i in range(len(one_str)):if one_str[i] (: #碰到第一个左括号把标志位设置为false说明从这里加上进行正式匹配flagFalseif len(right_list)0:left_list.append(append_list(ii,chone_str[i])) #当前左括号和左括号位置入栈else: #*替换最大可替换个数klen(right_list)tmp_replace max_replace_numfor j in range(k):if len(left_list)0 or j tmp_replace-1:breakelse:left_list.pop()max_replace_num - 1right_list.clear()left_list.append(append_list(ii, chone_str[i])) # 当前*和*位置入栈elif one_str[i] ):#如果当前字符时右括号出栈if len(left_list) ! 0: # 如果栈中有元素与之匹配没有元素说明不匹配返回位置left_list.pop()else:return i 1 # 不匹配返回位置信息else: #如果当前字符是*if max_replace_num0: #判断*是否需要进行右括号匹配为说明不需要进行替换passelse: #*需要替换为右括号if len(left_list)!0 : #如果栈中有元素与之匹配没有元素说明不匹配返回位置,并且替*换个数right_list.append(append_list(ii, chone_str[i])) # 左括号和左括号位置入栈else: #如果左括号个数为但是下一个与之匹配的为*,则跳过passk len(right_list)tmp_replacemax_replace_numfor i in range(k):if len(left_list) 0 or i tmp_replace-1:breakelse:left_list.pop()max_replace_num - 1if (len(left_list)!0): #如果左括号栈中元素不为空不匹配返回位置信息return left_list.pop()[0]1else: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) #去掉换行符\nlines.append(line) #把文件的每一行append到lines里面line file.readline()if not line:file.close()breakexcept :print(打开文件失败请确认文件名和路径是否正确)return linesdef main():# print(请输入文本文件路径)#读取文件# filepathinput() #读取控制台谁的文件路径linesread_file(test.txt)length_lineslen(lines)#breaket_match(str)输入参数str为需要匹配的字符串如果匹配成功则返回true,如果匹配不成功则返回falsefileopen(result.txt,w)for i in range(length_lines): #对读取出来的文件每一行进行匹配resultbreaket_match(one_strlines[i])if result-1:file.write(行号第str(i1)行; 源字符串lines[i]; 结果OK\n)print(行号第str(i1)行; 源字符串lines[i]; 结果OK)else:file.write(行号第 str(i1) 行; 源字符串 lines[i] ; 不匹配字符位置str(result) 结果 NOK\n)print(行号第 str(i1) 行; 源字符串 lines[i] ; 不匹配字符位置str(result) 结果 NOK)file.close()if __name__ __main__:main()
