#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);
}
1 回答
这里有一个观察结果是，如果最终得到一个完全括号的表达式，整个表达式中将会有一些顶级运算符 . 基于该运算符，如果许多不同情况之一成立，则整个表达式将评估为真 . 例如，如果顶级运算符是AND，则如果AND的左侧和右侧的子表达式为真，则表达式为true . 如果顶级操作是OR，则如果左或右子表达式求值为true，则整个表达式的计算结果为true . 如果顶级运算符是NOT，则如果NOT的子表达式为false，则整个表达式为true .
您可以想象一个自上而下的递归算法，其工作方式如下：对于每个运算符，暂时假设它是顶级运算符，并递归地确定所讨论的子表达式是否具有适当的真值 . 如果是这样，公式可以成立 . 如果没有，它不能 .
这里可能的子表达式/真值对的数量是O（n2），因为每个子表达式只是原始表达式的子阵列，并且它们只有O（n2） . 因此，会出现很多重叠的子问题，因此您可以使用memoization或自下而上的动态编程自上而下计算结果 .
这似乎是一个非常有趣的问题，所以我实际上用C编写了这个（不幸的是，C，不幸的是，因为这看起来很难 . ）：