Q001_KIDJourney_solution

[KIDJourney]

Question_ID: Q001

Language: Python

Time Cost: 50-mins

Time Complexity: O(n)

Solution

1. write a lexer to split tag and content (tokens).
2. tokens formatting is easy.
3. my code is ugly like shit

My Code

from string import ascii_letters, digits

KEYWORDS = {'<', '>'}
TAG_ALLOW_CHAR = set(list(ascii_letters) + ['/'] + list(digits))
TAG_ALLOW_NAME_CHAR = set(list(ascii_letters) + list(digits))

class Tag(object):
    def __init__(self, lex):
        if '/' in lex:
            self.tt = -1
        else :
            self.tt = 1
        self.lex = lex
        self.name = ''.join(list(filter(lambda x: x in TAG_ALLOW_NAME_CHAR,  self.lex)))

    def __eq__(self, tag):
        return self.tt + tag.tt == 0 and self.name == tag.name

    def __repr__(self):
        return "<Tag:'{}'>".format(self.lex)

class Content(object):
    def __init__(self, lex):
        self.lex = lex

    def __eq__(self, obj):
        return False

    def __repr__(self):
        return "<Content:'{}'>".format(self.lex)

def lex_xml(xmlstring):
    tokens = []
    stash = []
    in_tag = False
    for c in xml_line:
        if in_tag:
            if c == '>':
                stash.append(c)
                tokens.append(Tag(''.join(stash)))
                stash = []
                in_tag = False
                continue
            elif c not in TAG_ALLOW_CHAR:
                in_tag = False
                if stash:
                    tokens.append(Content(''.join(stash)))
                    stash = []
                in_tag = False
            else:
                stash.append(c)            

        if not in_tag:
            if c == '<':
                if stash:
                    tokens.append(Content(''.join(stash)))
                    stash = []
                stash.append(c)
                in_tag = True
            else:
                stash.append(c)

    if stash:
        tokens.append(Content(''.join(stash)))

    return tokens

def format_tokens(tokens):
    intend = 0
    lex_stack = []
    content_stash = []
    ret = []
    for l in tokens:
        is_tag  = isinstance(l, Tag)
        if is_tag:
            if lex_stack and lex_stack[-1] == l:
                lex_stack.pop()
                intend -= 1
                ret.append("{}{}".format('\t'*intend, l.lex))
            elif l.tt == 1:
                lex_stack.append(l)
                ret.append("{}{}".format('\t'*intend, l.lex))
                intend += 1
            else:
                ret.append("{}{}".format('\t'*intend, l.lex))

            if content_stash:
                ret.append('{}{}'.format('\t'*intend,''.join([i.lex for i in content_stash])))
                content_stash = []

        else:
            content_stash.append(l)

    return '\n'.join(ret)

if  __name__ == "__main__":
    xml_line = """<a>123<b>456<c/>"1>2"</d>blabla1>2>3>4<5<6<7<8 and i like math</b></a>"""
    # xml_line = "<a<a>>"
    tokens = lex_xml(xml_line)
    print(tokens)
    print(format_tokens(tokens))

Other

I should learn to make a beautiful lexer...

[isaacpei]

好长啊... 这么长的代码面试的时候是看不下去的 如果有好的解法, 可以跟面试官讨论一下, 面试官一般就会说我知道你的想法了, 不过你写个最简单的就好了~