#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <stdexcept>
#include <cassert>

using namespace std;

struct pt_element {
    virtual string to_string() const = 0;
    virtual ~pt_element() {}
};

struct term : public pt_element {
};

struct variable : public term {
    string name;

    variable(string n) : name(n) {}
    string to_string() const { return name; }
};

struct constant : public term {
    string val;

    constant(string v) : val(v) {} 
    string to_string() const { return val; }
};

struct parameter : public term {
    string val;

    parameter(string v) : val(v) {}

    string to_string() const {
        return("?"+val);
    }
};

struct pred_base : public pt_element {
    virtual pred_base& attach(pred_base*,bool conj=true)=0;
    virtual string to_string() { return ""; };
};

struct pred : public pred_base {
    string name;
    vector<term*> v_term_p;
    pred_base* tailed_by;
    bool tail_conj;
    bool truth; 

    pred(string v,bool t=true) : name(v),truth(t) {}

    string to_string() const {
        stringstream tmp;
        if (!truth) tmp << '~';
        tmp << name << '(';
        vector<term*>::const_iterator cit=v_term_p.begin();
        while(cit != v_term_p.end()) {
            tmp << (*cit)->to_string();
            cit++;
            if (cit != v_term_p.end()) tmp << ",";
        }
        tmp << ")";

        if (true==tail_conj) {
            tmp << " AND ";
        } else {
            tmp << " OR ";
        }

        if (tailed_by!=0) tmp << tailed_by->to_string();

        return tmp.str();
    }

    virtual pred_base& attach(pred_base* pbp,bool conj=true) {
        assert(0==tailed_by);
        tailed_by=pbp;
        tail_conj=conj;
        return *this;
    }

    virtual pred& add_term(term* term_p) {
        v_term_p.push_back(term_p);
        return *this;
    }

    virtual int arity() {
        return v_term_p.size();
    }
};

// corresponds to parenthesized group of (conjuncts of) predicates.
struct pred_group : public pred_base {
    vector<pred_base*> v_pred_p;
    bool truth; 
    pred_base* tailed_by;
    bool tail_conj;

    pred_group(bool truefalse=true) : truth(truefalse) {}

    virtual pred_group& add(pred_base* pbp) {
        v_pred_p.push_back(pbp);
        return *this;
    }

    string to_string() const {
        stringstream tmp;
        if (truth) tmp << '~';
        tmp << '(';
        vector<pred_base*>::const_iterator cit=v_pred_p.begin();
        while(cit != v_pred_p.end()) {
            if (*cit!=0) tmp << (*cit)->to_string();
            cit++;
            if (cit != v_pred_p.end()) tmp << ",";
        }
        tmp << ")";
        return tmp.str();
    }

    virtual pred_base& attach(pred_base* pbp,bool conj=true) {
        assert(0==tailed_by);
        tailed_by=pbp;
        tail_conj=conj;
        return *this;
    }
};

/*
// meant as a container for more or less transformed object tree
struct literalset : public pred_base {
    vector<pred_base*> v_pred_base_p;
    literalset() {}
    virtual literalset& add(pred_base* pgp) {
        v_pred_base_p.push_back(pgp);
        return *this;
    }
    string to_string() const {
        stringstream tmp;
        vector<pred_base*>::const_iterator cit=v_pred_base_p.begin();
        while(cit != v_pred_base_p.end()) {
            tmp << (*cit)->to_string();
            cit++;
            if (cit != v_pred_base_p.end()) tmp << ", ";
        }
        return tmp.str();
    }
};

struct predicate_set : public pt_element {
    vector<pred*> v_pred_p;
    predicate_set() {}
    virtual predicate_set& add(pred* p_p) {
        v_pred_p.push_back(p_p);
        return *this;
    }
    string to_string() const {
        stringstream tmp;
        vector<pred*>::const_iterator cit=v_pred_p.begin();
        while(cit != v_pred_p.end()) {
            tmp << (*cit)->to_string();
            cit++;
            if (cit != v_pred_p.end()) tmp << ", ";
        }
        return tmp.str();
    }
};
*/

class object_tree {
 public:

    pred_base* start;
    pred_base* attachpoint;

    object_tree() {}

    object_tree& set_attachpoint(pred_base* point) {
        attachpoint=point;
        return *this;
    }

    string to_string() const {
        if (0==start) return "";
        return start->to_string();
    }
};

ostream& operator<< (
    ostream& os,
    const pt_element& e
) {
    os << e.to_string();
    return os;
}

ostream& operator<< (
    ostream& os,
    const object_tree& ot
) {
    os << ot.to_string();
    return os;
}