Reddit Challenge #135 - De Morgan's Law http://redd.it/1qira9

de_morgan.cpp

#include <iostream> // std::cin, std::cout, std::ostream
#include <memory> // std::shared_ptr


/* *************************************
 * Expression
 */

class Expression {

public:
    virtual std::shared_ptr<Expression> simplify() const = 0;

protected:
    virtual void output(std::ostream &out) const = 0;

    friend std::ostream &operator<<(std::ostream &, const Expression &);

};

typedef std::shared_ptr<Expression> ExprPtr;


/* *************************************
 * Variable
 */

class Variable : public Expression {

protected:
    const char *m_Name;

public:
    Variable(const char *name);
    ExprPtr simplify() const;

protected:
    void output(std::ostream &out) const;

};


/* *************************************
 * Negation
 */

class Negation : public Expression {

protected:
    const ExprPtr m_Expr;

public:
    Negation(ExprPtr expr);
    ExprPtr simplify() const;

protected:
    void output(std::ostream &out) const;

 };


/* *************************************
 * Operators
 */

class Operator : public Expression {

protected:
    const ExprPtr m_Left;
    const ExprPtr m_Right;

public:
    Operator(ExprPtr left, ExprPtr right);
    virtual ExprPtr inverse() const = 0;

};


class And : public Operator {

public:
    And(ExprPtr left, ExprPtr right);
    ExprPtr simplify() const;
    ExprPtr inverse() const;

protected:
    void output(std::ostream &out) const;

};


class Or : public Operator {

public:
    Or(ExprPtr left, ExprPtr right);
    ExprPtr simplify() const;
    ExprPtr inverse() const;

protected:
    void output(std::ostream &out) const;

};


/* *************************************
 * Expression
 */

std::ostream &operator<<(std::ostream &out, const Expression &expr)
{
    expr.output(out);
    return out;
}


/* *************************************
 * Variable
 */

Variable::Variable(const char *name)
  : m_Name(name)
{}

ExprPtr Variable::simplify() const
{
    return ExprPtr(new Variable(m_Name));
}

void Variable::output(std::ostream &out) const
{
    out << m_Name;
}


/* *************************************
 * Negation
 */

Negation::Negation(ExprPtr expr)
  : m_Expr(expr)
{}

ExprPtr Negation::simplify() const
{
    ExprPtr expr = m_Expr->simplify();
    {
        /* Apply De Morgan's law */
        Operator *op = dynamic_cast<Operator*>(expr.get());
        if(op != 0)
            return op->inverse()->simplify();
    }
    {
        /* NOT NOT a = a */
        Negation *neg = dynamic_cast<Negation*>(expr.get());
        if(neg != 0)
            return neg->m_Expr;
    }
    return ExprPtr(new Negation(expr));
}

void Negation::output(std::ostream &out) const
{
    out << "NOT (" << *m_Expr << ")";
}


/* *************************************
 * Operators
 */

Operator::Operator(ExprPtr left, ExprPtr right)
  : m_Left(left), m_Right(right)
{}


And::And(ExprPtr left, ExprPtr right)
  : Operator(left, right)
{}

ExprPtr And::simplify() const
{
    return ExprPtr(new And(m_Left->simplify(), m_Right->simplify()));
}

ExprPtr And::inverse() const
{
    ExprPtr left(new Negation(m_Left));
    ExprPtr right(new Negation(m_Right));
    return ExprPtr(new Or(left, right));
}

void And::output(std::ostream &out) const
{
    out << "(" << *m_Left << " AND " << *m_Right << ")";
}


Or::Or(ExprPtr left, ExprPtr right)
  : Operator(left, right)
{}

ExprPtr Or::simplify() const
{
    return ExprPtr(new Or(m_Left->simplify(), m_Right->simplify()));
}

ExprPtr Or::inverse() const
{
    ExprPtr left(new Negation(m_Left));
    ExprPtr right(new Negation(m_Right));
    return ExprPtr(new And(left, right));
}

void Or::output(std::ostream &out) const
{
    out << "(" << *m_Left << " OR " << *m_Right << ")";
}


/* *************************************
 * main
 */

