mathjs/docs/expressions/expression_trees.md

# Expression trees

When parsing an expression via `math.parse(expr)`, math.js generates an
expression tree and returns the root node of the tree. An expression tree can
be used to analyze, manipulate, and evaluate expressions.

Example:

```js
const node = math.parse('sqrt(2 + x)')
```

In this case, the expression `sqrt(2 + x)` is parsed as:

```
  FunctionNode    sqrt
                   |
  OperatorNode     +
                  / \
  ConstantNode   2   x   SymbolNode
```

Alternatively, this expression tree can be build by manually creating nodes:

```js
const node1 = new math.expression.node.ConstantNode(2)
const node2 = new math.expression.node.SymbolNode('x')
const node3 = new math.expression.node.OperatorNode('+', 'add', [node1, node2])
const node4 = new math.expression.node.FunctionNode('sqrt', [node3])
```

The resulting expression tree with root node `node4` is equal to the expression
tree generated by `math.parse('sqrt(2 + x)')`.


## API

### Methods

All nodes have the following methods:

-   `clone() : Node`

    Create a shallow clone of the node.
    The node itself is cloned, its childs are not cloned.

-   `cloneDeep() : Node`

    Create a deep clone of the node.
    Both the node as well as all its childs are cloned recursively.

-   `compile() : Object`

    Compile an expression into optimized JavaScript code. `compile` returns an
    object with a function `eval([scope])` to evaluate. Example:

    ```js
    const node = math.parse('2 + x') // returns the root Node of an expression tree
    const code = node.compile()      // returns {eval: function (scope) {...}}
    const eval = code.eval({x: 3})   // returns 5
    ```

-   `eval([scope]) : Object`

    Compile and eval an expression, this is the equivalent of doing
    `node.compile().eval(scope)`. Example:

    ```js
    const node = math.parse('2 + x') // returns the root Node of an expression tree
    const eval = node.eval({x: 3})   // returns 5
    ```

-   `equals(other: Node) : boolean`

    Test whether this node equals an other node. Does a deep comparison of the
    values of both nodes.

-   `filter(callback: function) : Node[]`

    Recursively filter nodes in an expression tree. The `callback` function is
    called as `callback(node: Node, path: string, parent: Node) : boolean` for
    every node in the tree, and must return a boolean. The function `filter`
    returns an array with nodes for which the test returned true.
    Parameter `path` is a string containing a relative JSON Path.

    Example:

    ```js
    const node = math.parse('x^2 + x/4 + 3*y')
    const filtered = node.filter(function (node) {
      return node.isSymbolNode && node.name === 'x'
    })
    // returns an array with two entries: two SymbolNodes 'x'
    ```

-   `forEach(callback: function) : Node[]`

    Execute a callback for each of the child nodes of this node. The `callback`
    function is called as `callback(child: Node, path: string, parent: Node)`.
    Parameter `path` is a string containing a relative JSON Path.

    See also `traverse`, which is a recursive version of `forEach`.

    Example:

    ```js
    const node = math.parse('3 * x + 2')
    node.forEach(function (node, path, parent) {
      switch (node.type) {
        case 'OperatorNode':
          console.log(node.type, node.op)
          break
        case 'ConstantNode':
          console.log(node.type, node.value)
          break
        case 'SymbolNode':
          console.log(node.type, node.name)
          break
        default:
          console.log(node.type)
      }
    })
    // outputs:
    //   OperatorNode *
    //   ConstantNode 2
    ```

-   `map(callback: function) : Node[]`

    Transform a node. Creates a new Node having it's childs be the results of
    calling the provided callback function for each of the childs of the original
    node. The `callback` function is called as `callback(child: Node, path: string,
    parent: Node)` and must return a Node. Parameter `path` is a string containing
    a relative JSON Path.

    See also `transform`, which is a recursive version of `map`.

