A parser for simple boolean search expressions. Demo: https://repl.it/repls/AcceptableTornMath.

search.py

"""A parser for boolean search expressions.

This parser understands three types of tokens:

    1. AND <expression> <expression>
    2. OR <expression> <expression>
    3. <string>

All strings must be encapsulated in double quotes. The parser converts the
search expression into a set of lists containing all possible combinations of
the search strings.

Example:

    Search for all ThinkPad T410, T420, and T430 models, including the
    "performance" and "slim" models.

    Expression: AND AND "t" OR "410" OR "420" "430" OR "" OR "p" "s"
    Result:     [['t', '410', ''], ['t', '410', 'p'], ['t', '410', 's'],
                 ['t', '420', ''], ['t', '420', 'p'], ['t', '420', 's'],
                 ['t', '430', ''], ['t', '430', 'p'], ['t', '430', 's']]
"""


def parse(nodes):
    root = nodes.pop(0)
    if root.startswith('"') and root.endswith('"'):
        return [[root[1:-1]]], nodes

    lhs, nodes = parse(nodes)
    rhs, nodes = parse(nodes)
    result = []
    if root == 'AND':
        result = [i + j for i in lhs for j in rhs]
    elif root == 'OR':
        result = lhs + rhs

    return result, nodes