Булева формула - PullRequest
Новая
       15

Булева формула

0 голосов
/ 25 ноября 2018

Дана произвольная формула 2-значного булева алгебры, например (1V0) V1V ~ (0∧1).Как я могу получить результат этой формулы, используя JavaScript?Я имею в виду, учитель дает формулу, и моя программа должна напечатать результат 1 или 0.

Ответы [ 3 ]

0 голосов
/ 25 ноября 2018

Если входные данные всегда заслуживают доверия, одним из вариантов будет преобразование выражения в правильный синтаксис JS, а затем использование eval: 

const check = str => Boolean(eval(str
  .replace(/v/gi, '||')
  .replace(/∧/g, '&&')
  .replace(/~/g, '!')
));

console.log(check('(1V0)∧1V~(0∧1)'));
console.log(check('0∧0'));
console.log(check('1∧1'));
console.log(check('1∧0'));
console.log(check('1V0'));
console.log(check('0V0'));
0 голосов
/ 25 ноября 2018

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

Сначала вы разбиваете входные данные на "токены" или символы (операторы, значения, скобки).Это называется «лексизм» и довольно тривиально в вашем случае, потому что ваши символы всегда один символ.

Затем вы строите дерево разбора, или "AST", из этих токенов.Каждый узел в дереве разбора является объектом operator left right, где left и right могут быть значениями или другими объектами узла.Например, 

a v b ^ c

дает следующее дерево разбора 

   operator = v
   left = a
   right = {
       operator = ^
       left = b
       right = c
   }

Чтобы построить синтаксический анализатор, вам нужно определить набор формальных правил, называемых "грамматикой", для ваших выражений,Пример грамматики для логических значений: 

 <b-expression>::= <b-term> [OR <b-term>]*
 <b-term>      ::= <not-factor> [AND <not-factor>]*
 <not-factor>  ::= [NOT] <b-factor>
 <b-factor>    ::= <b-literal> | <b-variable> | (<b-expression>)

(https://compilers.iecc.com/crenshaw/tutor6.txt)

После построения AST вы «оцениваете» каждый узел дерева с помощью простого рекурсивного алгоритма: 

evaluate(node)
   if node is a value (e.g. "1"), return this value
   otherwise, 
        L = evaluate(node.left)
        R = evaluate(node.right)
        V = apply node.operator to L and R
        return V

Надеюсь, это поможет!

0 голосов
/ 25 ноября 2018

Вы можете использовать логические операторы, такие как

и замена данных логических операторов. 

 console.log((1 || 0) && 1 || !(0 && 1));
...