How to use expression trees in PHP?

expression-trees php

Question

I'm currently making a PHP-program that solves equations. I've divided the input equation into an array so that each line in the array contains one term. (So. [0] = "+5x", [1] = "=", [2] = "-5", [3] = "+10". This is just a basic equation. The script also divides what is in () into sub-arrays. So for example 2x+(5-3x)=3(x+1) [0] = "+2*x", [1] = array([0] = "+5"....

However, I discovered expression trees that is the perfect thing to use in this equation-solver. I've searched the whole internet to learn it, but I can't find any websites that explain it in PHP (I know PHP OOP.). There are lots of pages explaining them in for example C, but as I only know PHP, that is of no help, because I don't understand the example code.

Can anyone here explain everything about expression trees in PHP and some practical example code?

Accepted Answer

Here is the algorithm described. you can implement this in PHP. I don't think anyone already implemented this in PHP (and distribute it as open source)

An example would be:

2*x+3*5-(6+9) = 0

Where:

  • * = priority 2
  • + = priority 1
  • ( = will increase priority of signs by 10
  • + (second +) = priority 11
  • ) = will decrease priority of signs by 10
  • = = in this case it is showing that there is another expression (0)

The highest priority is the most important - the one you need to do first

Using these rules you can create an expression tree...

So.. a way in which you have to create the expression and then interpret is:

2 x * 3 5 * + 6 9 + -

Explained:

  • 2 * x | (1)
  • 3 * 5 | (2)
  • (1) + (2) | (3)
  • 6 + 9 | (4)
  • (3) - (4) = final

I don't remember exactly how to write a tree I did this to a course in Computer Science but it was something like this:

                                     -
                                /         \
                                E         (E)
                                |          +
                                +         / \
                             /    \      6   9
                            E      E        
                            |      |    
                            *      *
                           / \    / \    
                          T   E   T  E
                          |   |   |  |
                          2   T   3  T
                              |      |
                              x      5

Now you have to create your own interpreter for this. You can use the interpreter pattern: PHP Interpreter


Popular Answer

I built an expression tree in PHP which parses math expressions and tries to solve the problem. You can find the source here http://codehackit.blogspot.com/2011/08/expression-parser-in-php.html

I pretty much explain all the details in that blog post but if you find any ambiguities just ask here ;)

Cheers, hope it helps or at least inspires



Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Is this KB legal? Yes, learn why
Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Is this KB legal? Yes, learn why