Given an boolean expression decide where to place parenthesis so it becomes true

Question

I am thinking of creating a program that, given an boolean expression, for example, true and false xor true places parenthesis around the "operations" and returns the new equations that have true as a result. How would I do this, from where should I start? Is there a small algorithm in Dynamic Programming I should search for?

Answer 1

One observation here is that if you end up with a fully-parenthesized expression, there will be some top-level operator in the overall expression. Based on that operator, the entire expression will evaluate to true if one of a number of different cases hold. For example, if the top-level operator is an AND, then the expression is true if the subexpressions to the left and right of the AND are true. If the top-level operation is an OR, the whole expression evaluates to true if either the left or right subexpressions evaluate to true. If the top-level operator is a NOT, the entire expression is true if the subexpression of the NOT is false.

You can imagine a top-down recursive algorithm that works as follows: for each operator, temporarily assume it's the top-level operator and recursively determine whether the subexpressions in question can have the appropriate truth values. If so, the formula can be made true. If not, it can't.

The number of possible subexpression / truth value pairs here is O(n²), since each subexpression is just a subarray of the original expression and there are only O(n²) of them. Therefore, there are going to be a lot of overlapping subproblems, so you could either compute the result top-down with memoization or bottom-up wou dynamic programming.

This seemed like a really fun problem, so I actually coded this up in C++ (not, C, unfortunately, since that just seemed hard.):

#include <string>
#include <vector>
#include <unordered_map>
#include <utility>
#include <cassert>
#include <iostream>
using namespace std;

/**
 * Enumerated type: Symbol
 *
 * A type representing a symbol that can appear in a boolean expression.
 */
enum Symbol {
  TRUE,
  FALSE,
  AND,
  OR,
  NOT,
  IMPLIES,
  IFF,
  XOR
};

/**
 * Alias: Subproblem
 *
 * A name for a type representing one of the subproblems in the memoized
 * solution. Each subproblem corresponds to a subarray (given by a start
 * and end position) and an expected truth value (either true or false.)
 */
using Subproblem = tuple<size_t, size_t, bool>;
namespace std {
  template <> struct hash<Subproblem> {
    bool operator()(const Subproblem& s) const {
      return hash<size_t>()(get<0>(s)) + 31 * hash<size_t>()(get<1>(s)) + 127 * hash<bool>()(get<2>(s));
    }
  };
}

