Share This
Связаться со мной
Крути в низ
Categories
//Задача о поврежденной XML-строке

Задача о поврежденной XML-строке

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

zadacha o povrezhdennoj xml stroke 64027b0 - Задача о поврежденной XML-строке

На вход подается 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 задач на собеседовании для программиста

  • 0 views
  • 0 Comment

Leave a Reply

Ваш адрес email не будет опубликован.

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.

Свежие комментарии

    Рубрики

    About Author 01.

    blank
    Roman Spiridonov

    Моя специальность - Back-end Developer, Software Engineer Python. Мне 39 лет, я работаю в области информационных технологий более 5 лет. Опыт программирования на Python более 3 лет. На Django более 2 лет.

    Categories 05.

    © Speccy 2022 / All rights reserved

    Связаться со мной
    Close