Please solve logic.cpp in c++ using possibilities.rkt, logic.h, and testLogic.cpp

Please leave a comment if you need more information to solve logic.cpp

possibilities.rkt

	#lang racket
	(define (print-possibilities unchosen-vars chosen-vars)
	(cond
	[(empty? unchosen-vars)
	;; base case: unchosen-vars is empty (we've chosen everything)
	;; print out the current chosen-vars
	(displayln (reverse chosen-vars))]
	[else
	;; recursive case: unchosen-vars is nonempty
	;; take one var out of unchosen-vars, and put it into chosen vars
	;; (trying each possibility)
	;; to extract the first thing in the list, we use first
	(define var (first unchosen-vars))
	;; to get everything except the first element, use rest
	(define rest-of-vars (rest unchosen-vars))
	;; try the tree possibilities for the var
	;; cons adds an element to the front of a list (and it also makes pairs)
	(print-possibilities rest-of-vars (cons `(,var "A") chosen-vars)) #| try A |#
	(print-possibilities rest-of-vars (cons `(,var "B") chosen-vars)) #| try B |#
	(print-possibilities rest-of-vars (cons `(,var "C") chosen-vars)) #| try C |# ]))
	(define (print-possibilities-prettier vars)
	(print-possibilities vars '()))
	;; initially, everything is unchosen and nothing is chosen
	(print-possibilities '("x" "y" "z") '())
	;; could also call the prettier version with:
	;; (print-possibilities-prettier '("x" "y" "z"))

================================================

logic.h

#ifndef LOGIC_H #define LOGIC_H

#include #include #include #include #include #include

// combine the elements of two sets into a new set template std::set operator+(const std::set& a, const std::set& b) { std::set res; std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::inserter(res, res.begin())); return res; }

class Var;

// Base class for logical formulae class Formula { public: // evaluates the Formula with a given assignment of Vars to values virtual bool evaluate(std::map var2Val) = 0; // returns all the variables that exist in the Formula virtual std::set extractVarNames() = 0; virtual ~Formula() = default; };

// You can And together two logical formulae class And : public Formula { public: And(std::shared_ptr lhs, std::shared_ptr rhs); bool evaluate(std::map var2Val) override; std::set extractVarNames() override;

private: // you can And together two formulae and produce a bigger Formula! // lhs: left-hand side std::shared_ptr lhs; std::shared_ptr rhs; };

// You can Or together two logical formulae class Or : public Formula { public: Or(std::shared_ptr lhs, std::shared_ptr rhs); bool evaluate(std::map var2Val) override; std::set extractVarNames() override;

private: std::shared_ptr lhs; std::shared_ptr rhs; };

// You can negate any logical formula class Not : public Formula { public: Not(std::shared_ptr inside); bool evaluate(std::map var2Val) override; std::set extractVarNames() override;

private: std::shared_ptr inside; };

// A single propositional variable by itself is a logical formula // You can use Vars inside of bigger formulae class Var : public Formula { public: Var(std::string name); bool evaluate(std::map var2Val) override; std::set extractVarNames() override;

bool operator<(const Var& other) const; friend std::ostream& operator<<(std::ostream& os, const Var& v);

private: std::string name; };

// Given a formula f, compute all the ways to make it true // each map in the set is an assignment of variables to values std::set> satSolve(Formula& f);

// Helper function for satSolve that does the heavy lifting void satSolveHelper(Formula& f, std::set remainingVars, std::map choicesForVars, std::set>& satisfyingSolutions);

#endif /* LOGIC_H */

======================================================

logic.cpp

#include "logic.h" using namespace std;

// Stuff I've implemented for you (don't touch pls)

And::And(shared_ptr lhs, shared_ptr rhs) : lhs(lhs), rhs(rhs) {}

set And::extractVarNames() { return lhs->extractVarNames() + rhs->extractVarNames(); }

Or::Or(shared_ptr lhs, shared_ptr rhs) : lhs(lhs), rhs(rhs) {}

set Or::extractVarNames() { return lhs->extractVarNames() + rhs->extractVarNames(); }

Not::Not(shared_ptr inside) : inside(inside) {}

set Not::extractVarNames() { return inside->extractVarNames(); }

Var::Var(string name) : name(name) {}

set Var::extractVarNames() { return {name}; }

bool Var::operator<(const Var& other) const { return name < other.name; }

ostream& operator<<(ostream& os, const Var& v) { os << v.name; return os; }

// Stuff for you to implement

// FIXME: implement And's evaluation method // How can you use each piece of the And to determine // if the whole thing is true or false? // This will be a recursive method--first evaluate lhs & rhs bool And::evaluate(map var2Val) { return true; // fix this }

// FIXME: implement Or's evaluation method

// FIXME: implement Not's evaluation method

// FIXME: implement Var's evaluation method

// How can you turn a variable into a boolean? // (This is the base case, so no recursive calls needed here)

// Given a formula f, try all the possibilities for the variables, and // return all the ways to make it true. set> satSolve(Formula& f) { set> solutions;

// FIXME: call satSolveHelper with the proper values // use the solutions variable to store every solution you find

return solutions; }

// FIXME: implement this function to recursively find all the satisfying // solutions for a Formula f. You will do this by trying both true and false for // every variable in the formula. // // Explanations of the other parameters: // - remainingVars: the variables that you have not yet picked values for // - choicesForVars: the variables that you *have* picked values for (and // those values) // - satisfyingSolutions: a set of all the different variable choices // (represented as a map) // that make the Formula f true. This is a reference, // so you'll extend it each time you find a new // solution. void satSolveHelper(Formula& f, set remainingVars, map choicesForVars, set>& satisfyingSolutions) { // Base case: There are no remaining vars. This means you've made choices // for everybody, and now it's time to see if those choices paid // off. Check if f is true when evaluated using our current // choicesForVars. If it is, add our current choicesForVars to // the satisfyingSolutions.

// Recursive case: There is at least one Var to pick a value for. // Try both true and false for it recursively. // Steps to follow in this case: // - extract one Var (call it nextChoice) out of the remaing Vars // (remainingVars.begin() is a good way to get a Var out of a set) // - create a new set of remaining variables, removing the one you just // chose for your nextChoice variable // - recursively try to solve the Formula f using nextChoice set to true // - recursively try to solve the Formula f using nextChoice set to false }

============================================================

testLogic.cpp

#include using namespace std;

#include "logic.h" #include "testing.h"

void testEval(); void testSAT0(); void testSAT1(); void testSAT2(); void testSAT3();

int main() { testEval(); testSAT0(); testSAT1(); testSAT2(); testSAT3();

return 0; }

// helper functions to make Formulas shared_ptr _And(shared_ptr lhs, shared_ptr rhs) { return make_shared(lhs, rhs); }

shared_ptr _Or(shared_ptr lhs, shared_ptr rhs) { return make_shared(lhs, rhs); }

shared_ptr _Not(shared_ptr inside) { return make_shared(inside); }

shared_ptr _Var(const string& s) { return make_shared(s); }

// helper function to print all the solutions our satSolve function finds void printSolutions(set>& solutions) { int i = 1; for (auto m : solutions) { cout << "Solution " << i << ": ";

for (auto varValPair : m) { cout << " " << varValPair.first << " -> " << varValPair.second << endl; }

i++; } cout << endl; }

// the actual tests:

void testEval() { // p_or_q_and_not_r represents (p (q r) shared_ptr p = make_shared("p"); shared_ptr q = make_shared("q"); shared_ptr r = make_shared("r"); shared_ptr not_r = make_shared(r); shared_ptr q_and_not_r = make_shared(q, not_r); shared_ptr p_or_q_and_not_r = make_shared(p, q_and_not_r);

map var2Val1 = {{*p, false}, {*q, true}, {*r, false}}; // try evaluating the formula with p = false, q = true, and r = false assertTrue(p_or_q_and_not_r->evaluate(var2Val1) == true, "false || (true && !false)");

map var2Val2 = {{*p, false}, {*q, false}, {*r, false}}; // try evaluating the formula with p = false, q = false, and r = false assertTrue(p_or_q_and_not_r->evaluate(var2Val2) == false, "false || (false && !false)"); cout << endl; }

// p void testSAT0() { cout << "Test 0" << endl; cout << "======" << endl;

shared_ptr f = _Var("p"); set> solutions = satSolve(*f);

printSolutions(solutions); }

// p q void testSAT1() { cout << "Test 1" << endl; cout << "======" << endl;

shared_ptr f = _Or(_Not(_Var("p")), _Var("q")); set> solutions = satSolve(*f);

printSolutions(solutions); }

// (p (q r)) (p (q r)) void testSAT2() { cout << "Test 2" << endl; cout << "======" << endl;

shared_ptr f = _Or(_And(_Var("p"), _And(_Var("q"), _Not(_Var("r")))), _And(_Var("p"), _And(_Not(_Var("q")), _Not(_Var("r"))))); set> solutions = satSolve(*f);

printSolutions(solutions); }

// (p q) ((r s) (t u)) void testSAT3() { cout << "Test 3" << endl; cout << "======" << endl;

shared_ptr f = _Or( _Or(_Var("p"), _Var("q")), _Or(_Or(_Not(_Var("r")), _Var("s")), _And(_Var("t"), _Not(_Var("u"))))); set> solutions = satSolve(*f);

printSolutions(solutions); }