In this library you can find some dumpers that convert simple expression trees to common string notations.
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.
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.
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 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)
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))
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)-)*
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';
The library is fully tested. You can run the test suite with
phpunit