How can (simple) parse trees from computer algebra be used to rearrange equations for a variable?
On the following website it is nicely explained conceptually how parse trees can be used to check if 2 expressions are equal. It is assumed that there are only numbers, variables, +-*/() and there are no variables in powers. I would not know how to deal with transcendentials but I don't need to use them. U is the unary minus with the value of -1 and it's used for subtraction. R is used for division similarly. The same site is in attachment in case the link stops working.
http://people.bath.ac.uk/masjhd/Slides/CICM2010-Sangwin-handout.pdf
I would like to see a similar explanation as the one on the site for rearranging simple equations to a variable. It is assumed that the only possible operations are */+- both sides or raising both sides to a power, factorisation and expanding brackets. I would not expect the software to solve quadratics except for these types: x^2-y=0 → x=y^(1/2). The main thing I'm after is which rules I need to make such a program work. (eg move an addition branch from one side to another if the branch doesn't have your variable and it starts from the top)
I think simplifying expressions given such a tree should be quite easy, so I should be able to do that myself.
Parse-trees.pdf
http://people.bath.ac.uk/masjhd/Slides/CICM2010-Sangwin-handout.pdf
I would like to see a similar explanation as the one on the site for rearranging simple equations to a variable. It is assumed that the only possible operations are */+- both sides or raising both sides to a power, factorisation and expanding brackets. I would not expect the software to solve quadratics except for these types: x^2-y=0 → x=y^(1/2). The main thing I'm after is which rules I need to make such a program work. (eg move an addition branch from one side to another if the branch doesn't have your variable and it starts from the top)
I think simplifying expressions given such a tree should be quite easy, so I should be able to do that myself.
Parse-trees.pdf
ASKER
Contrary to your expectations both will solve equations on the way to result.I don't know what you mean by that. However this exercise has 2 purposes: using the software on computers where I can't install software and as a challenge. I have previously found it way to difficult to make VBA communicate with other software, so I'd like to avoid that.
ASKER
Background of the question:
Previously I made an expression simplifier without parse trees. (it just went through the string again and again) However it cannot simplify multiplication or division by variables. (the coefficients still simplify) and it doesn't include powers.
I started to think about making a better (more general) solution for that purpose. I have only partially finished the algorithm for the parsing tree.
I would like to know if an equation solver based on the parse trees is worth pursuing. (eg the basic idea is not too complex and I can do it in a few hours). I find it hard to estimate the scope of this project because I don't know how a solver algorithm is supposed to work. I would expect though that once I have the program with the parsing trees simplifying expressions, the program for solving equations based on the previous one should be much easier than making the simplifier in the first place. Before I spend hours making another algorithm I would like to have a broad overview of how the algorithm is supposed to work to make sure I don't start something I can't finish.
Previously I made an expression simplifier without parse trees. (it just went through the string again and again) However it cannot simplify multiplication or division by variables. (the coefficients still simplify) and it doesn't include powers.
I started to think about making a better (more general) solution for that purpose. I have only partially finished the algorithm for the parsing tree.
I would like to know if an equation solver based on the parse trees is worth pursuing. (eg the basic idea is not too complex and I can do it in a few hours). I find it hard to estimate the scope of this project because I don't know how a solver algorithm is supposed to work. I would expect though that once I have the program with the parsing trees simplifying expressions, the program for solving equations based on the previous one should be much easier than making the simplifier in the first place. Before I spend hours making another algorithm I would like to have a broad overview of how the algorithm is supposed to work to make sure I don't start something I can't finish.
Use R for parse trees and export to xlsx? Excel is not the best tool for numeric methods.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
BigRat
Thanks,
ACM seems to have valuable information, however it seems to aimed at people already researching the topic. The publications I found were mostly on improving existing techniques rather than explaining the basics. Can you direct me to a publication explaining the basics, or some site aimed at people who haven't worked on SIGSAM yet? I heard students learning programming do these tasks in universities. Whatever information they get would probably be useful.
Thanks,
ACM seems to have valuable information, however it seems to aimed at people already researching the topic. The publications I found were mostly on improving existing techniques rather than explaining the basics. Can you direct me to a publication explaining the basics, or some site aimed at people who haven't worked on SIGSAM yet? I heard students learning programming do these tasks in universities. Whatever information they get would probably be useful.
ASKER
The reason for the B is that on the suggested sources there are a large amount of publications and thus it takes a long time to find the bits I actually need. While the comments are useful for starting, they don't help in estimating the scope of the project about which I asked in a comment before.
Contrary to your expectations both will solve equations on the way to result.