#!/usr/bin/python3
"""Parse boolean exprs without precedence using the shunting-yard algorithm.

Following the pattern of L. Amber O'Hearn's protagonist.tagger.parse.

Interestingly, this seems to support both infix and postfix syntax!
"""
from collections import namedtuple
import re, sys


class Expr:
    def __str__(self):
        return self.template % self

class And(namedtuple('And', ('p', 'q')), Expr):
    arity = 2
    template = '(%s) and (%s)'

class Or(namedtuple('Or', ('p', 'q')), Expr):
    arity = 2
    template = '(%s) or (%s)'

class Not(namedtuple('Not', ('p',)), Expr):
    arity = 1
    template = 'not (%s)'

class Var(namedtuple('Var', ('name',)), Expr):
    template = '%s'


def parse(s):
    return parse_tokens(tokenize(s))

def tokenize(s):
    # XXX ignores unsyntactic characters
    return re.compile(r'[()] | \w+', re.X).findall(s)

class ParseException(Exception):
    pass

def parse_tokens(tokens):
    rands, rators = [], []      # operands, operators
    ops = {'and': And, 'or': Or, 'not': Not}
    
    def rate():                 # operate!
        if not rators:
            raise ParseException('Not enough operators', tokens, rands, rators)

        op = ops[rators.pop()]
        if len(rands) < op.arity:
            raise ParseException('Arity', tokens, rands, rators, op)
        rands[-op.arity:] = [op(*rands[-op.arity:])]

    for token in tokens:
        #print(token, rands, rators)
        if token in ops:
            if not rators or rators[-1] == '(' or token == 'not':
                rators.append(token)
            else:
                rate()
                rators.append(token)
        elif token == '(':
            rators.append(token)
        elif token == ')':
            while rators and rators[-1] != '(':
                rate()
            if not rators:
                raise ParseException('Unbalanced parentheses', tokens, rands)
            rators.pop()
        else:
            rands.append(Var(token))

    while rators:
        if rators[-1] == '(':
            raise ParseException('Unbalanced parentheses', tokens, rands)
        rate()

    if len(rands) != 1:
        raise ParseException('Not enough operators', tokens, rands)

    return rands[0]


if __name__ == '__main__':
    print(parse('a and b and not c or d and (e or f) and g'
                if len(sys.argv) == 1 else ' '.join(sys.argv[1:])))