<?php

define("COMP_AND", 1);
define("COMP_OR", 2);
define("COMP_XOR", 3);

function parseExpr($str, &$struct, &$vars) {
    // comp = {AND, OR}
    // name = [a-z][a-z0-9_]+
    // expr = [!](<name>|<expr>) <comp> [!](<name>|<expr>)
    
    // extra brackets result in a parse error (for now, anyways)

    if (preg_match("/^\s*\(?\s*([!]?)(([a-z][a-z0-9_]+)|(\(.*\)))\s+(AND|OR|XOR)\s+([!]?)(([a-z][a-z0-9_]+)|(\(.*\)))\s*\)?\s*$/",$str,$matches)) {

        switch ($matches[5]) {
            case "AND": $struct["comp"] = COMP_AND; break;
            case "OR": $struct["comp"] = COMP_OR; break;
            case "XOR": $struct["comp"] = COMP_XOR; break;
        }

        $temp = array();

        if (!empty($matches[4])) {
            // we have a sub-expression
            if (($err = parseExpr($matches[4], $temp, $vars)) !== true) {
                // a parse error occured, return the text
                return $err;
            }
            $struct["var1"] = $temp;
        } else {
            $struct["var1"] = $matches[3];

            $vars[$matches[3]] = rand(0,1); // add the name to the vars array
        }

        if (!empty($matches[9])) {
            // we have a sub-expression
            if (($err = parseExpr($matches[9], $temp, $vars)) !== true) {
                // a parse error occured, return the text
                return $err;
            }
            $struct["var2"] = $temp;
        } else {
            $struct["var2"] = $matches[8];

            $vars[$matches[8]] = rand(0,1); // add the name to the vars array
        }
        $struct["not1"] = $matches[1] == "!";
        $struct["not2"] = $matches[6] == "!";

        return true;
    } else {
        return "Parse error in '".$str."'";
    }
}


function calculateExpr($struct, $values) {
    if (is_array($struct["var1"])) {
        // subexpression, evaluate recursively
        $var1 = calculateExpr($struct["var1"], $values);
    } else {
        $var1 = $values[$struct["var1"]];
    }
    $var1 = ($struct["not1"] ? !$var1 : $var1);

    if (is_array($struct["var2"])) {
        // subexpression, evaluate recursively
        $var2 = calculateExpr($struct["var2"], $values);
    } else {
        $var2 = $values[$struct["var2"]];
    }
    $var2 = ($struct["not2"] ? !$var2 : $var2);

    switch ($struct["comp"]) {
        case COMP_AND: return $var1 and $var2; break;
        case COMP_OR: return $var1 or $var2; break;
        case COMP_XOR: return $var1 xor $var2; break;
    }

    return false;
}



$arr = array("aa AND bb", "aa OR bb", " (  aa AND bb  ) OR cc");
foreach ($arr as $a) {
    echo $a.":<br><pre>";
    $struct = array();
    $vars = array();
    if (($err = parseExpr($a, $struct, $vars)) !== true) {
        echo $err;
    } else {
        var_dump($struct);
        var_dump($vars);
        var_dump(calculateExpr($struct, $vars));
    }
    echo "</pre><p>";
}

?>