from enum import Enum

class LitType(Enum):
	TAGGLOB = 2
	TITLEGLOB = 3
	TAG = 9

class TokType(Enum):
	OR = 0
	NOT = 1
	EOF = 5
	AND = 6
	OPEN = 7
	CLOSE = 8

def classify_head(l):
	if len(l) == 0:
		return (TokType.EOF, None)

	s = l[0]
	if s == "OR":
		return (TokType.OR,None)
	elif s == "NOT":
		return (TokType.NOT,None)
	elif s == "[":
		return (TokType.OPEN,None)
	elif s == "]":
		return (TokType.CLOSE,None)
	elif s[:2] == "~~":
		return (LitType.TAGGLOB, s[2:])
	elif s[:2] == "~-":
		return (LitType.TITLEGLOB, s[2:])
	else:
		return (LitType.TAG, s)

class Atom:
	def __str__(self):
		return f'({self.op} "{self.v}")'
	def __init__(self, op, v):
		self.op = op
		self.v = v

class ParseTree:
	def push(self, pt):
		self.l.append(pt)
	def __str__(self):
		s = f'({self.op}'
		for i in self.l:
			s = s + ' ' + str(i)
		return s + ')'
	def __init__(self, op, l):
		self.op = op
		self.l = l

def encapsulate(pt, op):
	if pt.op != op:
		pt = ParseTree(op, [pt])
	return pt

"""
The parser is implemented like

e1 ::= e2 ("OR" e2)*;
e2 ::= e3*;
e3 ::= "NOT"? e4;
e4 ::= TAG | "[" e1 "]";
"""

class ParseError(Exception):
	pass

def e4(l):
	typ,s = classify_head(l)

	if typ == TokType.OPEN:
		pt,l = e1(l[1:])
		typ,_ = classify_head(l)
		if typ != TokType.CLOSE:
			raise ParseError
		return pt,l[1:]
	elif typ in LitType:
		return Atom(typ, s), l[1:]
	else:
		raise ParseError

def e3(l):
	typ,_ = classify_head(l)
	if typ == TokType.NOT:
		pt,l = e4(l[1:])
		return encapsulate(pt, TokType.NOT), l
	return e4(l)

def e2(l):
	pt,l = e3(l)
	try:
		while True:
			pt2,l = e3(l)
			pt = encapsulate(pt, TokType.AND)
			pt.push(pt2)
	except ParseError:
		pass
	return pt,l

def e1(l):
	pt,l = e2(l)
	typ,_ = classify_head(l)

	try:
		while typ == TokType.OR:
			pt2,l = e2(l[1:])
			pt = encapsulate(pt, TokType.OR)
			pt.push(pt2)
			typ,_ = classify_head(l)
	except ParseError:
		pass
	return pt,l

def parse(l):
	x,l = e1(l)
	if l != []:
		raise ParseError
	return x