Making a math parser
Hello, I''m interested in trying to program a math parser. My final objective is to make one that can
*) Read something like "cos(5*3)+4*8^2-7" and give the answer to it
*) Read something like "x^2 + sin(x)/x" and store it in some sort of class that can contain Any Mathematical Function
*) Try to integrate that (both numerically and analitically!)
But I''m going to need some help with some questions...
Basicly this is almost like making something like maple... is it even humanly possible to do that, or should I give up?
Are there good resources about making a parser to read mathematical expressions? I''m not too good at working with strings, and recogising a mathematical expression in them seems very hard. It should recognise things like the order of operations, operators, functions like cos and sin, brackets, and of course decimal numbers and all there notation variants (scientific notation etc).
What''s a good way to make a sort of class that can contain any mathematical function (well, I don''t mean ANY one, but any function that you can make out of expressions with operators, one or more unknown variables, parameters, cos, sin, ...)?
I know a bit about algorithms to do numerical integration (and differentiation and such), but how to do it analitically? A quite intelligent one that can do more than just simple functions, also things like "repeated integration" and other tricks. Any resources about this?
Any help would be greatly appreciated! Thanks.
quote:Original post by Boops
Basicly this is almost like making something like maple... is it even humanly possible to do that, or should I give up?
Well, assuming maple was written by humans, i guess it would be humanly possible...
The first two parts i think are feasible, but that last part i think would be very hard indeed.
I also know that the first two goals are definately obtainable. I have doen it for a class before...
What you probobly want to use are expression trees. To store x+y, hold the tree:
These expression trees can easily be evaluated, simplified, etc. I wrote the part in my calculator that does basic derivatives in 20mins cause its all recursive and simple rules.
Are you confused about the parsing also? It just takes some thinking and working out on paper...
Integration is a whole nothing story
My home page!!!
Find out about my diy LCD projector and programming projects!
What you probobly want to use are expression trees. To store x+y, hold the tree:
x + y = 2x+cos(z/y) = + ''+'' / \ / \x y ''*'' ''cos'' / \ | 2 x ''/'' / \ z y
These expression trees can easily be evaluated, simplified, etc. I wrote the part in my calculator that does basic derivatives in 20mins cause its all recursive and simple rules.
Are you confused about the parsing also? It just takes some thinking and working out on paper...
Integration is a whole nothing story
My home page!!!
Find out about my diy LCD projector and programming projects!
The Bison manual contains an implementation of a multi-function calculator.
--
AnkhSVN - A Visual Studio .NET Addin for the Subversion version control system.
[Project site] [Blog] [RSS] [Browse the source] [IRC channel]
--
AnkhSVN - A Visual Studio .NET Addin for the Subversion version control system.
[Project site] [Blog] [RSS] [Browse the source] [IRC channel]
Look up the CYK (Cocke-Younger-Kasami) algorithm for parsing strings generated by a context-free grammar. It''s a dynamic programming approach to parsing programming languages (or math) that seems to work quite well.
Basically, the steps are as follows:
1. Convert infix expression into postfix expression. In infix notation, operators are written between the operands, using parentheses to resolve operator precedence. In postfix notation, operators are written after the operands, and no parentheses are needed. The infix expression "cos(5 * 3) + 4 * 8 ^ 2 - 7" would become "3 5 * cos 4 8 2 ^ * + 7 -" in postfix.
2. Convert a postfix expression into an expression tree (like what Tazzel3D posted) using a stack. This is relatively easy, since all you have to do is push operands, and whenever an operator is encountered, you pop two operands, make them the child nodes of the operator node, and push the new conglomerate back on the stack.
3. Evaluate or simplify the expression tree via math.
Step 1 can be tricky, but there are several well-known algorithms for converting infix to postfix. Step 3 is the hardest, especially when performing such tasks as expression simplification and integration. MathematicaIntegrate function works by doing some weird transformations and guessing at the form of the solution, differentiating that, and then solving for the constants in a non-intuitive way. Many times the results can not be expressed in terms of simple mathematical functions - they can only be expressed in terms of other functions, often named after the Mathameticians who discovered them, that are in fact defined as integrals or solutions to differential equations. Some intregrals can''t even be expressed like that, such as the integral of x^x.
1. Convert infix expression into postfix expression. In infix notation, operators are written between the operands, using parentheses to resolve operator precedence. In postfix notation, operators are written after the operands, and no parentheses are needed. The infix expression "cos(5 * 3) + 4 * 8 ^ 2 - 7" would become "3 5 * cos 4 8 2 ^ * + 7 -" in postfix.
2. Convert a postfix expression into an expression tree (like what Tazzel3D posted) using a stack. This is relatively easy, since all you have to do is push operands, and whenever an operator is encountered, you pop two operands, make them the child nodes of the operator node, and push the new conglomerate back on the stack.
3. Evaluate or simplify the expression tree via math.
Step 1 can be tricky, but there are several well-known algorithms for converting infix to postfix. Step 3 is the hardest, especially when performing such tasks as expression simplification and integration. MathematicaIntegrate function works by doing some weird transformations and guessing at the form of the solution, differentiating that, and then solving for the constants in a non-intuitive way. Many times the results can not be expressed in terms of simple mathematical functions - they can only be expressed in terms of other functions, often named after the Mathameticians who discovered them, that are in fact defined as integrals or solutions to differential equations. Some intregrals can''t even be expressed like that, such as the integral of x^x.
Bison was already mentioned, and I really think a tool like that would be the best thing for the job. Alternatively, look into something like the boost::spirit parser (though TBH I don''t really like boost::spirit).
"Sneftel is correct, if rather vulgar." --Flarelocke
"Sneftel is correct, if rather vulgar." --Flarelocke
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement