是否有算法技巧可以解决布尔表达式中的括号放置排列？

Question

问题（点击查看） 被赋予一个由 t 和 f（代表布尔真/假）组成的随机字符串，并用 & | 之一分隔。 ^ 例如“T&F|F^T&T^F”并编写一个函数来返回唯一括号放置的数量（其中括号对的总数 = t/f 的数量 - 1），整个表达式将计算为 true。 (T&((F^T)|(T&F))) 是正确的。 我的代码返回正确的答案，但没有在指定的时间内返回（对于很长的输入字符串）。我正在寻找关于我是否需要理解一种可以大大减少迭代/递归的算法技巧的提示，或者我的代码不够高效。

我的算法本质上会迭代每个配对，但在将任何给定的 tf 对减少为单个新值之后，它会根据查找表检查字符/括号放置的结果字符串，以查看之前是否已达到该模式，并继续而不递归如果有的话。

例如，如果输入是 T T F T F F T：如果我们正在进行一个排列，其中第一对是 (T T)F T F F T，第二对是 (T T)F T(F F)T，那么最终我们将得到一个排列，其第一对是 T T F T(F F)T，第二对是 (T T)F T(F F)T，此时表格将显示该路径已被遍历，并将继续进行下一个排列。

每次减少 tf 字符串时，我也会执行检查，例如(T&F)^F|T&T --> F^F|T&T 确保至少还剩下一个 T，因为 F^F|F&F 不再需要递归。

我觉得一定有一种方法可以减少超出我所做的遍历量。

//  C++.   The input will be given as two strings, e.g. "ttfftf","&&^|^"

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <iostream>

using namespace std;

using pairVec = vector<pair<string,char>>;

unordered_map<string, bool> usedPatMap{};

inline char tOrF(char c1, char c2, char op){
    if(c1=='f') {
        if(c2=='f') return 'f';
        else { // c2=='t'
            if(op=='&') return 'f';
            return 't';
        }
    }
    else { //c1=='t'
        if(c2=='f') {
            if(op=='&') return 'f';
            return 't';
        }
        else { // c2=='t'
            if(op=='^') return 'f';
            return 't';
        }
    }
  }

void traverse(pairVec& tfs, string ops, int64_t& ct) {
    for(int i = 0; i + 1 < tfs.size(); ++i) {
      char tf = tOrF(tfs[i].second, tfs[i+1].second, ops[i]);
      string newBracePat = "(" + tfs[i].first + tfs[i+1].first + ")";
      pairVec tfs2 = tfs;
      string ops2 = ops;
      auto p = tfs2.erase(tfs2.begin() + i, tfs2.begin() + 2 + i);
      tfs2.insert(p,make_pair(newBracePat,tf));
      
      if(find_if(tfs2.begin(), tfs2.end(),
            [](auto x){ return x.second=='t';})==tfs2.end()) continue;

      string checkStr;
      for(auto pr:tfs2) checkStr.append(pr.first);
      if(!usedPatMap[checkStr]) usedPatMap[checkStr] = true;
      else continue;
      
      ops2.erase(ops2.begin()+i);
      if(ops2.empty()) {
        if(tfs2[0].second=='t') ++ct;
        return; }
      traverse(tfs2, ops2, ct);
    }
   }

int64_t solve(const string &s, const string &ops) {
  
    if(s.length() < 2 || ops.length()!=s.length() - 1) return 0;
    int64_t ct = 0;

    string s2 = s, ops2 = ops;
  pairVec v(s2.length(),{"x",'t'});
  for(int i = 0; i < s2.length(); ++i) if(s2[i]=='f') v[i].second = 'f';
  traverse(v, ops2, ct);
  return ct;
}

int main(int argc, char **argv) {
  cout<<solve("ttftfftftf","|&^&&||^&");
}

Answer 1

通过简要查看您的代码，我注意到您实际上是在不同位置插入括号来构造字符串。这当然代表了很多实际上没有必要的操纵。

不需要任何字符串操作。计算输入的子字符串的结果就足够了，并收集每个错误结果的数量和真实结果的数量。如果您从最小的子字符串开始，只有一个

f

 或 

t

 值，那么这是微不足道的。然后，您可以依靠这些结果来计算具有两个操作数和一个运算符的子字符串的计数。这给出了新的结果层。对于下一层，您还需要考虑顶部运算符的选择（左侧和右侧操作数较小，您已经有计数）。

这是对自底向上动态规划解决方案的描述。

我在这里提供 C 风格代码，使用普通数组。对于 C++，最好像您一样使用向量：

int64_t solve(const std::string &s, const std::string &ops)
{
    size_t n = s.length();
    int64_t dp[n][n][2]; // Dynamic programming tabulation
    for (size_t i = 0; i < n; i++) {
        int64_t isTrue = (s[i] == 't');
        dp[0][i][0] = 1 - isTrue;
        dp[0][i][1] = isTrue;
    }
    int64_t *counters = dp[0][0];
    for (size_t opCount = 1; opCount < n; opCount++) {
        for (size_t start = 0; start + opCount < n; start++) {
            counters = dp[opCount][start];
            counters[0] = counters[1] = 0;
            for (size_t leftOpCount = 0; leftOpCount < opCount; leftOpCount++) {
                int64_t *left = dp[leftOpCount][start];
                int64_t *right = dp[opCount - 1 - leftOpCount][start + leftOpCount + 1]; 
                int64_t ff = left[0] * right[0];
                int64_t ft = left[0] * right[1] + left[1] * right[0];
                int64_t tt = left[1] * right[1];
                char op = ops[start + leftOpCount];
                if (op == '&') {
                    counters[0] += ff + ft;
                    counters[1] += tt;
                } else if (op == '|') {
                    counters[0] += ff;
                    counters[1] += tt + ft;
                } else {
                    counters[0] += ff + tt;
                    counters[1] += ft;
                }
            }
        }
    }
    return counters[1];
}

dp

的第一个维度表示所考虑表达式的运算符数量（从0开始，直到并包括𝑛−1）。第二个维度在 

s

 中具有该子表达式开始的起始索引。第三维只有两个条目：一项用于错误计数，一项用于真实计数。