Решение задачи Поврежденный XML с Acmp

Без пояснения   Просмотров: 2054

Формат XML является распространенным способом обмена данными между различными программами. Недавно программист Иванов написал небольшую программу, которая сохраняет некоторую важную информацию в виде XML-строки.

XML-строка состоит из открывающих и закрывающих тегов. Открывающий тег начинается с открывающей угловой скобки (<), за ней следует имя тега — непустая строка из строчных букв английского алфавита, а затем закрывающая угловая скобка (>). Примеры открывающих тегов: , .

Закрывающий тег начинается с открывающей угловой скобки, за ней следует прямой слеш (/), затем имя тега — непустая строка из строчных букв английского алфавита, а затем закрывающая угловая скобка. Примеры закрывающихся тегов: , .

XML-строка называется корректной, если она может быть получена по следующим правилам:

Пустая строка является корректной XML-строкой.
Если A и B — корректные XML-строки, то строка AB, получающаяся приписыванием строки B в конец строки A, также является корректной XML-строкой.
Если A — корректная XML-строка, то строка A, получающаяся приписыванием в начало A открывающегося тега, а в конец — закрывающегося с таким же именем, также является корректной XML-строкой. Здесь X — любая непустая строка из строчных букв английского алфавита.
Например, представленные ниже строки:




являются корректными XML-строками, а такие строки как:




не являются корректными XML-строками.

Иванов отправил файл с сохраненной XML-строкой по электронной почте своему коллеге Петрову. Однако, к сожалению, файл повредился в процессе пересылки: ровно один символ в строке заменился на некоторый другой символ.

Требуется написать программу, которая по строке, которую получил Петров, восстановит исходную XML-строку, которую отправлял Иванов.

Код 

def isValid(str):
    if str[0] != '<' or str[-1] != '>':
        return 0
    open = []
    i = 0
    while 1:
        if i == len(str):
            break
        if str[i] != '<':
            return 0
        i += 1
        closing = 0
        if str[i] == '/':
            closing = 1
            i += 1
        if not ('a' <= str[i] and str[i] <= 'z'):
            return 0
        tag = str[i]
        i += 1
        while 'a' <= str[i] and str[i] <= 'z':
            tag += str[i]
            i += 1
        if str[i] != '>':
            return 0
        i += 1
        if closing == 0:
            open.append(tag)
        else:
            if len(open) == 0:
                return 0
            if open[-1] != tag:
                return 0
            del open[-1]
    return len(open) == 0


s = list(input())
chars = ['<', '/', '>', 'a', 'b', 'c', 'd', 'e', 'f']
chars += ['g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o']
chars += ['p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
open_quotes, close_quotes, slashes = 0, 0, 0
letters = {}
for i in s:
    if i == '<':
        open_quotes += 1
    elif i == '>':
        close_quotes += 1
    elif i == '/':
        slashes += 1
    else:
        if i in letters:
            letters[i] += 1
        else:
            letters[i] = 1


for j in chars:
    if j == '<' and open_quotes % 2:
        for i in range(len(s)):
            t = s.copy()
            t[i] = j
            if isValid(t):
                print(*t, sep="")
                raise SystemExit
    if j == '>' and close_quotes % 2:
        for i in range(len(s)):
            t = s.copy()
            t[i] = j
            if isValid(t):
                print(*t, sep="")
                raise SystemExit
    if j == '/' and close_quotes // 2 != slashes:
        for i in range(len(s)):
            t = s.copy()
            t[i] = j
            if isValid(t):
                print(*t, sep="")
                raise SystemExit
    if j in letters and letters[j] % 2:
        for i in range(len(s)):
            t = s.copy()
            t[i] = j
            if isValid(t):
                print(*t, sep="")
                raise SystemExit
# <a><ab></ab><c></c></b>

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp