Итак, у меня есть личная программа, которая реализует это для строк с формой "Ab|c(d|E)|fa"
мой полный исходный код представляет собой полный беспорядок и содержит множество других вещей, которые я пытаюсь сделать одновременно (не удается упростить выражение, обводя kmaps и прочее)
Однако я могу пройти через то, что я сделал, если это поможет
его настройка упрощает анализ с заглавными буквами, представляющими положительные, и строчными буквами, представляющими отрицание/не (), представляющими подвыражения, и [], представляющими отрицательные подвыражения, поэтому входная строка `ABC (DEF) G (HI (KK) S [ as][ge])S преобразуется в эту структуру .repr()
AND(
A
B
C
AND( D E F )
G
AND(
H
I
AND( K K )
S
NAND( !A !S )
NAND( !G !E )
)
S
)
и что-то вроде "Ab|cb" есть
OR(
AND( A !B )
AND( !C !B )
)
У меня есть объект (я называю выражение), который содержит информацию о его типе, хранящемся примерно в следующем
namespace xpr { //expression types
enum typ {
identity_,
negation_,
and_,
or_,
nand_,
nor_
};
}
class expression{
...
xpr::typ type = xpr::identity_;
char value = ' ';
std::vector<expression> sub_expressions;
...
};
и либо символ, который является его значением, либо вектор выражений. (и или ни выражения nand)
Преобразование его в эту форму выражения выполняется с помощью вложенных конструкторов, которые продолжают передавать текущую позицию в строке, а также ее уровень.
наконец, чтобы ответить на ваш вопрос
std::vector<char> vars = trackUsed();
// equivalent to a set but more efficent to do the sort/unique at the end one time.
removeDuplicates(vars);
const auto truth_table_width = vars.size();
const auto truth_table_size = (size_t)std::pow((size_t)2, truth_table_width); // 2^width
expression::test_type test; // abc through !a!b!c
test.reserve(truth_table_width);
for ( const auto &v : vars ) {
// value_type is value: 6, sign: 2 so character has to fit in 6bits and sign in 2.
// minus 'A' to make A-Z 0-26
test.emplace_back(v - 'A', xpr::negative);
}
for ( size_t i = 0; i < truth_table_size; i++ ) {
for ( size_t j = 0; j < truth_table_width; j++ ) {
// converts 0 to negative and 1 to positive
test[j].sign = (xpr::sign_type)((i >> j) & 0x1);
}
bool valid = testValues(test);
if ( valid ) {
sum_of_products.push_back(test);
}
}
Я создал таблицу истинности, извлекая все используемые символы, удаляя дубликаты и сортируя их. создание объекта, определенного реализацией вектора ›› увеличение значения до максимальной ширины таблицы истинности и использование бита знака этого значения для заполнения таблицы истинности - 0 = [0, 0, ... 1 = [1, 0 , ... 2 = [0, 1, ... и т. д., а затем перебирает внешний вектор и отправляет внутренний вектор в функцию-член testValues, специализированную для каждого типа выражения.
// given A true B true C true see if whole expression evaluates to true.
bool expression::testValues(const potion::test_type& values) const {
if ( this->is_simple() ) {
auto val = std::lower_bound(values.begin(), values.end(),
this->value,
[ ](potion::val_type lhs, char rhs) -> bool {return lhs < rhs; }
);
if ( type == xpr::identity_ ) return (*val).sign;
if ( type == xpr::negation_ ) return !(*val).sign;
}
if ( type == xpr::and_ || type == xpr::nand_ ) {
const bool is_and = type == xpr::and_; //used to combine and and nand expressions and return the oposite val for nand
for ( const auto& e : sub_expressions ) {
if ( e.testValues(values) == false ) return !is_and; // short circuit- if b is false then abc is false
}
return is_and;
}
if ( type == xpr::or_ || type == xpr::nor_ ) {
const bool is_or = type == xpr::or_; //used to combine or and nor and return the oposite val for nor
for ( const auto& e : sub_expressions ) {
if ( e.testValues(values) == true ) return is_or; // short circuit- if b is true then a|b|c is true
}
return !is_or;
}
throw std::runtime_error("Expression can't be simplified. Type not valid"); //should never happen
return false;
}
Очевидно, есть тонны и тонны стандартного кода/кода синтаксического анализа, который, вероятно, не самый лучший. И если вы хотите анализировать строки, используя пользовательский язык, который вы определяете (( c + ~d ) * b ) * ~( d + a * e ), то код синтаксического анализа, очевидно, будет сильно отличаться.
В любом случае, я надеюсь, что это будет полезно для вашего проекта. TLDR: может быть немного сложнее реализовать, чем вы изначально думали. Хотя все, что я сделал, является функциональным, код не самый чистый, и его тяжелая настройка для моего конкретного случая - только получение положительных записей таблицы истинности и сохранение их в сумме произведений, которые можно обрабатывать дальше.
person
BlueLightning42
schedule
24.10.2020
(( c + ~d ) * b ) * ~( d + a * e )? Или разрешено жестко кодировать формулу с некоторым преобразованием, чтобы использовать ее как выражение C++? - person MikeCAT schedule 24.10.2020c d ~ + b * d a e * + ~ *(которая совпадает с указанным вами выражением, если я набрал его правильно), где постфиксная форма ввод гораздо легче оценить - person Justin schedule 24.10.2020c d ~ + b * d a e * + ~ *, вычисление может быть реализовано с помощью стека.push c, push d, pop and ~, pop two and +, push b, pop two and *, push d, push a, push e, pop two and *, pop two and +, pop and ~, pop two and *- person Justin schedule 24.10.2020