<?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>";
}

?>