/* Internal implementation. */
namespace {
  /**
   * Function: canYield(const vector<Symbol>& formula,
   *                    size_t start, size_t end,
   *                    unordered_map<Subproblem, bool>& subproblems,
   *                    bool expected);
   * --------------------------------------------------------------------------
   * Determines whether the subexpression in range [start, end) of the formula
   * given by formula can be made to evaluate to result. Memoizes its results
   * to avoid extraneous computations.
   */
  bool canYield(const vector<Symbol>& formula,
        size_t start, size_t end,
        unordered_map<Subproblem, bool>& subproblems,
        bool expected) {
    /* Edge case check: we shouldn't have an empty range. */
    assert (end > start);

    /* Begin by seeing if we've already computed this. If so, we're done!
     * If not, we have to do some work. By the time this if statement finishes,
     * soln should be valid.
     */
    const Subproblem thisSubproblem = make_tuple(start, end, expected);
    if (!subproblems.count(thisSubproblem)) {
      /* Base case: If this is a single-element range, it must be either
       * to TRUE or FALSE, and we should be able to read off the answer
       * directly.
       */
      if (start + 1 == end) {
    /* This has to be TRUE or FALSE; otherwise the formula is malformed. */
    assert (formula[start] == TRUE || formula[start] == FALSE);

    /* See whether the enumerated constant matches the expected value. */
    bool isTrue = (formula[start] == TRUE);
    subproblems[thisSubproblem] = (isTrue == expected);
      }
      /* Otherwise, we have a longer range. */
      else {
    /* If this range begins with a NOT, one option is to parenthesize
     * the rest of the expression to try to get the opposite of what's
     * expected.
     */
    if (formula[start] == NOT &&
        canYield(formula, start + 1, end, subproblems, !expected)) {
      subproblems[thisSubproblem] = true;
    } else {
      /* Iterate over the range, trying to put all binary operators at
       * the top level if possible. If any of them work, we're done!
       */
      for (size_t i = start; i < end; i++) {
        /* To handle AND and OR, we'll use the fact that de Morgan's laws
         * allows us to unite a bunch of cases together.
         */
        if (formula[i] == AND || formula[i] == OR) {
          /* Here's the observatino. If we're trying to make an AND true
           * or an OR false, we need to get both subformulas to match
           * the expected truth value. If we're trying to make an AND false
           * or an OR true, we need to get one subformula to match the
           * expected truth value. So we need to see the parity of the
           * combination of AND/OR and whether we want true/false.
           */
          bool parity = ((formula[i] == AND) == expected);

          /* If the parities match, we're either looking for an AND/true
           * or an OR/false.
           */
          if (parity &&
          canYield(formula, start, i, subproblems, expected) &&
          canYield(formula, i+1, end, subproblems, expected)) {
        subproblems[thisSubproblem] = true;
        break;
          }
          /* If the parities disagree, we're either looking for AND/false
           * or OR/true.
           */
          else if (!parity &&
               (canYield(formula, start, i, subproblems, expected) ||
            canYield(formula, i+1, end, subproblems, expected))) {
        subproblems[thisSubproblem] = true;
        break;          
          }
        }
        /* If we see an XOR or IFF, we can similarly use a de Morgan's
         * trick.
         */
        else if (formula[i] == XOR || formula[i] == IFF) {
          /* If we're looking for an XOR/true or an IFF/false, then we
           * need exactly one of the two subproblems to be true. If we're
           * looking for an XOR/false or an IFF/true, then we need both
           * of the subproblems to be true or both to be false. Let's
           * start by determining which case we're in.
           */
          bool parity = ((formula[i] == XOR) == expected);

          /* Fire off the four subproblems we need to consider. */
          bool fTrue  = canYield(formula, start, i, subproblems, true);
          bool fFalse = canYield(formula, start, i, subproblems, false);
          bool sTrue  = canYield(formula, i+1, end, subproblems, true);
          bool sFalse  = canYield(formula, i+1, end, subproblems, false);

          /* If we have true parity, we're looking for XOR/true or IFF/
           * false, so we want the first and second halves to disagree.
           */
          if (parity && ((fTrue && sFalse) || (fFalse && sTrue))) {
        subproblems[thisSubproblem] = true;
        break;
          }
          /* Otherwise, we're looking for equal parity, so we need the
           * first and second halves to agree.
           */
          else if (!parity && ((fTrue && sTrue) || (fFalse && sFalse))) {
        subproblems[thisSubproblem] = true;
        break;
          }
        }
        /* Implications are their own can of worms since they're so 
         * different than everything else.
         */
        else if (formula[i] == IMPLIES) {
          /* For 'true,' we check if the antecedent can be made false
           * or the consequent made true.
           */
          if (expected &&
          (canYield(formula, start, i, subproblems, false) ||
           canYield(formula, i+1, end, subproblems, true))) {
        subproblems[thisSubproblem] = true;
        break;
          }
          /* For 'false,' we see if the antecedent is true and the
           * consequent is false.
           */
          if (!expected &&
          canYield(formula, start, i, subproblems, true) &&
          canYield(formula, i+1, end, subproblems, false)) {
        subproblems[thisSubproblem] = true;
        break;
          }
        }
      }
    }
      }
    }
    /* Return the solution we found. Notice that as a cute trick, if we didn't
     * record a true value in the course of solving the problem, then this
     * read will default to false - which is what we wanted!
     */
    return subproblems[thisSubproblem];
  }
}

