nicmart/expression-tree

A simple php library to build and dump expression trees.

dev-master 2013-04-22 09:49 UTC

Requires

• php: >=5.3.3
• nicmart/tree: dev-master

MIT

• Nicolò Martini

README

In this library you can find some dumpers that convert simple expression trees to common string notations.

What is an expression tree?

Take for example a simple algebraic expression like

2 * (100 : (1 + 3)) * (98 - 7)

In evaluating this expression we have to find out which expressions has to be evaluated first, in which order, and their hierarchical relationship.

In this case the expression tree is

       *
      /|\
     / | \
    2  :  -
      /|   |\
     / |   | \
  100  +   98 7
      / \
     1   3

In such a tree leaf nodes are numbers and tree nodes are operators.

Building the tree

This library does not offer (at least now) an expression parser, and it is supposed you already have the expression in the tree format.

Since this library depends on nicmart/Tree library, you can build the tree with its Builder:

<?php
    $builder = new Tree\Builder\NodeBuilder;
    
    $builder
        ->value('*')
        ->leaf(2)
        ->tree(':')
            ->leaf(100)
            ->tree('+')
                ->leaf(1)
                ->leaf(3)
            ->end()
            ->tree('-')
                ->leaf(98)
                ->leaf(7)
            ->end()
        ->end()
    ;
    
    $expressionTree = $builder->getNode();

What you get is an instance of Tree\Node\Node that reflects the expressions.

Dumping

You can dump a tree expression giving your own implementation of the ExpressionTree\Dumper\NodeDumperInterface interface. However, included in this package you can find three dumper ready to use. They reflect the three classical way for traversing a tree (inorder, preorder and postorder traversing).

Infix dumper

Infix notation is the one commonly used in writing math expressions. In this notation operators are written bewtween operands.

The code

    $dumper = new ExpressionTree\Dumper\InfixDumper;
    
    echo $dumper->dump($expressionTree);

will print

2 * (100 : (1 + 3)) * (98 - 7)

Prefix dumper

In prefix notation (aka reverse Polish notation) opators are written before operands. The code The code

    $dumper = new ExpressionTree\Dumper\PrefixDumper;
    
    echo $dumper->dump($expressionTree);

will print

*(2 :(100 +(1 3)) -(98 7))

Postfix dumper

In postfix notation operators are suffixed, so they are written after operands. The code

    $dumper = new ExpressionTree\Dumper\PostfixDumper;
    
    echo $dumper->dump($expressionTree);

will print

(2 (100 (1 3)+): (98 7)-)*

Install

The best way to install ExpressionTree is through composer.

Just create a composer.json file for your project:

{
    "require": {
        "nicmart/expression-tree": "dev-master"
    }
}

Then you can run these two commands to install it:

$ curl -s http://getcomposer.org/installer | php
$ php composer.phar install

or simply run composer install if you have have already installed the composer globally.

Then you can include the autoloader, and you will have access to the library classes:

<?php
require 'vendor/autoload.php';

Tests

The library is fully tested. You can run the test suite with

phpunit