queryparse: use demorgan's laws to simplify parsed expression

2 files changed, 17 insertions, 1 deletions

diff --git a/queryparse.py b/queryparse.py
index 9bab83e..3377803 100644
--- a/queryparse.py
+++ b/queryparse.py
@@ -57,6 +57,21 @@ def encapsulate(pt, op):
 		pt = ParseTree(op, [pt])
 	return pt
 
+def demorgan(pt):
+	if pt.op in LitType:
+		return ParseTree(TokType.NOT, [pt])
+	elif pt.op == TokType.NOT:
+		return pt.l[0]
+	elif pt.op == TokType.OR:
+		pt.op = TokType.AND
+	elif pt.op == TokType.AND:
+		pt.op = TokType.OR
+	else:
+		raise ParseError
+
+	pt.l = [demorgan(x) for x in pt.l]
+	return pt
+
 """
 The parser is implemented like
 
@@ -88,7 +103,7 @@ def e3(lits, l):
 	typ,_ = classify_head(l)
 	if typ == TokType.NOT:
 		pt,l = e4(lits, l[1:])
-		return encapsulate(pt, TokType.NOT), l
+		return demorgan(pt), l
 	return e4(lits, l)
 
 def e2(lits, l):
diff --git a/test/t_queryparse.py b/test/t_queryparse.py
index df21639..3cf5dcb 100755
--- a/test/t_queryparse.py
+++ b/test/t_queryparse.py
@@ -18,3 +18,4 @@ f(["NOT", "[", "x", "y", "z", "]"])
 f(["x", "y", "NOT", "z", "[", "a", "OR", "b", "]", "c"])
 f(["x", "y", "z", "OR", "NOT", "x", "a", "z"])
 f(["~~internal-*", "~-Application*", "NOT", "~~*xyz*"])
+f(["NOT", "[", "x", "y", "z", "OR", "x", "a", "]", "b"])