Есть ли алгоритм для решения перестановок размещения скобок в логических выражениях? ⇐ C++

[Anonymous]

Проблема (нажмите, чтобы увидеть) заключается в том, чтобы получить случайную строку из символов t и f (что означает логическое значение true/false), разделенных одним из & | ^ например «T&F|F^T&T^F» и напишите функцию, возвращающую количество уникальных размещений скобок (где общее количество пар скобок = количество t/f - 1), для которых общее выражение будет иметь значение true. (T&((F^T)|(T&F))) верно.
Мой код возвращает правильный ответ, но не за отведенное время (для очень длинных входных строк). Я ищу подсказку, нужно ли мне понять трюк алгоритма, который радикально сокращает количество итераций/рекурсий, или мой код просто недостаточно эффективен.
Мой алгоритм по сути повторяется каждое соединение, но после сокращения любой данной пары tf до одного нового значения он проверяет полученную строку размещения символов/скобок по таблице поиска, чтобы увидеть, был ли этот шаблон достигнут ранее, и продолжает без рекурсии, если да.
Например, если входные данные — T T F T F F T: Если мы находимся на перестановке, где первая пара — (TT)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
#include
#include
#include
#include

using namespace std;

using pairVec = vector;

unordered_map 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.second, tfs[i+1].second, ops);
string newBracePat = "(" + tfs.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=='f') v.second = 'f';
traverse(v, ops2, ct);
return ct;
}

int main(int argc, char **argv) {
cout

Подробнее здесь: https://stackoverflow.com/questions/784 ... -boolean-e