Булевы выражения: постфикс для нескольких инфиксных строк

Question

Дано следующее (инфиксное) выражение:

(country = be or country = nl) and 
(language = en or language = nl) and 
message contains twitter

Я хотел бы создать следующие 4 инфиксных нотации:

message contains twitter and country = be and language = en
message contains twitter and country = be and language = en
message contains twitter and country = nl and language = nl
message contains twitter and country = nl and language = nl

В общем, я бы хотел избавиться от всех операционных.

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

(В целях иллюстрации постфиксной нотацией для этого запроса будет:)

country be = country nl = or language en = language = nl or and message twitter contains and

Кто-нибудь знает алгоритм для достижения этой цели?

Answer 1

Разбейте проблему на два этапа: постфикс для нескольких постфиксов, постфикс для инфиксов. Каждый шаг выполняется путем "интерпретации" постфиксного выражения.

Для постфикса для нескольких постфиксных интерпретаторов: значения стека являются коллекциями выражений постфикса. Правила интерпретации следующие.

<predicate>: push a one-element collection containing <predicate>.
AND: pop the top two collections into C1 and C2. With two nested loops,
     create a collection containing x y AND for all x in C1 and y in C2.
     Push this collection.
OR: pop the top two collections into C1 and C2. Push the union of C1 and C2.

Для интерпретатора постфикса в инфикс: значения стека являются выражениями инфикса.

<predicate>: push <predicate>.
AND: pop two expressions into x and y. Push the expression (x) and (y).

Эти шаги можно объединить, но я хотел бы привести два примера этой техники.

Answer 2

Возможно, проще всего работать с представлением в виде дерева. Используйте алгоритм маневрового двора, чтобы построить двоичное дерево, представляющее уравнение. Узел в дереве может быть:

class Node {
    const OP = 'operator';
    const LEAF = 'leaf';
    $type = null; // Will be eight Node::OP or Node::LEAF
    $op = null; // could be 'or' or 'and' 'contains'; 
    $value = null; // used for leaf eg 'twitter'
    $left = null;
    $right = null;

}

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

Если у вас есть древовидное представление, вам нужно несколько алгоритмов.

Сначала вам нужен алгоритм для копирования дерева

public function copy($node) {
    if($node->type == Node::LEAF) {
        $node2 = new Node();
        $node2->type = Node::LEAF;
        $node2->value = $node->value;
        return $node2;
    }
    else {
        $left = copy($node->left);
        $right = copy($node->right);
        $node2 = new Node();
        $node2->type = Node::OP;
        $node2->op = $node->op;
        $node2->left = $node->left;
        $node2->right = $node->right;
        return $node2;
    }
}

Затем алгоритм, чтобы найти первый 'или' узел оператора.

function findOr($node) {
    if($node->type == Node::OP && $node->op == 'or') {
       return $node;
    } else if($node->type == Node::OP ) {
       $leftRes = findOr($node->$left);
       if( is_null($leftRes) ) {
           $rightRes = findOr($node->$right); // will be null or a found node
           return $rightRes;
       } else {
           return $leftRes; // found one on the left, no need to walk rest of tree
       }
    } else {
       return null;
    }
}

и, наконец, алгоритм copyLR, дающий либо левую (true), либо правую (false) ветвь. Он ведет себя как копия, если только узел не соответствует $target, когда возвращается левая или правая ветвь.

public function copyLR($node,$target,$leftRight) {
    if($node == $target) {
        if($leftRight)
            return copy($node->left);
        else
            return copy($node->right);
    }
    else if($node->type == Node::LEAF) {
        $node2 = new Node();
        $node2->type = Node::LEAF;
        $node2->value = $node->value;
        return $node2;
    }
    else {
        $left = copy($node->left,$target,$leftRight);
        $right = copy($node->right,$target,$leftRight);
        $node2 = new Node();
        $node2->type = Node::OP;
        $node2->op = $node->op;
        $node2->left = $node->left;
        $node2->right = $node->right;
        return $node2;
    }
}

Кусочки теперь собраны вместе

$root = parse(); // result from the parsing step 
$queue = array($root);
$output = array();
while( count($queue) > 0) {
    $base = array_shift($queue);
    $target = findOr($base);
    if(is_null($target)) {
        $output[] = $base; // no or operators found so output
    } else {
        // an 'or' operator found
        $left = copyLR($base,$target,true); // copy the left
        $right = copyLR($base,$target,false); // copy the right
        array_push($left); // push both onto the end of the queue
        array_push($right);
    }
}