Parsing a logical expression and converting it to a tree in Perl

Question

I have a complex boolean expression that looks like this:

((((!((cond1) || (cond2) || (cond3)) && (cond4))) && (cond5)) <= (((cond6) || (cond7) || (cond8)) || (cond9))) 

Each line has several tens of expressions. Allowed logical signs || , && and <= . <= means that conclusions, as in a <= b , mean that b leads to a.

I need to review these statements and check the conditions, as some of them are no longer valid. I want to be able to see it on a tree, and then check each of them sheet (where each sheet is a condition), remove unnecessary leaves and build complete and correct expressions.

I know that each node of the tree is defined by the pair of the first bracket and the bracket that closes it, but I do not know how to identify such pairs and how to identify the logical sign between them.

All signs except ! enter between two expressions.

Answer 1

Sounds like a case for Parse :: RecDescent :

 use strict; use warnings; use Parse::RecDescent; my $text = '((((!((cond1) || (cond2) || (cond3)) && (cond4))) && (cond5)) <= (((cond6) || (cond7) || (cond8)) || (cond9)))'; #$::RD_TRACE=1; my $grammar = q{ startrule: expr expr: operand operation(s?) { $return = @{$item[2]} ? { 'operations' => $item[2], 'lvalue' => $item[1] } : $item[1] } operation: /\|\||&&|<=/ operand { $return = { 'op' => $item[1], 'rvalue' => $item[2] } } operand: '(' expr ')' { $return = $item[2] } operand: '!' operand { $return = { 'op' => '!', 'value' => $item[2] } } operand: /\w+/ }; my $parser = Parse::RecDescent->new($grammar); my $result = $parser->startrule($text) or die "Couldn't parse!\n"; use Data::Dumper; $Data::Dumper::Indent = 1; $Data::Dumper::Sortkeys = 1; print Dumper $result; 

Grammar in English:

All this expression. An expression is an operand followed by zero or more binary operators and their operands. Each operand is an expression in parentheses, '!' followed by an operand or word (e.g. cond1 ).

Each node in the created tree is in one of the following forms:

• cond1 - condition
• { 'op' => '!', 'value' => 'node' } -! applies to another node
• { 'lvalue' => 'node', 'operations' => [ one or more of: { 'op' => 'binop', 'rvalue' => 'node' } ] } - a series of one or more operations, representing node binop node binop node ...

I did not break a number of binary operations (for example, ((cond1) || (cond2) || (cond3)) ) into a binary tree because you did not provide any information about priority or associativity.

The output for your example:

 $VAR1 = { 'lvalue' => { 'lvalue' => { 'lvalue' => { 'op' => '!', 'value' => { 'lvalue' => 'cond1', 'operations' => [ { 'op' => '||', 'rvalue' => 'cond2' }, { 'op' => '||', 'rvalue' => 'cond3' } ] } }, 'operations' => [ { 'op' => '&&', 'rvalue' => 'cond4' } ] }, 'operations' => [ { 'op' => '&&', 'rvalue' => 'cond5' } ] }, 'operations' => [ { 'op' => '<=', 'rvalue' => { 'lvalue' => { 'lvalue' => 'cond6', 'operations' => [ { 'op' => '||', 'rvalue' => 'cond7' }, { 'op' => '||', 'rvalue' => 'cond8' } ] }, 'operations' => [ { 'op' => '||', 'rvalue' => 'cond9' } ] } } ] };