1

我和 html 是这样的:

<div id="tree">
    <div id="AND" class="node">
        <div id="OR" class="node">
            <div id="a" class="node"></div>
            <div id="b" class="node"></div>
        </div>
        <div id="OR" class="node">
             <div id="c" class="node"></div>
             <div id="d" class="node"></div>
        </div>
    </div>
</div>

我使用 jquery 来获取这样的节点:

$(".node")

我使用 for 形成这样的数组:

var expresion = ["AND","OR","a", "b", "OR", "c", "d"];

我想构建类似的东西:

a OR b AND c OR d

有谁知道构建布尔表达式的算法。提前致谢。

4

3 回答 3

1

尝试遍历数组的前缀:您将能够构造您想要的表达式。这对程序员来说是一个简单的过程,它将作为练习留下。我会帮忙:阅读Tree Traversal。基本上,访问数组的顺序将产生您想要的输出。

于 2012-07-12T21:28:52.083 回答
0

理想情况下,您应该自己按顺序遍历节点。参见:http ://en.wikipedia.org/wiki/In-order_traversal#Inorder_Traversal


但是,此功能应该为您提供您正在寻找的确切功能:

function convertPreOrderArrayToInOrderString(elements)
{
    var cursor = 0;
    // While all the elements aren't merged together
    while (elements.length > 1)
    {
        // Skip to the nextleaf
        while (elements[cursor] === "AND" || elements[cursor] === "OR") cursor++;
        
        // If we made all the matches we can at this depth, go to the next one
        if (typeof elements[cursor+1] === "undefined") 
        {
            cursor = 0;
            continue;
        }
        
        // The relevant pieces to combining
        var previous = elements[cursor-1];
        var current = elements[cursor];
        var next = elements[cursor+1];
        
        // Create a string from the pieces
        var tmpStr = current + " " + previous;
        
        // How many we've combined
        var combined = 2;
        
        // If the third piece is complete, we can join it too
        if (next !== "AND" && next != "OR")
        {
            // Tack the third piece on
            tmpStr += " " + next;
            combined++;
        }
        
        // Remove the individual elements and replace with the combined ones
        var newElements = elements.slice(0, cursor-1);
        newElements.push(tmpStr);
        newElements = newElements.concat(elements.slice(cursor - 1 + combined));
        
        // From now on, opreate on the new array with combined elements
        elements = newElements;
    }
    
    // There should be one element left
    return elements[0];
}


var expression = ["AND","OR","AND","a","f","OR","e","b","OR","c","d"];
console.log(convertPreOrderArrayToInOrderString(expression));
// Gives: "a AND f OR e OR b AND c OR d"

对应的小提琴:http: //jsfiddle.net/DvZj4/4/

不过,在更一般的情况下,您可能更喜欢这样做:

function convertPreOrderToInOrder(elements)
{
    // Very simple sanity checks
    if (elements.length === 1 && (elements[0] === "AND" || elements[0] === "OR"))
    {
        console.error("Cannot construct compound expression with boolean connectors without values");
        return;
    }
    else if (elements.length === 1)
    {
        // Only 1 items, just return it
        return elements[0];
    }
    else if (elements.length > 1 && elements[0] !== "AND" && elements[0] !== "OR")
    {
        console.error("Cannot construct compound expression  without boolean connectors");
        return;
    }

    // Convert back to a tree from the preorder, then flatten again in order
    return flattenTreeInOrder(getTreeFromPreOrderArray(elements));
}

// Reconstructs a tree from a pre-ordered array of elements
// Assumes your array of elements can construct a properly
// balanced tree. If it can't, this will get screwy
function getTreeFromPreOrderArray(elements)
{
    var i, el, root = {}, current = root;
    // Iterate over every element
    for (i in elements)
    {
        el = elements[i];
        // Pretty much just a root check
        if ( (el === "AND" || el === "OR") && !current.connector)
        {
            // Make this a root
            current.connector = el;
        }
        // Not a root, can we go left?
        else if (!current.left)
        {
            // Branch left
            if (el === "AND" || el === "OR")
            {
                current.left = {connector: el};
                current.left.parent = current;
                current = current.left;
            }
            // Left left
            else
            {
                current.left = el;
                current.left.parent = current;
            }
        }
        // Not a root, can't go left. Try to the right.
        else
        {
            // Branch right
            if (el === "AND" || el === "OR")
            {
                current.right = {connector: el};
                current.right.parent = current;
                current = current.right;
            }
            // Leaf Right
            else
            {
                current.right = el;
                current.right.parent = current;
                // Tricky bit: If we put a leaf on the right, we need
                // to go back up to the nearest parent who doesn't have
                // right child;
                while (current.parent && current.right)
                {
                    current = current.parent;
                }
            }
        }
    }
    return root;
}

// Flatten a tree into an array using in-order traversal
// No recursion, uses stack-based traversal
// Returns an array of strings
function flattenTreeInOrder(root)
{
    var stack = [];
    var flat = [];
    var current = root;
    // We need to keep going as long as there's either something in the
    // stack, or we're looking at a node.
    while (stack.length > 0 || current)
    {
        // If the looked at node is defined
        // This will help us tell if we've gone past a leaf
        if (current)
        {
            // Don't care during in order traversal. Just push this on
            // and move to the left
            stack.push(current);
            current = current.left;
        } 
        else
        {
            // Starting to go back up, but the current is undefined
            // So, pop first, then start capturing in order elements
            current = stack.pop();
            flat.push(current.connector || current);
            current = current.right;
        }
    }
                    
    return flat;
}


var expression = ["AND","OR","AND","a","f","OR","e","b","OR","c","d"];
console.log(convertPreOrderToInOrder(expression).join(" "));
// Gives: "a AND f OR e OR b AND c OR d"

​ 对应小提琴:http: //jsfiddle.net/keR5j/


不能复制 htmlid元素

此外,您不能像在结构中那样使用 id。有多个相同的实例id,即每个规范的两个节点id="OR"是无效的 HTML:http: //www.w3.org/TR/html401/struct/global.html#h-7.5.2

id = 名称 [CS]

此属性为元素分配名称。此名称在文档中必须是唯一的。


于 2012-07-13T23:48:41.677 回答
0
function travarse(node){
    var result = [];
    var op = node.children("#AND,#OR");
    var len = op.length;
    var term;
    if(len){
      term = op.children(".node");
      result=result.concat(travarse($(term.get(0))));
      result.push(op.get(0).id);
      result=result.concat(travarse($(term.get(1))));
    } else {
      term = node.children(".node");
      result.push(term.get(0).id);
      result.push(node.get(0).id);
      result.push(term.get(1).id);
    }
    return result;
}

//var expresion = $.map($.makeArray($(".node")), function(el){ return el.id; });//["AND", "OR", "a", "b", "OR", "c", "d"]
var expression = travarse($('#tree'));//["a", "OR", "b", "AND", "c", "OR", "d"]
于 2012-07-13T17:49:39.763 回答