algorithm - 使用二叉树解决字母表达式以获得句子

Question

我正在尝试解决字母表达式以获得有效的句子。

输入和输出的示例是：-

输入

实际的：

(((​"​one​"​ . ​"​two​"​) | ​"​twelve​"​) . (​"​zero​"​ | ​"​o​"​) . ​"​six​"​)

代币化：

['(', '(', '(', 'one', '.', 'two', ')', '|', 'twelve', ')', '.', 
 '(', 'zero', '|', 'o', ')', '.', 'six', ')']

输出

• 一二零六

• 一二六六

• 十二点六

运营商

• ()-必需的分组运算符
• []-可选分组运算符
• .-连接连接运算符
• |-或连接运算符

运算符的.优先级确实高于|运算符。我无法理解我应该如何去做。（我想用 Python 写代码）

标签： algorithmdata-structuresbinary-treebinary-search-treegraph-algorithm

Answer 1

我假设您已经设法标记输入。然后我建议作为第二步从令牌构建一棵树，以便以下输入：

(((​"​one​"​ . ​"​two​"​) | ​"​twelve​"​) . (​"​zero​"​ | ​"​o​"​) . ​"​six​"​)

...将成为以下树：

请注意，您可以[...]将 OR 运算符与None元素结合使用（这不会在最终字符串中产生任何内容）来实现可选单词（包含在 中）。例如["six"]，将被解释为(None|"six")，在树中将是：

使用树，您可以使用递归来查找可能的字符串。每个递归调用都会返回一个可能的字符串列表（可能只有一个）。如果孩子属于.(AND) 操作，则为孩子找到的所有字符串列表必须组合为笛卡尔积。如果它们属于|(OR) 操作，则这些列表应该只是连接起来（因为任何孩子的所有可能的字符串对于父母来说都是可能的）。

以下是一些可能有用的代码：

import itertools
import re

# subclass list just to distinguish between arguments of a "." or "|" operator
class OrList(list): # for "|" operator arguments
    pass

class AndList(list): # for "." operator arguments
    pass

def parse(tokens):
    # helper function to conditionally either append-to or extend a list
    def add(lst, factor):
        if type(factor) == type(lst):
            lst.extend(factor)
        else:
            lst.append(factor)
        return lst

    # helper function to conditionally return the given list or its only element
    def simplify(lst):
        if isinstance(lst, OrList): # remove duplicates
            for i in range(len(lst)-1,-1,-1):
                if lst.index(lst[i]) < i:
                    del lst[i]
        return lst if len(lst) > 1 else lst[0]

    it = iter(tokens + [""])

    def recur(end):
        terms = OrList()
        factors = AndList()
        token = None
        while token != end:
            token = next(it)
            if token[0] == '"':
                add(factors, token[1:-1]) # remove the quotes
            elif token == "(":
                add(factors, recur(")"))
            elif token == "[": # encode [expr] as if it were: (|expr)
                add(factors, add(OrList([None]), recur("]")))
            else:
                raise ValueError("Expected expression, got {}".format(token))
            token = next(it)
            if token != end and token not in ".|":
                raise ValueError("Expected operator, got {}".format(token))
            if token == "|" or token == end:
                add(terms, simplify(factors))
                factors = AndList()
        return simplify(terms)

    return recur("")

def validPhrases(node): # returns list of strings
    if isinstance(node, list):
        results = [validPhrases(child) for child in node]
        if isinstance(node, OrList):
            # flatten
            results = list(itertools.chain.from_iterable(results))
        else: # instance of AndList
            # all combinations
            results = [" ".join([s for s in combi if s != None]) 
                    for combi in itertools.product(*results)]
        return list(set(results)) # remove duplicates
    else: # str
        return [node]

def generate(expr):
    # tokenize
    tokens = re.findall(r'"[^"]*"|\S', expr) # don't throw away the quotes yet
    # make a tree in line with precedence rules
    tree = parse(tokens)
    # finally build all possible strings from this tree
    return validPhrases(tree)

expr = '((("one" . "two" | "twelve") . ("zero" | "o")) . "six")'

print(generate(expr))

看到它在repl.it上运行