-	`toHTML(options: object): string`

	Get a HTML representation of the parsed expression. Example:

    ```js
    const node = math.parse('sqrt(2/3)')
    node.toString()
	// returns
	// <span class="math-function">sqrt</span>
	// <span class="math-paranthesis math-round-parenthesis">(</span>
	// <span class="math-number">2</span>
	// <span class="math-operator math-binary-operator math-explicit-binary-operator">/</span>
	// <span class="math-number">3</span>
	// <span class="math-paranthesis math-round-parenthesis">)</span>
    ```

    Information about the available HTML classes in [HTML Classes](html_classes.md).
    Information about the options in [Customization](customization.md#custom-html-latex-and-string-output).

-   `toString(options: object) : string`

    Get a string representation of the parsed expression. This is not exactly
    the same as the original input. Example:

    ```js
    const node = math.parse('3+4*2')
    node.toString()  // returns '3 + (4 * 2)'
    ```

    Information about the options in [Customization](customization.md#custom-html-latex-and-string-output).

-   `toTex(options: object): string`

    Get a [LaTeX](https://en.wikipedia.org/wiki/LaTeX) representation of the
    expression. Example:

    ```js
    const node = math.parse('sqrt(2/3)')
    node.toTex() // returns '\sqrt{\frac{2}{3}}'
    ```

    Information about the options in [Customization](customization.md#custom-html-latex-and-string-output).

-   `transform(callback: function)`

    Recursively transform an expression tree via a transform function. Similar
    to `Array.map`, but recursively executed on all nodes in the expression tree.
    The callback function is a mapping function accepting a node, and returning
    a replacement for the node or the original node. Function `callback` is
    called as `callback(node: Node, path: string, parent: Node)` for every node
    in the tree, and must return a `Node`. Parameter `path` is a string containing
    a relative JSON Path.

    For example, to replace all nodes of type `SymbolNode` having name 'x' with a
    ConstantNode with value `3`:

    ```js
    const node = math.parse('x^2 + 5*x')
    const transformed = node.transform(function (node, path, parent) {
      if (node.isSymbolNode && node.name === 'x') {
        return new math.expression.node.ConstantNode(3)
      }
      else {
        return node
      }
    })
    transformed.toString() // returns '3 ^ 2 + 5 * 3'
    ```

-   `traverse(callback)`

    Recursively traverse all nodes in a node tree. Executes given callback for
    this node and each of its child nodes. Similar to `Array.forEach`, except
    recursive.
    The callback function is a mapping function accepting a node, and returning
    a replacement for the node or the original node. Function `callback` is
    called as `callback(node: Node, path: string, parent: Node)` for every node
    in the tree. Parameter `path` is a string containing a relative JSON Path.
    Example:

    ```js
    const node = math.parse('3 * x + 2')
    node.traverse(function (node, path, parent) {
      switch (node.type) {
        case 'OperatorNode':
          console.log(node.type, node.op)
          break
        case 'ConstantNode':
          console.log(node.type, node.value)
          break
        case 'SymbolNode':
          console.log(node.type, node.name)
          break
        default:
          console.log(node.type)
      }
    })
    // outputs:
    //   OperatorNode +
    //   OperatorNode *
    //   ConstantNode 3
    //   SymbolNode x
    //   ConstantNode 2
    ```


### Properties

Each `Node` has the following properties:

-   `comment: string`

    A string holding a comment if there was any in the expression, or else the
    string will be empty string. A comment can be attached to the root node of
    an expression or to each of the childs nodes of a `BlockNode`.

-   `isNode: true`

    Is defined with value `true` on Nodes. Additionally, each type of node
    adds it's own flag, for example a `SymbolNode` as has a property
    `isSymbolNode: true`.

-   `type: string`

    The type of the node, for example `'SymbolNode'` in case of a `SymbolNode`.


## Nodes

math.js has the following types of nodes. All nodes are available at the
namespace `math.expression.node`.


### AccessorNode

Construction:

```
new AccessorNode(object: Node, index: IndexNode)
```

Properties:

- `object: Node`
- `index: IndexNode`
- `name: string` (read-only) The function or method name. Returns an empty string when undefined.

Examples:

```js
const node1 = math.parse('a[3]')

const object = new math.expression.node.SymbolNode('a')
const index = new math.expression.node.IndexNode([3])
const node2 = new math.expression.node.AccessorNode(object, index)
```


### ArrayNode

Construction:

```
new ArrayNode(items: Node[])
```

Properties:

- `items: Node[]`

Examples:

```js
const node1 = math.parse('[1, 2, 3]')

const one    = new math.expression.node.ConstantNode(1)
const two    = new math.expression.node.ConstantNode(2)
const three  = new math.expression.node.ConstantNode(3)
const node2  = new math.expression.node.ArrayNode([one, two, three])
```


### AssignmentNode

Construction:

```
new AssignmentNode(object: SymbolNode, value: Node)
new AssignmentNode(object: SymbolNode | AccessorNode, index: IndexNode, value: Node)
```

Properties:

- `object: SymbolNode | AccessorNode`
- `index: IndexNode | null`
- `value: Node`
- `name: string` (read-only) The function or method name. Returns an empty string when undefined.

Examples:

```js
const node1 = math.parse('a = 3')

const object = new math.expression.node.SymbolNode('a')
const value = new math.expression.node.ConstantNode(3)
const node2 = new math.expression.node.AssignmentNode(object, value)
```


### BlockNode

A `BlockNode` is created when parsing a multi line expression like `a=2;b=3` or
`a=2\nb=3`. Evaluating a `BlockNode` returns a `ResultSet`. The results can be
retrieved via `ResultSet.entries` or `ResultSet.valueOf()`, which contains
an `Array` with the results of the visible lines (i.e. lines not ending with
a semicolon).

Construction:

```
block = new BlockNode(Array.<{node: Node} | {node: Node, visible: boolean}>)
```

Properties:

- `blocks: Array.<{node: Node, visible: boolean}>`

Examples:

```js
const block1 = math.parse('a=1; b=2; c=3')

const a = new math.expression.node.SymbolNode('a')
const one = new math.expression.node.ConstantNode(1)
const ass1 = new math.expression.node.AssignmentNode(a, one)

const b = new math.expression.node.SymbolNode('b')
const two = new math.expression.node.ConstantNode(2)
const ass2 = new math.expression.node.AssignmentNode(b, two)

const c = new math.expression.node.SymbolNode('c')
const three = new math.expression.node.ConstantNode(3)
const ass3 = new math.expression.node.AssignmentNode(c, three)

const block2 = new BlockNode([
  {node: ass1, visible: false},
  {node: ass2, visible: false},
  {node: ass3, visible: true}
])
```


### ConditionalNode

Construction:

```
new ConditionalNode(condition: Node, trueExpr: Node, falseExpr: Node)
```

Properties:

- `condition: Node`
- `trueExpr: Node`
- `falseExpr: Node`

Examples:

```js
const node1 = math.parse('a > 0 ? a : -a')

const a         = new math.expression.node.SymbolNode('a')
const zero      = new math.expression.node.ConstantNode(0)
const condition = new math.expression.node.OperatorNode('>', 'larger', [a, zero])
const trueExpr  = a
const falseExpr = new math.expression.node.OperatorNode('-', 'unaryMinus', [a])
const node2     = new math.expression.node.ConditionalNode(condition, trueExpr, falseExpr)
```

### ConstantNode

Construction:

```
new ConstantNode(value: *)
```

Properties:

- `value: *`

Examples:

```js
const node1 = math.parse('2.4')

const node2 = new math.expression.node.ConstantNode(2.4)
const node3 = new math.expression.node.ConstantNode('foo')
```


### FunctionAssignmentNode

Construction:

```
new FunctionAssignmentNode(name: string, params: string[], expr: Node)
```

Properties:

- `name: string`
- `params: string[]`
- `expr: Node`

Examples:

```js
const node1 = math.parse('f(x) = x^2')

const x      = new math.expression.node.SymbolNode('x')
const two    = new math.expression.node.ConstantNode(2)
const expr   = new math.expression.node.OperatorNode('^', 'pow', [x, 2])
const node2  = new math.expression.node.FunctionAssignmentNode('f', ['x'], expr)
```


### FunctionNode

Construction:

```
new FunctionNode(fn: Node | string, args: Node[])
```

Properties:

- `fn: Node | string` (read-only) The object or function name which to invoke.
- `args: Node[]`

Examples:

```js
const node1 = math.parse('sqrt(4)')

const four  = new math.expression.node.ConstantNode(4)
const node3 = new math.expression.node.FunctionNode(new SymbolNode('sqrt'), [four])
```


### IndexNode

Construction:

```
new IndexNode(dimensions: Node[])
new IndexNode(dimensions: Node[], dotNotation: boolean)
```

Each dimension can be a single value, a range, or a property. The values of
indices are one-based, including range end.

An optional property `dotNotation` can be provided describing whether this index
was written using dot notation like `a.b`, or using bracket notation
like `a["b"]`. Default value is `false`. This information is used when
stringifying the IndexNode.

Properties:

- `dimensions: Node[]`
- `dotNotation: boolean`

Examples:

```js
const node1 = math.parse('A[1:3, 2]')

const A     = new math.expression.node.SymbolNode('A')
const one   = new math.expression.node.ConstantNode(1)
const two   = new math.expression.node.ConstantNode(2)
const three = new math.expression.node.ConstantNode(3)

const range = new math.expression.node.RangeNode(one, three)
const index = new math.expression.node.IndexNode([range, two])
const node2 = new math.expression.node.AccessNode(A, index)
```

### ObjectNode

Construction:

```
new ObjectNode(properties: Object.<string, Node>)
```

Properties:

- `properties: Object.<string, Node>`

Examples:

```js
const node1 = math.parse('{a: 1, b: 2, c: 3}')

const a = new math.expression.node.ConstantNode(1)
const b = new math.expression.node.ConstantNode(2)
const c = new math.expression.node.ConstantNode(3)
const node2 = new math.expression.node.ObjectNode({a: a, b: b, c: c})
```


### OperatorNode

Construction:

```
new OperatorNode(op: string, fn: string, args: Node[])
```

Additional methods:

-   `isUnary() : boolean`

    Returns true when the `OperatorNode` contains exactly one argument,
    like with a unary minus:

    ```js
    const a = new math.expression.node.ConstantNode(2)
    const b = new math.expression.node.OperatorNode('-', 'unaryMinus', [a])
    b.isUnary() // true
    ```

-   `isBinary() : boolean`

    Returns true when the `OperatorNode` contains exactly two arguments,
    like with most regular operators:

    ```js
    const a = new math.expression.node.ConstantNode(2)
    const b = new math.expression.node.ConstantNode(3)
    const c = new math.expression.node.OperatorNode('+', 'add', [a, b])
    c.isBinary() // true
    ```

Properties:

- `op: string`
- `fn: string`
- `args: Node[]`

Examples:

```js
const node1 = math.parse('2.3 + 5')

const a     = new math.expression.node.ConstantNode(2.3)
const b     = new math.expression.node.ConstantNode(5)
const node2 = new math.expression.node.OperatorNode('+', 'add', [a, b])
```

### ParenthesisNode

Construction:

```
new ParenthesisNode(content: Node)
```

Properties:

- `content: Node`

Examples:

```js
const node1 = math.parse('(1)')

const a     = new math.expression.node.ConstantNode(1)
const node2 = new math.expression.node.ParenthesisNode(a)
```

### RangeNode

Construction:

```
new RangeNode(start: Node, end: Node [, step: Node])
```

Properties:

- `start: Node`
- `end: Node`
- `step: Node | null`

Examples:

```js
const node1 = math.parse('1:10')
const node2 = math.parse('0:2:10')

const zero = new math.expression.node.ConstantNode(0)
const one = new math.expression.node.ConstantNode(1)
const two = new math.expression.node.ConstantNode(2)
const ten = new math.expression.node.ConstantNode(10)

const node3 = new math.expression.node.RangeNode(one, ten)
const node4 = new math.expression.node.RangeNode(zero, ten, two)
```

### RelationalNode

Construction:

```
new RelationalNode(conditionals: string[], params: Node[])
```

`conditionals` is an array of strings, each of which may be 'smaller', 'larger', 'smallerEq', 'largerEq', 'equal', or 'unequal'. The `conditionals` array must contain exactly one fewer item than `params`.

Properties:

- `conditionals: string[]`
- `params: Node[]`

A `RelationalNode` efficiently represents a chained conditional expression with two or more comparison operators, such as `10 < x <= 50`. The expression is equivalent to `10 < x and x <= 50`, except that `x` is evaluated only once, and evaluation stops (is "short-circuited") once any condition tests false. Operators that are subject to chaining are `<`, `>`, `<=`, `>=`, `==`, and `!=`. For backward compatibility, `math.parse` will return an `OperatorNode` if only a single conditional is present (such as `x > 2`).

Examples:

```js

const ten = new Math.expression.node.ConstantNode(10)
const x = new Math.expression.node.SymbolNode('x')
const fifty = new Math.expression.node.ConstantNode(50)

const node1 = new math.expression.node.RelationalNode(['smaller', 'smallerEq'], [ten, x, fifty])
const node2 = math.parse('10 < x <= 50')
```


### SymbolNode

Construction:

```
new SymbolNode(name: string)
```

Properties:

- `name: string`

Examples:

```js
const node = math.parse('x')

const x = new math.expression.node.SymbolNode('x')
```