🐍🧩 Задача о поврежденной XML-строке
Задача о поврежденной XML-строке часто встречается на олимпиадах. Рассмотрим два варианта решения на Python.
На вход подается XML-строкa, состоящая из строчных букв латинского алфавита, угловых скобок «<», «>» и слэшей «/». В этой строке один символ ошибочно заменен на другой – букву, угловую скобку, либо слэш. Длина строки – от 7 до 1000 символов. Напишите программу, которая находит ошибочный символ и заменяет его на правильный – так, чтобы все теги XML-строки корректно закрывались. Правильных ответов может быть больше одного – можно вывести любой, или все сразу.
Пример ввода: | Пример вывода: |
<a><aa> | <a></a> |
<a><>a> | <a></a> |
<ab/</ab> | <ab></ab> |
<a><ab></ab><c></c></b> | <a><ab></ab><c></c></a> <b><ab></ab><c></c></b> |
Решение
Задача решается методом перебора. Нужно написать функцию проверки строки: для каждого открывающего тега в корректной строке должен быть соответствующий закрывающий тег.
Способ 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 задач на собеседовании для программиста