Postfix code to tree

c go java js lua py vbs rkt scm pro

The postfix code can be used, if needed, to reconstruct a tree. Thus, the postfix code can be used as a compact way to store a tree.

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

Here is the postfix representation.

x y & x ! y ! & |

Here is a list that can represent the code.

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

Here is a code example, with print statements interspersed to trace what is happening.

Here is the JavaScript code.

var codeList1 = [
	["var", "x"],
	["var", "y"],
	["op2", "and"],
	["var", "x"],
	["op1", "not"],
	["var", "y"],
	["op1", "not"],
	["op2", "and"],
	["op2", "or"]
	];
function codeToTree(codeList1) {
	var n1 = codeList1.length;
	var stack1 = [];
	for (var i1=0; i1 < n1; i1++) {
		var code1 = codeList1[i1];
		var type1 = code1[0];
		var value1;
		if (type1 == "var") {
			var name1 = code1[1];
			value1 = [type1, name1];
			}
		else if (type1 == "int") {
			var int1 = code1[1];
			value1 = [type1, int1];
			}
		else if (type1 == "op1") {
			var op1 = code1[1];
			var right1 = stack1.pop();
			value1 = [type1, op1, right1];
			}
		else if (type1 == "op2") {
			var op2 = code1[1];
			var right1 = stack1.pop();
			var left1 = stack1.pop();
			value1 = [type1, op2, left1, right1];
			}
		stack1.push(value1);
		}
	return stack1[0];
	}

var tree1 = codeToTree(codeList1)

console.log(tree1+"\n");

Here is the output of the JavaScript code.

op2,or,op2,and,var,x,var,y,op2,and,op1,not,var,x,op1,not,var,y

Note that the printed output of a list (above) is not pretty-printed, but printed using the default print behavior. For pretty-print purposes, a special-purpose routine is needed to output the structure in the form desired (omitted, left as an exercise).