A Tree-based Approach to Mathematical Functions

Introduction

In one of my latest projects (the code for which can be found here) I sought to represent mathematical functions hierarchically. The idea is fairly simple. Each of the basic elementary operators $(+, -, ×, \div)$ performs an operation on two operands. The operands can be thought of as children of the operator. For example, the expression $5+3$ can be represented as a addition operation with its first child being the number $5$ and its second child being the number $2$.

Numbers are also functions, except that they have no children. They make up the leaves of the function tree.

The children of an operator can be any function, including other operators. They must only be a function, meaning that they could be other operators. For example, take the expression $5+3+2$. The expression can be rewritten as $(5+3)+2$. It can be represented as a tree with addition operation being the root, the expression $(5+3)$ being the first child and the number $2$ as the second child.

The concept can be extended to other functions such as exponentiation, trigonometric functions, and logarithms. It doesn't matter whether the operator takes one or two (or zero, as with numbers and variables) operands.

Precedence and Evaluation

The function tree is evaluated in a depth-first, recursive manner. The functions that are farther down the tree have a higher precedence than those above, and get evaluated first. Leaf nodes (numbers are variables) have the highest precedence of all. The precedence of the function is based upon its mathematically defined precedence (think BEDMAS) and its 'depth' within brackets. The more brackets by which a function is surrounded, the higher its precedence.

For example, take the function $2+3\times4$. Since multiplication has a higher precedence than addition, the multiplication operation must be evaluated before the addition operation. It is thus placed as a child of the addition operator, and gets evaluated first.

Building

How can one algorithmically create the tree structure out of a function in standard infix notation?

The Builder itself needs to keep track of the current function - the last one placed in the tree. That way it knows where to pick back up when another one is added.

Each function must be wrapped in a Node for the building process. The Node stores some extra information about the function. The Node keeps track of the parent Node, as well as the bracket depth of the function. Since the parent and the bracket depth are not required after the tree is built, they aren't stored in the Function object itself.

When a new node gets inserted into the tree, its precedence gets compared to the current node. Here is the code:

private int comparePrecedence(FunctionNode other)  {
    if (getBracketDepth() > other.getBracketDepth())
        return 1;
    if (getBracketDepth() < other.getBracketDepth())
        return -1;
    return (getFunction().getPrecedence().compareTo(other
            .getFunction().getPrecedence()));
}

There are three potential cases. Either the new node has a lower, equal, or greater precedence than the current node.

If the new node has a higher precedence, things are easy. The new node is just added as a child of the current node.

If the new node has an equal precedence to the current one, it's a little more complicated. Functions can be either right associative or left associative. If a function is right associative, that means that if multiple occurrences of it are in a row, they should be evaluated right to left. Left associativity is the opposite. Exponentiation is an example of function that is right associative. If the new node is right associative, it's added as a child. Since new Nodes contain functions to the right of the current one (the entire function is being read left to right), we want right associative Nodes to be inserted as children and thus evaluated first. Conversely, left associative Nodes are inserted as the parent of the current Node.

The final case is when the new node has a lower precedence than the current node. In this case, we traverse up the tree until we reach a node with a lower precedence, or the top of the tree. The node is then inserted.

Take a look at the source code of the building algorithm in its entirety here.