My first stab at a DeMorgans visitor + tests

DeMorgansExprVisitor.cs

// ---------------------------------------------------------------
// Uses DeMorgans Law of formal logic to remove NOT's from the AST
// (This is advantageous when running queries against Lucene)
// http://en.wikipedia.org/wiki/De_Morgans_laws
// ---------------------------------------------------------------

public class DeMorgansExprVisitor : IExprVisitor<Expr>
{
    int _notCount;

    bool Negate
    {
        get { return (_notCount%2) == 1; }
    }

    public Expr Visit(AndExpr expr)
    {
        Expr lhs = expr.LHS.Accept(this);
        Expr rhs = expr.RHS.Accept(this);

        return Negate ? (Expr) new OrExpr(lhs, rhs) : new AndExpr(lhs, rhs);
    }

    public Expr Visit(OrExpr expr)
    {
        Expr lhs = expr.LHS.Accept(this);
        Expr rhs = expr.RHS.Accept(this);

        return Negate ? (Expr) new AndExpr(lhs, rhs) : new OrExpr(lhs, rhs);
    }

    public Expr Visit(NotExpr expr)
    {
        try
        {
            _notCount++;

            return expr.Expression.Accept(this);
        }
        finally
        {
            _notCount--;
        }
    }

    public Expr Visit(Group expr)
    {
        return expr.Expression.Accept(this);
    }

    public Expr Visit(TerminalExpr expr)
    {
        return Negate ? new TerminalExpr(expr.Identifier, GetInverseOfOperator(expr.Operator), expr.Operand) : expr;
    }

    public Expr Visit(Empty expr)
    {
        return expr;
    }

    static Operator GetInverseOfOperator(Operator op)
    {
        switch (op)
        {
            case Operator.Is:
                return Operator.IsNot;
            case Operator.IsNot:
                return Operator.Is;
            case Operator.In:
                return Operator.NotIn;
            case Operator.NotIn:
                return Operator.In;
            case Operator.Contains:
                return Operator.DoesNotContain;
            case Operator.DoesNotContain:
                return Operator.Contains;
            case Operator.Eq:
                return Operator.NotEq;
            case Operator.NotEq:
                return Operator.Eq;
            case Operator.Gt:
                return Operator.Lte;
            case Operator.Gte:
                return Operator.Lt;
            case Operator.Lt:
                return Operator.Gte;
            case Operator.Lte:
                return Operator.Gt;
            default:
                throw new Exception("Unexpected operator: " + op);
        }
    }
}

public class DeMorgansVisitorTests
{
    readonly DeMorgansExprVisitor visitor = new DeMorgansExprVisitor();

    [Fact]
    public void no_nots_retains_same_structure()
    {
        TerminalExpr a = TerminalExpr.Eq("t1", "v1");
        TerminalExpr b = TerminalExpr.Lt("t2", "v2");
        TerminalExpr c = TerminalExpr.Gte("t3", "v3");
        TerminalExpr d = TerminalExpr.Contains("t4", "v4");

        var original = new AndExpr(new OrExpr(a, b), new OrExpr(c, d));

        Assert.Equal(original, original.Accept(visitor));
    }

    [Theory]
    [InlineData(Operator.Eq, Operator.NotEq)]
    [InlineData(Operator.NotEq, Operator.Eq)]
    [InlineData(Operator.Gt, Operator.Lte)]
    [InlineData(Operator.Gte, Operator.Lt)]
    [InlineData(Operator.Lt, Operator.Gte)]
    [InlineData(Operator.Lte, Operator.Gt)]
    [InlineData(Operator.Contains, Operator.DoesNotContain)]
    [InlineData(Operator.DoesNotContain, Operator.Contains)]
    [InlineData(Operator.Is, Operator.IsNot)]
    [InlineData(Operator.IsNot, Operator.Is)]
    [InlineData(Operator.In, Operator.NotIn)]
    [InlineData(Operator.NotIn, Operator.In)]
    public void not_single_value_with_operator_translated_to_expected_operator(Operator originalOp, Operator expectedOp)
    {
        var input = new NotExpr(new TerminalExpr("t", originalOp, new Value(new QuotedValue("v"))));
        var expected = new TerminalExpr("t", expectedOp, new Value(new QuotedValue("v")));
        Assert.Equal(expected, input.Accept(visitor));
    }

