nicmart / expression-tree
A simple php library to build and dump expression trees.
Requires
- php: >=5.3.3
- nicmart/tree: dev-master
This package is auto-updated.
Last update: 2024-10-23 16:57:40 UTC
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