Binary Expression Tree that evaluates Postfix input

Question

My code for a Binary Expression Tree that takes postfix input from the user and recursively builds and evaluates the expression. Proper input can be assumed.

class Node {
 constructor(data) {
 this.data = data,
 this.left = null,
 this.right = null
 }
}
class BinaryExpressionTree {
 constructor() {
 this.stack = [],
 this.operators = ['+', '-', '*', '/', '(', ')', '^']
 }
 buildExpressionTree(expression) {
 expression.forEach((char) => {
 const node = new Node(char)
 if (!this.operators.includes(char)) {
 node.data = parseInt(node.data, 10)
 this.stack.push(node)
 } else {
 const r = this.stack.pop()
 const l = this.stack.pop()
 node.right = r
 node.left = l
 this.stack.push(node)
 }
 }) 
 }
 operate(n1, o, n2) { // operand in middle
 const operations = {
 '^': function (a, b) {
 return a ** b
 },
 '*': function (a, b) {
 return a * b
 },
 '/': function (a, b) {
 return a / b
 },
 '+': function (a, b) {
 return a + b
 },
 '-': function (a, b) {
 return a - b
 }
 } 
 return operations[o](n1, n2) 
 }
 evaluate(root) {
 if (!root.data) { 
 return 0
 }
 if (!root.left && !root.right) {
 return root.data
 }
 let leftSum = this.evaluate(root.left)
 let rightSum = this.evaluate(root.right)
 return this.operate(leftSum, root.data, rightSum)
 } 
}
const input = ['8', '2', '^', '6', '+', '2', '10', '*', '2', '/', '-']
const testTree = new BinaryExpressionTree()
testTree.buildExpressionTree(input)
const answer = testTree.evaluate(testTree.stack[0])
console.log('prefix input: ', input.join(' '))
console.log('answer: ', answer)

Output:

postfix input: 8 2 ^ 6 + 2 10 * 2 / -
answer: 60

Any feedback is welcome.

• janos: "prefix input" is a typo, right? You meant "postfix", right?
• MadHatter: Indeed I do. 64/3.

Answer 1

Validate inputs

It's not mentioned if we can assume the input is always valid.

Aside from parsing errors, if the input is not in valid postfix form, the parsed tree may be broken, consider for example some infix inputs such as 1 + 2.

OOP and encapsulation

The stack used in parsing the input is accessible outside of the class. I don't understand why, and also why is it retained at all after the parsing. When working with trees, the root is the most natural critical piece, I find it unexpected to be aware of a stack instead.

I think input validation would have revealed this issue: at the end of parsing a well-formed non-empty expression, the stack should have precisely one item in it. That item could be stored as the root of the tree.

Users of BinaryExpressionTree must know how to access the root, so that they can call evaluate on it. From a user's perspective, it seems a bit strange to pass the tree's own root to itself. It would be more natural to be able to call evaluate without arguments.

A different kind of encapsulation issue is the definition of operations. Since these are common to all operations, it would be better to define them outside of the operate function, to avoid unnecessary repeated evaluations.

After operations are removed from the operate function, it will look something like this:

operate(n1, o, n2) { // operand in middle
 return operations[o](n1, n2) 
}

And at this point, it will be easier to inline it, so that callers don't have to know the correct order of parameters, which reduces the mental burden and less prone to simple mistakes.

Don't repeat yourself

The presumably supported operators are in two places:

• In the constructor as a list of symbols
• In operate as keys in a map of functions

From the constructor it looks like ( and ) are supported, but actually they are not handled during parsing.

It would be better to define the operator functions once, and use that mapping during parsing.

Improving some names

• buildExpressionTree duplicates terms from the name of the class. We know we're working with an expression tree. I'd call this parse.

• I find leftSum and rightSum a bit misleading, suggesting "add" operations behind. In truth these values are results of the left and right sub-expressions, so leftResult and rightResult would be better.

• The name l is used when parsing the expression. With some fonts, this letter can be difficult to distinguish from 1 or |, so I avoid it. left would be a good name there. Or in the posted code, inlining is also fine.

Use const instead of let

These should use const instead of let:

let leftSum = this.evaluate(root.left)
let rightSum = this.evaluate(root.right)

Use arrow functions

The operations could be defined more compactly using arrow functions:

const operations = {
 '^': (a, b) => a ** b,
 '*': (a, b) => a * b,
 '/': (a, b) => a / b,
 '+': (a, b) => a + b,
 '-': (a, b) => a - b
} 

• MadHatter: Refactored after feedback: github.com/Sebastion-Vigil/parse-driver/blob/main/…

Answer 2

Some additional notes on your code.

• Keep code noise low. Code noise is any code that is not required and gets in the way of maintainability and readability.

• Avoid single use variables.

• Keep names short.

• Never expose anything that is not required to use the Object. If you must use the class syntax, use # for private members. Create static members rather than create a copy for each instance.

• Don't repeat names. Eg BinaryExpressionTree.buildExpressionTree can be BinaryExpressionTree.build.

• Use undefined (the default assignment) rather than the object null.

• Use semicolons.

• Constructors are only needed if the instantiation needs data (arguments).

• Use Number to evaluate numbers (not parseInt).

• Use isNaN to test if a value is or is not a number.

• Use double quotes.

Rewrite

Using class syntax

const Expression = (() => class E {
 static #Node = (data, right, left) => ({data, right, left});
 static #operate = (n1, o, n2) => E.#operations[o](n1, n2);
 static #operations = {
 "^"(a, b) { return a ** b },
 "*"(a, b) { return a * b },
 "/"(a, b) { return a / b },
 "+"(a, b) { return a + b },
 "-"(a, b) { return a - b }
 };
 stack = [];
 build(expression) {
 for (const op of expression) {
 if (!isNaN(op)) {
 this.stack.push(E.#Node(Number(op)));
 } else if (E.#operations[op]) {
 this.stack.push(E.#Node(op, this.stack.pop(), this.stack.pop()));
 }
 }
 }
 eval(node) {
 if (node.data) { 
 return node.left && node.right ? 
 E.#operate(this.eval(node.left), node.data, this.eval(node.right)) :
 node.data;
 }
 return 0;
 } 
 }
)();

• MadHatter: Your feedback is gold; in my refactored code I was torn between Number() and parseFloat(); a brief explanation of why the former is better than the latter in this case?
• Blindman67: parseFloat and parseInt (apart from ints radix) will parse a string even if the string contains a malformed number. Eg parseFloat("1..1") === 1 and Number("1..1") === NaN Though you can predicate parseFloat with isNaN eg isNaN("1..1) === true