    [Fact]
    public void not_and_becomes_or()
    {
        var input = new NotExpr(new AndExpr(TerminalExpr.Eq("t1", "v1"), TerminalExpr.Eq("t2", "v2")));
        var expected = new OrExpr(TerminalExpr.NotEq("t1", "v1"), TerminalExpr.NotEq("t2", "v2"));
        Assert.Equal(expected, input.Accept(visitor));
    }

    [Fact]
    public void not_or_becomes_and()
    {
        var input = new NotExpr(new OrExpr(TerminalExpr.Eq("t1", "v1"), TerminalExpr.Eq("t2", "v2")));
        var expected = new AndExpr(TerminalExpr.NotEq("t1", "v1"), TerminalExpr.NotEq("t2", "v2"));
        Assert.Equal(expected, input.Accept(visitor));
    }

    [Fact]
    public void not_within_a_not_is_just_the_term()
    {
        var input = new NotExpr(new NotExpr(TerminalExpr.Eq("t", "v")));
        TerminalExpr expected = TerminalExpr.Eq("t", "v");
        Assert.Equal(expected, input.Accept(visitor));
    }

    [Fact]
    public void not_within_not_within_not_behaves_like_single_not()
    {
        var input = new NotExpr(new NotExpr(new NotExpr(TerminalExpr.Contains("t", "v"))));
        TerminalExpr expected = TerminalExpr.DoesNotContain("t", "v");
        Assert.Equal(expected, input.Accept(visitor));
    }

    [Fact]
    public void two_levels_of_not_returns_expected()
    {
        TerminalExpr t1 = TerminalExpr.Contains("t", "v");
        TerminalExpr t2 = TerminalExpr.Lt("t1", "v1");
        var notAnd = new NotExpr(new AndExpr(t1, t2));

        TerminalExpr t3 = TerminalExpr.Gte("t", "v");
        TerminalExpr t4 = TerminalExpr.Eq("t1", "v1");
        var notOr = new NotExpr(new OrExpr(t3, t4));

        var input = new NotExpr(new AndExpr(notOr, notAnd));

        var expAnd = new AndExpr(t1, t2);
        var expOr = new OrExpr(t3, t4);
        var expected = new OrExpr(expOr, expAnd);

        Assert.Equal(expected, input.Accept(visitor));
    }

    [Fact]
    public void not_two_levels_deep_correctly_reverses_infix_ops_and_term_operators()
    {
        TerminalExpr t1 = TerminalExpr.Contains("t", "v");
        TerminalExpr t2 = TerminalExpr.Lt("t1", "v1");
        var notAnd = new NotExpr(new AndExpr(t1, t2));

        TerminalExpr t3 = TerminalExpr.Gte("t", "v");
        TerminalExpr t4 = TerminalExpr.Eq("t1", "v1");
        var notOr = new NotExpr(new OrExpr(t3, t4));

        var input = new AndExpr(notOr, notAnd);

        TerminalExpr notLiked = TerminalExpr.DoesNotContain("t", "v");
        TerminalExpr e1 = TerminalExpr.Gte("t1", "v1");
        var expOr = new OrExpr(notLiked, e1);

        TerminalExpr e3 = TerminalExpr.Lt("t", "v");
        TerminalExpr e4 = TerminalExpr.NotEq("t1", "v1");
        var expAnd = new AndExpr(e3, e4);

        var expected = new AndExpr(expAnd, expOr);

        Assert.Equal(expected, input.Accept(visitor));
    }
}