BOJ 5076 - Web Pages

문제

백준 온라인 저지 - 5076번

풀이 과정

HTML 문자열을 입력으로 받아서 해당 문자열이 유효한지 판단하는 문제입니다.
열린 태그와 닫힌 태그는 서로 쌍을 이루어야 하기 때문에 (self-closing 태그 제외) 스택 을 이용해서 유효성을 판단하면 됩니다.
이때 주어진 문자열에서 태그를 추출하기 위해 파싱하는 함수를 구현합니다.
태그 정보는 태그 이름, 태그 타입 으로 구성됩니다.

코드

import sys


def parse_tag(html):
    parsed_tags = []
    start_parsing = False
    tag_name = ''
    tag_type = ''

    for idx in range(len(html)):
        if html[idx] == '<':
            tag_type = 'open' if html[idx + 1] != '/' else 'close'
            start_parsing = True
        elif html[idx] == '>':
            tag_type = 'self-closing' if html[idx - 1] == '/' else tag_type
            parsed_tags.append({'tag_type': tag_type, 'tag_name': tag_name })
            tag_type = ''
            tag_name = ''
            start_parsing = False
        else:
            if start_parsing and html[idx] != ' ':
                if html[idx] != '/':
                    tag_name += html[idx]
            else:
                start_parsing = False

    return parsed_tags


def solution(html):
    tag_stack = []
    tags = parse_tag(html)

    for tag in tags:
        if tag['tag_type'] == 'self-closing':
            continue
        elif tag['tag_type'] == 'close':
            if not tag_stack:
                return 'illegal'

            top_tag = tag_stack[-1]
            if top_tag['tag_type'] != 'open' or top_tag['tag_name'] != tag['tag_name']:
                return 'illegal'

            tag_stack.pop()
        else:
            tag_stack.append(tag)

    return 'legal' if not tag_stack else 'illegal'


if __name__ == '__main__':
    while True:
        question = sys.stdin.readline().strip()

        if question == '#':
            break

        answer = solution(question)
        print(answer)