# Designing a basic Binary Expression Tree structure

## Preface

I need to generate some algebraic expressions for math testing in elementary school. The test should generate a list of expressions compiled according to certain rules and check the correctness of the solution. I have decided to represent the expression as a Binary expression tree.

At this stage, I only need to be able to convert the tree to infix form, as well as evaluate the result of the expression. I do not plan to expand this functionality, nor do I plan to add new types of nodes or extend existing ones. To generate expressions, a separate classes will be written that will build expressions recursively using only constructors. And I intentionally limit myself to int numbers only.

I'm not a professional developer and I don't know Java very well. This is more of a self study project. I need help to understand if I'm moving in the right direction.

## Subject

My recursive structure looks like this:

ExpressionTree = Leaf | Branch
Branch = ExpressionTree Operator ExpressionTree


#### ExpressionTree interface

import org.jetbrains.annotations.NotNull;

public sealed interface ExpressionTree permits Leaf, Branch {

@NotNull String toInfix();

int evaluate();
}


And I immediately have a question. I am 100% sure that no one but me will use this interface. And I am not going to write other implementations. Are these good enough reasons not to waste time writing the obvious Javadoc?

#### Leaf class

import org.jetbrains.annotations.NotNull;

public final class Leaf implements ExpressionTree {

private final int value;

public Leaf(int value) {
this.value = value;
}

@Override
public @NotNull String toInfix() {
return String.valueOf(value);
}

@Override
public int evaluate() {
return value;
}
}


#### Branch class

This is where the main work takes place. The evaluation of the branch is obvious. To represent an expression in infix form, you need to correctly place the brackets. And this is exactly the place where I most likely overdid it. How clear is the logic of the infix() method? How can this part of the code be improved? I am primarily interested in the readability and overall style of the code.

import org.jetbrains.annotations.NotNull;

import java.util.function.BiPredicate;
import java.util.function.Function;

public final class Branch implements ExpressionTree {

private final @NotNull Operator operator;
private final @NotNull ExpressionTree left;
private final @NotNull ExpressionTree right;

public Branch(final @NotNull Operator operator,
final @NotNull ExpressionTree left,
final @NotNull ExpressionTree right) {
this.operator = operator;
this.left = left;
this.right = right;
}

private static final BiPredicate<Operator, Operator> less =
(op1, op2) -> op1.getPrecedence() < op2.getPrecedence();
private static final BiPredicate<Operator, Operator> lessOrEqual =
(op1, op2) -> op1.getPrecedence() <= op2.getPrecedence();
private static final Function<Operator, BiPredicate<Operator, Operator>> selectPredicate =
op -> op.isCommutative() ? less : lessOrEqual;

private static boolean isParenthesisNeeded(BiPredicate<Operator, Operator> biPredicate,
ExpressionTree child,
Branch parent) {
if (child instanceof Branch) {
return biPredicate.test(((Branch) child).operator, parent.operator);
} else {
return false;
}
}

@Override
public @NotNull String toInfix() {
String leftExprFormat = isParenthesisNeeded(less, left, this) ? "(%s)" : "%s";
String rightExprFormat = isParenthesisNeeded(selectPredicate.apply(operator), right, this) ? "(%s)" : "%s";
String format = String.join(" ", leftExprFormat, "%s", rightExprFormat);

return format.formatted(left.toInfix(), operator.getSymbol(), right.toInfix());
}

@Override
public int evaluate() {
return operator.apply(left.evaluate(), right.evaluate());
}
}


#### Operator enum

import org.jetbrains.annotations.NotNull;

import java.util.function.IntBinaryOperator;

public enum Operator {
ADD("+", (a, b) -> a + b, 5, true),
SUB("-", (a, b) -> a - b, 5, false),
MUL("*", (a, b) -> a * b, 7, true),
DIV("/", (a, b) -> a / b, 7, false);

private final @NotNull String symbol;
private final @NotNull IntBinaryOperator op;
private final int precedence;
private final boolean commutative;

Operator(@NotNull String symbol,
@NotNull IntBinaryOperator op,
int precedence,
boolean commutative) {

this.symbol = symbol;
this.op = op;
this.precedence = precedence;
this.commutative = commutative;
}

public int apply(int left, int right) {
return op.applyAsInt(left, right);
}

public @NotNull String getSymbol() {
return symbol;
}

public int getPrecedence() {
return precedence;
}

public boolean isCommutative() {
return commutative;
}
}


I wrote tests and they are all green. I also already have an expression generator, but it still needs some work.

I am mainly interested in my Branch and Operator classes. Is it OK to implement calculation logic directly in enum?

Thanks for any feedback.

While the expression tree is in fact a tree-structure, the elements in the tree are operators and operands. Using overly generic non-representative names makes it more difficult to follow the code. If you revise it as follows, the names describe the function of the classes (and you will not have a hard time trying to figure out a name for unary operator class when you decide to add it :)).

Expression = Operand | BinaryOperator
BinaryOperator = BiFunction Expression Expression


K.H.'s suggestion for separating the infix formatting into a separate InfixFormatter class is a good one and you should do it. Putting the formatting code in the expression tree violates single responsibility principle and makes it difficult to add different kinds of formatting.

Are these good enough reasons not to waste time writing the obvious Javadoc?

You don't need a reason to not write obvious documentation. Obvious documentation should never be written. The trick is to know when documentation is non-obvious and needs to be written. For example, if you don't rename your classes, you would have to write documentation for the Branch class to explain that is in fact a binary operator. If you rename it, the class name already tells it's function and you don't need documentation for it. An easy way to figure out what needs to be documented is to leave the code alone and come back to it a year later. You will instantly see the places you should have documented. The lambdas used in the infix formatting sure look like something that might need to be explained to future you.

Is it OK to implement calculation logic directly in enum?

It depends. Personally I don't like code in enums. For this case it may be justifiable. But the question probably should be that is it a good idea to define the calculation logic as enums? My opinion is that it's not. Enums are closed classes and you can't add any operators now without changing the enum. Going to extreme, one might argue whether the Operators even need to know what their symbols are? The symbols exist only for display purposes and isn't displaying the responsibility of InfixFormatter and InfixParser? Should division use / or ÷? Should multiplication use * or ×? But I digress... :)

Using IDE-specific annotations is not a long-term solution. While they provide static code validation help, they don't provide any runtime assistance if your classes are used by someone else. Also they add an unnecessary dependency to a third party library. It is better to use Objects.requireNonNull(...) in public APIs. A good static code analyzer will be able to follow the execution path and show warnings about misuse. Also having @NotNull annotation on both final class fields and the constructor parameters that are assigned to them is redundant. The @NotNull annotations in the Operator enum are mostly unnecessary as the fields and the constructor are not public.

• Great explanation +1 Commented Dec 23, 2022 at 7:26

• Is toInfix really necessary? Shouldn't toString be enough?
• Should the code Branch.toInfix be in that class? I would consider putting this into operator itself or a class (InfixFormatter?) that displays the expression in infix notation so that it's possible to use different notation. I know you won't need it, but just thinking about it gives more clues about where this code should be.
• Yes it is okay to put code in enums, especially if you are trying to do objective oriented and not functional! Quite contrary it is a code smell when enum has flags that other classes are using for a logic (ex. commutative). Add even more if it makes sense!
• Shouldn't toString be enough? -- I'm assuming that the toString() method is primarily for debugging and logging purposes. I am satisfied with the default implementation of this method for enum type. On the other hand, I can represent my tree in different String forms. It is quite possible that a prefix form is needed, or any other form of representation of my tree. I think a separate method serves my needs better. Commented Dec 15, 2022 at 16:03