int main()
{
    // Build an expression
    ExprPtr e(new Or(
        ExprPtr(new And(
            ExprPtr(new Negation(
                ExprPtr(new Variable("a"))
            )),
            ExprPtr(new Variable("b"))
        )),
        ExprPtr(new Negation(
            ExprPtr(new Variable("c"))
        ))
    ));

    // Negate it
    ExprPtr ne(new Negation(e));
    std::cout << *ne << "\n" << *ne->simplify() << "\n";

    return 0;
}

expressions.cpp

#include "expressions.h"


/* *************************************
 * Expression
 */

std::ostream &operator<<(std::ostream &out, const Expression &expr)
{
    expr.output(out);
    return out;
}


/* *************************************
 * Variable
 */

Variable::Variable(const char *name)
  : m_Name(name)
{}

ExprPtr Variable::simplify() const
{
    return ExprPtr(new Variable(m_Name));
}

void Variable::output(std::ostream &out) const
{
    out << m_Name;
}


/* *************************************
 * Negation
 */

Negation::Negation(ExprPtr expr)
  : m_Expr(expr)
{}

ExprPtr Negation::simplify() const
{
    ExprPtr expr = m_Expr->simplify();
    {
        /* Apply De Morgan's law */
        Operator *op = dynamic_cast<Operator*>(expr.get());
        if(op != 0)
            return op->inverse()->simplify();
    }
    {
        /* NOT NOT a = a */
        Negation *neg = dynamic_cast<Negation*>(expr.get());
        if(neg != 0)
            return neg->m_Expr;
    }
    return ExprPtr(new Negation(expr));
}

void Negation::output(std::ostream &out) const
{
    out << "NOT (" << *m_Expr << ")";
}


/* *************************************
 * Operators
 */

Operator::Operator(ExprPtr left, ExprPtr right)
  : m_Left(left), m_Right(right)
{}


And::And(ExprPtr left, ExprPtr right)
  : Operator(left, right)
{}

ExprPtr And::simplify() const
{
    return ExprPtr(new And(m_Left->simplify(), m_Right->simplify()));
}

ExprPtr And::inverse() const
{
    ExprPtr left(new Negation(m_Left));
    ExprPtr right(new Negation(m_Right));
    return ExprPtr(new Or(left, right));
}

void And::output(std::ostream &out) const
{
    out << "(" << *m_Left << " AND " << *m_Right << ")";
}


Or::Or(ExprPtr left, ExprPtr right)
  : Operator(left, right)
{}

ExprPtr Or::simplify() const
{
    return ExprPtr(new Or(m_Left->simplify(), m_Right->simplify()));
}

ExprPtr Or::inverse() const
{
    ExprPtr left(new Negation(m_Left));
    ExprPtr right(new Negation(m_Right));
    return ExprPtr(new And(left, right));
}

void Or::output(std::ostream &out) const
{
    out << "(" << *m_Left << " OR " << *m_Right << ")";
}

expressions.h

#ifndef EXPRESSIONS_H
#define EXPRESSIONS_H

#include <iostream> // std::cin, std::cout, std::ostream
#include <memory> // std::shared_ptr


/* *************************************
 * Expression
 */

class Expression {

public:
    virtual std::shared_ptr<Expression> simplify() const = 0;

protected:
    virtual void output(std::ostream &out) const = 0;

    friend std::ostream &operator<<(std::ostream &, const Expression &);

};

typedef std::shared_ptr<Expression> ExprPtr;


/* *************************************
 * Variable
 */

class Variable : public Expression {

protected:
    const char *m_Name;

public:
    Variable(const char *name);
    ExprPtr simplify() const;

protected:
    void output(std::ostream &out) const;

};


/* *************************************
 * Negation
 */

class Negation : public Expression {

protected:
    const ExprPtr m_Expr;

public:
    Negation(ExprPtr expr);
    ExprPtr simplify() const;

protected:
    void output(std::ostream &out) const;

 };


/* *************************************
 * Operators
 */

class Operator : public Expression {

protected:
    const ExprPtr m_Left;
    const ExprPtr m_Right;

public:
    Operator(ExprPtr left, ExprPtr right);
    virtual ExprPtr inverse() const = 0;

};


class And : public Operator {

public:
    And(ExprPtr left, ExprPtr right);
    ExprPtr simplify() const;
    ExprPtr inverse() const;

protected:
    void output(std::ostream &out) const;

};


class Or : public Operator {

public:
    Or(ExprPtr left, ExprPtr right);
    ExprPtr simplify() const;
    ExprPtr inverse() const;

protected:
    void output(std::ostream &out) const;

};

