Наталья Кайда 15 февраля 2022

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

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

Работа мечты в один клик 💼

Работа в Сбере: пройди собеседование и получи оффер за 15 минут

💭Мечтаешь работать в Сбере, но не хочешь проходить десять кругов HR-собеседований? Теперь это проще, чем когда-либо!

💡AI-интервью за 15 минут – и ты уже на шаг ближе к своей новой работе.

Как получить оффер?
📌 Зарегистрируйся
📌 Пройди AI-интервью
📌 Получи обратную связь сразу же!

HR больше не тянут время – рекрутеры свяжутся с тобой в течение двух дней! 🚀

Реклама. ПАО СБЕРБАНК, ИНН 7707083893. Erid 2VtzquscAwp

На вход подается 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))
***

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




Комментарии

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