Задача о поврежденной XML-строке часто встречается на олимпиадах. Рассмотрим два варианта решения на Python.

На вход подается XML-строкa, состоящая из строчных букв латинского алфавита, угловых скобок «<», «>» и слэшей «/». В этой строке один символ ошибочно заменен на другой – букву, угловую скобку, либо слэш. Длина строки – от 7 до 1000 символов. Напишите программу, которая находит ошибочный символ и заменяет его на правильный – так, чтобы все теги XML-строки корректно закрывались. Правильных ответов может быть больше одного – можно вывести любой, или все сразу.

Решение

Задача решается методом перебора. Нужно написать функцию проверки строки: для каждого открывающего тега в корректной строке должен быть соответствующий закрывающий тег.

Способ 1 – ленивый. Для проверки тегов скобки просто отбрасываются, для замены неверных тегов формируется множество, состоящее из незакрытых тегов, скобок и слэша. Отбрасывание скобок и последующая сборка строки с заведомо правильными скобками могут показаться лишними операциями, однако они позволяют быстро (без перебора) избавиться от ошибки, если она кроется в угловых скобках.

         string = input() temp = string tags = (string.replace('<', ' ').replace('>', ' ')).split()   def checkTags(xml):     stack = []     open_right = None     tags = (xml.replace('<', ' ').replace('>', ' ')).split()     for i in tags:         if i.isalpha():             stack.append(i)         elif i.startswith('/') and i[1:] in stack:             stack.remove(i[1:])         else:              open_right = i              return open_right     if len(stack) == 0 and open_right == None:         return 'closed'     else:         return stack     if checkTags(temp) != 'closed':     exchange = [i for e in checkTags(temp) for i in e]     exchange.extend(['<', '>', '/'])     temp = list(string)     answers = []     for j in range(len(temp)):         for i in '<>/qwertyuiopasdfghjklzxcvbnm':             if temp[j] in set(exchange):                 temp[j] = i                 xml = ''.join(temp)                 if checkTags(xml) == 'closed':                     tags = (xml.replace('<', ' ').replace('>', ' ')).split()                     result = (''.join(["<" + i + ">" for i in tags]))                     if len(result) == len(string):                         answers.append(result)                 else:                     temp = list(string)       print(max(answers))       else:     print(''.join(["<" + i + ">" for i in tags]))     

Способ 2 – в отличие от первого, подсчитывает количество недостающих символов: букв, скобок и слэшей, и проводит перебор и замену в соответствии с результатами. Как следствие, работает быстрее.

         def checkTags(xml):     if xml[0] != '<' or xml[-1] != '>':         return 0     opening_tag = []     i = 0     while True:         if i == len(xml):             break         if xml[i] != '<':             return 0         i += 1         closing_tag = 0         if xml[i] == '/':             closing_tag  = 1             i += 1         if not ('a' <= xml[i] and xml[i] <= 'z'):             return 0         tag = xml[i]         i += 1         while 'a' <= xml[i] and xml[i] <= 'z':             tag += xml[i]             i += 1         if xml[i] != '>':             return 0         i += 1         if closing_tag  == 0:             opening_tag.append(tag)         else:             if len(opening_tag) == 0:                 return 0             if opening_tag[-1] != tag:                 return 0             del opening_tag[-1]     return len(opening_tag) == 0 def changeSymbol():     for i in range(len(string)):         temp = string.copy()         temp[i] = j         if checkTags(temp):             result.append(temp) string = list(input()) opened_chevron = string.count('<') closed_chevron = string.count('>') slashes = string.count('/') letters = {} result = [] for i in string:     letters[i] = letters.get(i, 0) + 1 for j in '<>/qwertyuiopasdfghjklzxcvbnm':     if j == '<' and opened_chevron % 2:         changeSymbol()                      elif j == '>' and closed_chevron % 2:         changeSymbol()                      elif j == '/' and closed_chevron // 2 != slashes:         changeSymbol()                      elif j in letters and letters[j] % 2:         changeSymbol()              for i in result:     print(''.join(i))      

***

Материалы по теме

• 🧩 Задача о спорте и условии Фано
• 🧩 27 сайтов с задачками для оттачивания навыков программирования
• 🧩 15 задач на собеседовании для программиста