README.md

• Attempt eval first, and then try satisfiable.
• Download eval.c and satisfiable.c to your machine by copy/pasting the code into files with the same name.
• Compile using dcc -o eval eval.c and dcc -o satisfiable satisfiable.c respectively.
• Instructions, including the problem statement and how to run each program, are given in each file.
• Good luck!

eval.c

#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
/* Feel free to add libraries, if you want. */

/**
 * A boolean expression is one involving boolean values (true, false) and
 * boolean operators (AND, OR, NOT). As an example, "true OR false" is a simple
 * example of a boolean expression.
 *
 * The exact definitions of these boolean operators are:
 *
 *   - The expression "a AND b" is true if a and b both evaluate to true,
 *     and is false otherwise.
 *
 *   - The expression "a OR b" is false if a and b both evaluate to false,
 *     and is true otherwise.
 *
 *   - The expression "NOT a" negates the value of a -- that is, "NOT false"
 *     becomes true, and "NOT true" becomes false.
 *
 * Per the definitions, the expression "true OR false" evaluates to true.
 *
 *
 * Here is one way to represent these boolean expressions as compact strings:
 *
 *   - Write the boolean value true as T, and the boolean value false as F.
 *
 *   - T and F are valid boolean expressions.
 *
 *   - We write "a AND b" as &ab, where a and b are themselves boolean expressions.
 *
 *   - We write "a OR b" as |ab, where a and b are themselves boolean expressions.
 *
 *   - We write "NOT a" as !a, where a is itself a boolean expression.
 *
 * Here are a few examples of how we can represent some boolean expressions like this,
 * some possibly with multiple representations (all of which are valid):
 *
 *   - "true OR false"                 becomes  |TF
 *
 *   - "true AND false AND true"       becomes  &T&FT or &&TFT
 *
 *   - "NOT (false AND true) OR true"  becomes  |!&FTT
 *
 *   - "true AND (NOT true)"           becomes  &T!T
 *
 *
 * Given a boolean expression in this format, evaluate it. That is, determine
 * whether it evaluates to true or false, and return that value.
 * You can assume that all inputs to this function are valid.
 */
bool eval(char *expr) {
    /* TODO: Implement me! */
    return true;
}


/**
 * If you want to run the sample test cases, use ./eval.
 * If you want to input your own test case, use ./eval [expression].
 */
int main(int argc, char *argv[]) {
    if (argc == 1) {
        assert(eval("|TF") == true);
        assert(eval("&T&FT") == false);
        assert(eval("&&TFT") == false);
        assert(eval("|!&FTT") == true);
        assert(eval("&T!T") == false);

        printf("If your program printed this message, "
               "you have passed the sample tests.\nMake sure you do your "
               "own testing though!\n");
    } else if (argc >= 2) {
        printf(eval(argv[1]) ? "true" : "false");
    }

    return 0;
}

satisfiable.c

#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
/* Feel free to add libraries, if you want. */

/**
 * Consider the same boolean expression scheme as used in the previous exercise,
 * but now with an added twist: boolean variables. Up to 4 different kinds of
 * variables from the set {a, b, c, d} may appear in expressions now, and each
 * variable can be treated as true or false independently.
 *
 * As an example, &ab represents the expression "a AND b". This expression is true
 * when a and b are both true.
 *
 *
 * Call any expression satisfiable if we can pick values for its variables such
 * that the expression evaluates to true. We saw that &ab is satisfiable. However,
 * not all expressions are: &a!a is always false, and so is not satisfiable.
 *
 * Here are a few more examples of satisfiable and unsatisfiable expressions:
 *
 *   - The expression &TT is satisfiable: it is always true.
 *
 *   - The expression |a!a is satisfiable: any value of a makes it true.
 *
 *   - The expression &T&b!c is satisfiable: when b is true and c is false,
 *     the expression is true. Note that this expression contains both
 *     variables and plain true/false values!
 *
 *   - The expression &b&|!a!c&|cd|!d!a is satisfiable: when a is false,
 *     b is true, c is true and d is false, the expression is true.
 *
 *   - The expression &a&|!a!c&|cb|!b!a is not satisfiable: this is a bit
 *     tedious/hard to check yourself, though.
 *
 *
 * Given a boolean expression in this extended format, determine if it is
 * satisfiable. You do not have to show/remember the choice, if it exists:
 * you should return true if it can be made true, and false otherwise.
 * As before, you can assume all inputs to this function are valid, and that
 * all variables that appear in the expression are one of {a, b, c, d}.
 */
bool satisfiable(char *expr) {
    /* TODO: Implement me! */
    return true;
}


/**
 * If you want to run the sample test cases, use ./satisfiable.
 * If you want to input your own test case, use ./satisfiable [expression].
 */
int main(int argc, char *argv[]) {
    if (argc == 1) {
        assert(satisfiable("&ab") == true);
        assert(satisfiable("&a!a") == false);
        assert(satisfiable("&TT") == true);
        assert(satisfiable("|a!a") == true);
        assert(satisfiable("&T&b!c") == true);
        assert(satisfiable("&b&|!a!c&|cd|!d!a") == true);
        assert(satisfiable("&a&|!a!c&|cb|!b!a") == false);

        /* Examples from the previous exercise should work too. */
        assert(satisfiable("|TF") == true);
        assert(satisfiable("&T&FT") == false);
        assert(satisfiable("&&TFT") == false);
        assert(satisfiable("|!&FTT") == true);
        assert(satisfiable("&T!T") == false);

        printf("If your program printed this message, "
               "you have passed the sample tests.\nMake sure you do your "
               "own testing though!\n");
    } else if (argc >= 2) {
        printf(satisfiable(argv[1]) ? "Satisfiable" : "Not satisfiable");
    }

    return 0;
}