/**
 * Function: canParenthesizeToYieldTrue(const vector<Symbol>& formula);
 * Usage: if (canParentheiszeToYieldTrue({FALSE, AND, NOT, FALSE})) // false
 *        if (canParenthesizeToYieldTrue({NOT, FALSE, AND, FALSE})) // true
 * 
 * ----------------------------------------------------------------------------
 * Given a boolean expression, returns whether it's possible to add parentheses
 * into the expression in a way that causes that expression to evaluate to
 * true. It is assumed that this formula is well-formed and nonempty.
 */
bool canParenthesizeToYieldTrue(const vector<Symbol>& formula) {
  /* Table for memoizing whether each subproblem is solvable or not. */
  unordered_map<Subproblem, bool> subproblems;
  return canYield(formula, 0, formula.size(), subproblems, true);
}

/* Prints out an expression in a nice form. */
void printExpr(const vector<Symbol>& problem) {
  for (Symbol s: problem) {
    switch (s) {
    case TRUE:    cout << "true";     break;
    case FALSE:   cout << "false";    break;
    case AND:     cout << " /\\ ";    break;
    case OR:      cout << " \\/ ";    break;
    case NOT:     cout << "!";        break;
    case XOR:     cout << " + ";      break;
    case IFF:     cout << " <-> ";    break;
    case IMPLIES: cout << " -> ";     break;
    default: assert(false);
    }
  }
}

/* Runs a test case to see if the program behaves as expected. */
void check(const vector<Symbol>& problem, bool expected) {
  bool result = (canParenthesizeToYieldTrue(problem) == expected);
  if (result) {
    cout << "  pass: ";
    printExpr(problem);
    cout << endl;
  }
  else {
    cout << "! FAIL: ";
    printExpr(problem);

    string throwaway;
    getline(cin, throwaway);
  }
}

int main() {
  /* Basic logic checks. */
  check({TRUE}, true);
  check({FALSE}, false);
  check({NOT, TRUE}, false);
  check({NOT, FALSE}, true);
  check({TRUE, AND, TRUE}, true);
  check({TRUE, AND, FALSE}, false);
  check({FALSE, AND, TRUE}, false);
  check({FALSE, AND, FALSE}, false);
  check({TRUE, OR, TRUE}, true);
  check({TRUE, OR, FALSE}, true);
  check({FALSE, OR, TRUE}, true);
  check({FALSE, OR, FALSE}, false);
  check({TRUE, XOR, TRUE}, false);
  check({TRUE, XOR, FALSE}, true);
  check({FALSE, XOR, TRUE}, true);
  check({FALSE, XOR, FALSE}, false);
  check({TRUE, IFF, TRUE}, true);
  check({TRUE, IFF, FALSE}, false);
  check({FALSE, IFF, TRUE}, false);
  check({FALSE, IFF, FALSE}, true);
  check({TRUE, IMPLIES, TRUE}, true);
  check({TRUE, IMPLIES, FALSE}, false);
  check({FALSE, IMPLIES, TRUE}, true);
  check({FALSE, IMPLIES, FALSE}, true);

  /* Harder ones! */
  check({TRUE, AND, NOT, TRUE}, false);
  check({NOT, TRUE, AND, TRUE}, false);
  check({FALSE, AND, NOT, FALSE}, false);
  check({NOT, FALSE, AND, FALSE}, true);

  check({TRUE, OR, NOT, TRUE}, true);
  check({NOT, TRUE, OR, TRUE}, true);
  check({FALSE, OR, NOT, TRUE}, false);
  check({NOT, TRUE, OR, FALSE}, false);

  check({NOT, FALSE, IMPLIES, TRUE}, true);
  check({NOT, FALSE, IMPLIES, FALSE}, false);

  check({NOT, FALSE, XOR, TRUE}, false);
  check({NOT, FALSE, IFF, FALSE}, false);

  /* Ridiculous */
  check({NOT, NOT, FALSE, OR, FALSE, OR, FALSE}, false);
}