Блог

ИТАК, у меня есть уравнение (( c ~ d) * b ) * ~ ( d a * e), из которого я пытаюсь сгенерировать таблицу истинности, но я не уверен, как бы я даже начал с того, чтобы заставить программу вычислять, должна ли переменная быть равна trueили false в соответствии с таблицей истинности. Есть предложения, как это сделать? Заранее благодарю вас.

 #include<iostream>

using namespace std;

bool checkBoolTF(int a){
    bool TF;
    if(a == 0){
        TF = false;
    }
    else{
        TF = true;
    }
    return TF;
}

int main()
{
  int a,b,c,d,e;
  bool aBool, bBool, cBool, dBool, eBool;

  string equation = "(( c   ~d ) * b ) * ~( d   a * e )";
  bool equationTF;


  //LOOP TO TRUTH TABLE - FINAL VALUES
  cout << "----------------------------------------------------------------------" << endl;
  cout << "|  a  |  b  |  c  |  d  |  e  |  " << equation << "  |" << endl;
  cout << "----------------------------------------------------------------------" << endl;
    for(a=0;a<=1;a  ){
        checkBoolTF(a);
            for(b=0;b<=1;b  ){
                checkBoolTF(b);
                    for(c=0;c<=1;c  ){
                        checkBoolTF(c);
                            for(d=0;d<=1;d  ){
                                checkBoolTF(d);
                                    for(e=0;e<=1;e  ){
                                        checkBoolTF(e);
                                        cout << "|  " << a << "  |  " << b <<  "  |  " << c <<  "  |  " << d <<  "  |  " << e << "  |                   "  << equationTF << "                |" << endl;
                                        cout << "----------------------------------------------------------------------" << endl;
                                    }
                            }
                    }
            }
    }
    return 0;
}
  

Шаг 1: Токенизация.

 enum class TokenType {
  bracket, binop, binaryop, var, literal
};
struct Token {
  TokenType type;
  char value;
 };
  

преобразуйте строку в вектор token .

Вы еще не используете literal : это значения 0 или 1. Вы будете использовать его позже.

Напишите код, который красиво печатает вектор токенов.

Шаг 2: создайте простое дерево.

 struct Tree {
  bool is_token=true;
  Token token;
  std::vector<Tree> tree;
};
  

измените свой первый код, чтобы сгенерировать дерево, содержащее вектор токенов.

Напишите код, который красиво его печатает. Тест.

Шаг 3: уменьшите дерево

Шаг 3a: скобки

Теперь выполните шаг сокращения; обходит вектор деревьев и генерирует один. Он слепо копирует все, что не является скобкой, в выходные данные. Если он видит a ( , он копирует все до совпадения ) (количество открытых и закрытых) в поддерево, затем копирует это поддерево в выходные данные.

Он берет "a ( b c )" и превращает его a затем b c в поддерево.

Напишите код, который может печатать поддеревья. Тест.

Шаг 3b: вложенные скобки

Затем выполните рекурсию по созданному вами поддереву, чтобы его вложенные скобки также помещались в поддеревья.

Шаг 3c: операторы

Далее, поработайте над операторами. ~ это просто: он проглатывает следующее дерево в векторе. Поскольку связывает loser than * , для каждого создайте два поддерева; одно для всего до, одно для всего после. Затем выполните то же самое для * .

После всего этого вы превращаете

 a (b c)*~(d e)
  

в

    (a , ( * (  (b, c), ~( (d,e))))
  

Шаг 4: замена

Сопоставление a std::map , которое сопоставляет переменную со значением. Возьмите копию дерева и пройдитесь по нему, заменив каждую переменную литералом, равным ее значению.

Шаг 5: оценка

Для каждого оператора вычислите поддерево (поддеревья), а затем примените оператор.

Результатом должно быть 0 или 1.

4 и 5 можно выполнить независимо, начав с буквального выражения.

Итак, у меня есть личная программа, которая реализует это для строк с формой "Ab|c(d|E)|fa"

мой полный исходный код представляет собой полный беспорядок и содержит множество других вещей, которые я пытаюсь сделать одновременно (не удается упростить выражение, обведя kmaps и прочее)

Однако я могу рассказать о том, что я сделал, если это поможет

мне будет проще анализировать ее с помощью заглавных букв, представляющих положительные и строчные буквы, представляющие отрицание / not (), представляющие подвыражения, и [], представляющие отрицаемые подвыражения, поэтому входная строка `»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 amp;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) amp; 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_typeamp; 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 autoamp; 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 autoamp; 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: может быть немного сложнее реализовать, чем вы изначально думали. Хотя все, что я сделал, функционально, код не самый чистый и его тяжелая настройка для моего конкретного случая — только получение записей таблицы истинности, которые имеют положительные значения, и сохранение их в сумме произведения, которая может быть обработана дальше.

Для начала вы можете упростить функцию checkBoolTF до чего-то вроде:

 bool checkBoolTF (int a)
{
    return !(a==0);
}
  

Во-вторых, похоже, что в циклах for значения, возвращаемые этой функцией, ничему не присваиваются и поэтому теряются. Итак, вы, вероятно, хотите определить вспомогательную переменную:

 bool auxA = checkBoolTF(a);
  

и так далее..

Я хотел бы показать дополнительное, уже существующее решение. Он хорошо структурирован и прокомментирован. Он опубликован на github. Пожалуйста, смотрите здесь

Предполагаемая цель этой программы — вычислить пары тестов MCDC. Но, конечно, это также все, что вы хотите. Я не рекомендую копировать и вставлять, но вы могли бы прочитать и узнать, как выполнить вашу реализацию.

Этот код считывает именно те строки, которые вы указали. Он также создает таблицу истинности. Но это лишь незначительная часть всей функциональности.

Итак, что вам нужно сделать, это скомпилировать строку во что-то, что может быть оценено как логическое выражение.

Для этого я сначала определил входной алфавит и язык, описанный грамматикой. Затем я создал компилятор, состоящий из сканера (лексера), анализатора и генератора кода. На самом деле я создал 2 компилятора с одинаковым интерфейсом и 2 разными интерфейсами. Итак, 2 разных генератора кода. Во-первых, для виртуальной машины, которая может вычислять логическое выражение для любой комбинации входных переменных. И, 2-й серверный сервер, создаст абстрактное синтаксическое дерево, с помощью которого я оцениваю все возможные тестовые пары MCDC.

Как уже было сказано, первый генератор кода создает операционный код для виртуальной машины. С помощью этой машины вычисляется таблица истинности и с ее помощью вычисляются все minterms. Затем используются Куайн и МаКкласки (2 разные реализации) для минимизации логического выражения. И, в конце концов, оптимизированная версия метода Петрикса используется для решения проблемы равномерного покрытия и определения минимального набора простых импликантов.

Часть MCDC, возможно, слишком сложна для объяснения здесь.

Но главное сообщение заключается в том, что сначала вам нужно проанализировать вашу строку и преобразовать ее во что-то исполняемое.

Затем вы можете оценивать все, что хотите.