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?
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
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