#endif

main.cpp

#include "expressions.h"
#include "parser.h"


/* *************************************
 * main
 */

int main()
{
    // Read expressions
    char buffer[4096];
    while(std::cin.good())
    {
        std::cin.getline(buffer, 4096);
        if(buffer[0] == '\0')
            break;
        ExprPtr expr = parse(buffer);
        std::cout << *ExprPtr(new Negation(expr))->simplify() << "\n";
    }

    return 0;
}

Makefile

CC=gcc
CXX=g++
CXXFLAGS=-std=c++11

.PHONY: all small full clean

all: small full
small: small.exe
full: full.exe

small.exe: de_morgan.o
	$(CXX) -o $@ $^

full.exe: expressions.o main.o parser.o
	$(CXX) -o $@ $^

%.o: %.cpp
	$(CXX) $(CXXFLAGS) -c -o $@ $<

clean:
	$(RM) de_morgan.o expressions.o main.o parser.o

distclean: clean
	$(RM) full.exe small.exe

parser.cpp

#include <cctype>
#include <cstring>

#include "parser.h"


/* *************************************
 * Lexer
 */
 
class Lexer {

protected:
    const std::string m_String;
    size_t m_Pos;
    std::string m_Unlexed;

public:
    Lexer(const std::string &str);
    std::string lex();
    void unlex(const std::string &t);

protected:
    bool specialchar(char c);

};

Lexer::Lexer(const std::string &str)
  : m_String(str), m_Pos(0)
{}

std::string Lexer::lex()
{
    if(m_Unlexed.size() > 0)
    {
        std::string t = m_Unlexed;
        m_Unlexed = "";
        return t;
    }

    while(m_Pos < m_String.size() and isspace(m_String[m_Pos]))
        m_Pos++;
    if(m_Pos >= m_String.size())
        return "";

    if(specialchar(m_String[m_Pos]))
        return std::string(1, m_String[m_Pos++]);
    else
    {
        size_t start = m_Pos++;
        while(m_Pos < m_String.size() and
              !isspace(m_String[m_Pos]) and
              !specialchar(m_String[m_Pos]))
            m_Pos++;
        return m_String.substr(start, m_Pos - start);
    }
}

void Lexer::unlex(const std::string &t)
{
    m_Unlexed = t;
}

bool Lexer::specialchar(char c)
{
    return c == '(' or c == ')';
}


/* *************************************
 * Parser
 */

class Parser {

protected:
    const std::unique_ptr<Lexer> m_Lexer;

public:
    Parser(std::unique_ptr<Lexer>&& lexer);
    Parser(const std::string &str);

    ExprPtr parse(bool go_on=true);
    ExprPtr parse_more(ExprPtr left);

};

Parser::Parser(std::unique_ptr<Lexer>&& lexer)
  : m_Lexer(std::move(lexer))
{}

Parser::Parser(const std::string &str)
  : m_Lexer(new Lexer(str))
{}

ExprPtr Parser::parse(bool go_on)
{
    std::string token = m_Lexer->lex();
    ExprPtr expr;
    if(token == "NOT")
        expr = ExprPtr(new Negation(parse(false)));
    else if(token == "(")
    {
        expr = parse();
        if(m_Lexer->lex() != ")")
        {
            std::cerr << "Missing \")\"\n";
            exit(1);
        }
    }
    else if(token == "AND" or token == "OR" or token == ")")
    {
        std::cerr << "Unexpected token \"" << token << "\"\n";
        exit(1);
    }
    else
        expr = ExprPtr(new Variable(strdup(token.c_str()))); // Memory leak

    if(go_on)
        return parse_more(expr);
    else
        return expr;
}

ExprPtr Parser::parse_more(ExprPtr left)
{
    std::string token = m_Lexer->lex();
    if(token == "AND")
        return parse_more(ExprPtr(new And(left, parse())));
    else if(token == "OR")
        return parse_more(ExprPtr(new Or(left, parse())));
    else if(token == ")")
    {
        m_Lexer->unlex(token);
        return left;
    }
    else if(token == "")
        return left;
    else
    {
        std::cerr << "Unexpected token \"" << token << "\"\n";
        exit(1);
    }
}


ExprPtr parse(const std::string &str)
{
    Parser parser(str);
    return parser.parse();
}

parser.h

#include "expressions.h"


ExprPtr parse(const std::string &str);