Tree evaluation

c go java js lua py vbs rkt scm pro

A tree traversal can be used to return the value of a logical expression tree, given that the values of the logical variables are known.

A dictionary is passed to the tree evaluation routine that maps variable names to values.

Diagnostic print statements are used to show a trace of the evaluation.

( X & Y ) | ( ( ! X ) & ( ! Y ) )

Here is the JavaScript code.

var treeList1 = [
	"op2",
	"or",
	[
		"op2",
		"and",
		["var", "x"],
		["var", "y"],
		],
	[
		"op2",
		"and",
		[
			"op1",
			"not",
			["var", "x"],
			],
		[
			"op1",
			"not",
			["var", "y"],
			],
		]
	];

function evaluate(tree1, varDict1) {
	var type1 = tree1[0];
	var value1 = 0;
	if (type1 == "op1") {
		var op1 = tree1[1];
		var right1 = tree1[2];
		var y1 = evaluate(right1,varDict1);
		if (op1 == "not") {
			value1 = 1 - y1;
			}
		console.log("\t"+op1+" "+y1+" is "+value1+"\n");
		}
	else if (type1 == "op2") {
		var op2 = tree1[1];
		var left1 = tree1[2];
		var right1 = tree1[3];
		var x1 = evaluate(left1,varDict1);
		var y1 = evaluate(right1,varDict1);
		if (op2 == "and") {
			value1 = x1 * y1;
			}
		else if (op2 == "or") {
			value1 = x1 + y1 - x1*y1;
			}
		else if (op2 == "xor") {
			value1 = (x1 + y1) % 2;
			}
		else if (op2 == "eqv") {
			value1 = (x1 + y1 + 1) % 2;
			}
		console.log("\t"+x1+" "+op2+" "+y1+" is "+value1+"\n");
		}
	else if (type1 == "var") {
		var name1 = tree1[1];
		value1 = varDict1[name1];
		console.log("\tvar "+name1+" is "+value1+"\n");
		}
	else if (type1 == "int") {
		value1 = tree1[1];
		console.log("\tint "+value1+" is "+value1+"\n");
		}
	return value1;
	}
console.log("(begin evaluation)\n");
varDict1 = {}
for (x1=0; x1<=1; x1++) {
	for (y1=0; y1<=1; y1++) {
		console.log("let x="+x1+" and y="+y1+"\n");
		varDict1["x"] = x1;
		varDict1["y"] = y1;
		var z1 = evaluate(treeList1,varDict1);
		console.log("then z="+z1+"\n");
		}
	}
console.log("(end evaluation)\n");

Here is the output of the JavaScript code.

(begin evaluation)

let x=0 and y=0

	var x is 0

	var y is 0

	0 and 0 is 0

	var x is 0

	not 0 is 1

	var y is 0

	not 0 is 1

	1 and 1 is 1

	0 or 1 is 1

then z=1

let x=0 and y=1

	var x is 0

	var y is 1

	0 and 1 is 0

	var x is 0

	not 0 is 1

	var y is 1

	not 1 is 0

	1 and 0 is 0

	0 or 0 is 0

then z=0

let x=1 and y=0

	var x is 1

	var y is 0

	1 and 0 is 0

	var x is 1

	not 1 is 0

	var y is 0

	not 0 is 1

	0 and 1 is 0

	0 or 0 is 0

then z=0

let x=1 and y=1

	var x is 1

	var y is 1

	1 and 1 is 1

	var x is 1

	not 1 is 0

	var y is 1

	not 1 is 0

	0 and 0 is 0

	1 or 0 is 1

then z=1

(end evaluation)

The next step is to separate the evaluate process, that takes a tree and an environment to evaluate a result, into two parts.

generate to generate code from the tree
execute to execute code given the environment.

The stack-based code is the basis for instruction set code.