Math parser
Author
Does anyone know where I can get code to parse a mathmatical polynomial like this:
A*x^2 + B*y^2 + C*z^2 + D*x*y + E*y*z + F*x*z + G*x + H*y + I*z + J = 0
where:
x = x0 + dx*t
y = y0 + dx*t
z = z0 + dx*t
and give me an answer in the form of:
C2*t^2 + C1*t + C0 = 0
Off course how I would enter the data doesn''t matter, I just want it to somehow give me C2, C1, C0 with given values for everything else.
LinaInverse2010
What do you want to do exactly?
Do you want to parse the string "A*x^2 + ... + J = 0"?
The string "A*x^2 + ... + J = 0 where: x = x0 + dx*t y = y0 + dx*t z = z0 + dx*t"?
Or do you just need a function like GetC012FromABCDEFGHIJ(someA,SomeB,...,SomeJ)
That last one shouldn''t be to hard, assuming the equation is static (i.e. only has an x, y and z):
A*x^2 + B*y^2 + C*z^2 + D*x*y + E*y*z + F*x*z + G*x + H*y + I*z + J = 0
=A*x0*dx*x0*dx * t^2
+B*y0*dy*y0*yx * t^2
+C*z0*dz*z0*zx * t^2
+D*x0*dx*y0*yx * t^2
+E*y0*dy*z0*zx * t^2
+F*x0*dx*z0*zx * t^2
+G*x0*dx * t
+H*y0*dy * t
+U*z0*dz * t
+J
=C2*t^2 + C1*t + C0,
C2 = A*x0*dx*x0*dx + B*y0*dy*y0*yx + C*z0*dz*z0*zx + D*x0*dx*y0*yx + E*y0*dy*z0*zx + F*x0*dx*z0*zx
C1 = G*x0*dx + H*y0*dy + U*z0*dz
C0 = J
Do you want to parse the string "A*x^2 + ... + J = 0"?
The string "A*x^2 + ... + J = 0 where: x = x0 + dx*t y = y0 + dx*t z = z0 + dx*t"?
Or do you just need a function like GetC012FromABCDEFGHIJ(someA,SomeB,...,SomeJ)
That last one shouldn''t be to hard, assuming the equation is static (i.e. only has an x, y and z):
A*x^2 + B*y^2 + C*z^2 + D*x*y + E*y*z + F*x*z + G*x + H*y + I*z + J = 0
=A*x0*dx*x0*dx * t^2
+B*y0*dy*y0*yx * t^2
+C*z0*dz*z0*zx * t^2
+D*x0*dx*y0*yx * t^2
+E*y0*dy*z0*zx * t^2
+F*x0*dx*z0*zx * t^2
+G*x0*dx * t
+H*y0*dy * t
+U*z0*dz * t
+J
=C2*t^2 + C1*t + C0,
C2 = A*x0*dx*x0*dx + B*y0*dy*y0*yx + C*z0*dz*z0*zx + D*x0*dx*y0*yx + E*y0*dy*z0*zx + F*x0*dx*z0*zx
C1 = G*x0*dx + H*y0*dy + U*z0*dz
C0 = J
Author
I want it to be able to parse an n-degree polynomial. The 2-nd degree I gave was just an example.
I''m going to use the coefficients given back to find the roots of the n-degree polynomial. This is for intersecting a ray with an nth degree polynomial. How I enter the polynomial is irrelevant to me.
LinaInverse2010
I''m going to use the coefficients given back to find the roots of the n-degree polynomial. This is for intersecting a ray with an nth degree polynomial. How I enter the polynomial is irrelevant to me.
LinaInverse2010
A single variable polynomial of degree n can be represented by a single vector of size n. The vector {p0, p1, p2, ..., pn} could then represent the polynomial P(x) = p0 + p1*x + p2*x^2 + ... pn*x^n. Multiplying a polynomial P(x) with a constant c would give c * P(x) = {c*p0, c*p1, c*p2, ...}, adding two polynomials P(x) + Q(x) = {p0+q0, p1+q1, p2+q2, ...}, and multiplying two polynomials R(x) = P(x) * Q(x) would look something like this:
Now all you have to do is to read the original polynomial one term at a time, substituting each x, y and z with the polynomials {x0, dx}, {y0, dy}, {z0, dz} respectively, and multiply them together with the coefficient. To make parsing simple, each term could be represented by four numbers, the coefficient and the multiplicities of x, y, and z. Thus, the string "5 4 3 2" would mean 5*x^4*y^3*z^2.
R = {0, 0, 0, ..., 0} (degree R = degree P + degree Q)for j = 0 to degree P for k = 0 to degree Q R[j+k] += P[j] * Q[k] Now all you have to do is to read the original polynomial one term at a time, substituting each x, y and z with the polynomials {x0, dx}, {y0, dy}, {z0, dz} respectively, and multiply them together with the coefficient. To make parsing simple, each term could be represented by four numbers, the coefficient and the multiplicities of x, y, and z. Thus, the string "5 4 3 2" would mean 5*x^4*y^3*z^2.
Should be: "A single variable polynomial of degree n can be represented by a single vector of size n+1."
There is a symbolic math package for python so you could embed python and use that package.
Otherwise you are going to have to use an expression tree. I could get long winded explaining it, but I''ll try to keep this short. An expression tree is a tree of operators. The children of an operator is it''s operands and may be expressions themselves. There are no parentheses because precedence is implied by the position in the tree, i.e. the children are evaluated by the root.
Here you have a simple tree. f*g*h where f=A+B*x+C*x^2 using a second degree of three variables as an example. x in turn is also an expression. The expression at each stage is simple to parse and build although it doesn''t sound like you actually need to parse. You could use the vector suggestion with a simple loop to build the expression tree. So you build each expression tree with empty variable pools.
You then build from the bottom up. t is undefined so there is no reason to do substitution on the x, y and z expressions. You just place x in the variable pool to build f, y for g and z for h. The result of evaluation of those expressions with those variables goes into the variable pool for the top expression, i.e. f*g*h. When you evaluate that expression with those in the variable pool you get an expression tree representing what you would get if you did the substitutions by hand. Not simplified by any means.
First you have to expand it out and then you collect terms. Expansion is simple. You replace a product of sums with a sum of products. Sounds simple and is simple. Somewhere in your tree you have a product where at least one of the children is a sum. All you deal with at any single instance is (A+B)*(C+D). You simply covert that to A*C+A*D+B*C+B*D. A, B, C and D may well be expressions, but you just proceed down the tree after performing the substituion. If they are expressions of the correct form they will be substituted in turn.
Now you rotate your variable right. So say you had (A+B*t)*(C+D*t) which became A*C + A*D*t + B*t*C + B*t*D*t so you make it A*C + A*D*t + B*C*t + B*D*t*t. Now A*C, A*D, B*C and B*D are all constants so replace those expressions with their values. t*t=t^2 so you make that substitution as well. All you have at this point is a sum of products of some constant and some power of t. So you rotate again by the power of t. Now way down at the bottom right most position you have A*t^B+C*t^D. If B=D then that can be replaced by (A+C)*t^B. Replace A+C by its value, back out one level and do it all again. Eventually B!=D. So now you are checking the left subtree of the right subtree against the left subtree. You end up with basically a linked list. The left side of the tree is some coefficent and power of t and the right hand side is the higher order terms. You can convert that into a vector where the position in the vector is the power and the value at that position is the coefficent.
You could also just evaluate that expression tree with some value of t in the variable pool. I assume you actually need the coefficents for some reason other than to evaluate the polynomial. If all you need is to evaluate the polynomial then skip the entire simplification. If you stick f, g, h, x, y, z and t into the variable pool you can just evaluate f*g*h. For that matter you can just make the coefficents variables and life gets a whole lot easier.
Overall stick the expression tree in a tree view as you are doing it. It is complex only in everything that is going on and not in any individual thing you are doing. When you can see what is going on there is less to track in your head.
Otherwise you are going to have to use an expression tree. I could get long winded explaining it, but I''ll try to keep this short. An expression tree is a tree of operators. The children of an operator is it''s operands and may be expressions themselves. There are no parentheses because precedence is implied by the position in the tree, i.e. the children are evaluated by the root.
Here you have a simple tree. f*g*h where f=A+B*x+C*x^2 using a second degree of three variables as an example. x in turn is also an expression. The expression at each stage is simple to parse and build although it doesn''t sound like you actually need to parse. You could use the vector suggestion with a simple loop to build the expression tree. So you build each expression tree with empty variable pools.
You then build from the bottom up. t is undefined so there is no reason to do substitution on the x, y and z expressions. You just place x in the variable pool to build f, y for g and z for h. The result of evaluation of those expressions with those variables goes into the variable pool for the top expression, i.e. f*g*h. When you evaluate that expression with those in the variable pool you get an expression tree representing what you would get if you did the substitutions by hand. Not simplified by any means.
First you have to expand it out and then you collect terms. Expansion is simple. You replace a product of sums with a sum of products. Sounds simple and is simple. Somewhere in your tree you have a product where at least one of the children is a sum. All you deal with at any single instance is (A+B)*(C+D). You simply covert that to A*C+A*D+B*C+B*D. A, B, C and D may well be expressions, but you just proceed down the tree after performing the substituion. If they are expressions of the correct form they will be substituted in turn.
Now you rotate your variable right. So say you had (A+B*t)*(C+D*t) which became A*C + A*D*t + B*t*C + B*t*D*t so you make it A*C + A*D*t + B*C*t + B*D*t*t. Now A*C, A*D, B*C and B*D are all constants so replace those expressions with their values. t*t=t^2 so you make that substitution as well. All you have at this point is a sum of products of some constant and some power of t. So you rotate again by the power of t. Now way down at the bottom right most position you have A*t^B+C*t^D. If B=D then that can be replaced by (A+C)*t^B. Replace A+C by its value, back out one level and do it all again. Eventually B!=D. So now you are checking the left subtree of the right subtree against the left subtree. You end up with basically a linked list. The left side of the tree is some coefficent and power of t and the right hand side is the higher order terms. You can convert that into a vector where the position in the vector is the power and the value at that position is the coefficent.
You could also just evaluate that expression tree with some value of t in the variable pool. I assume you actually need the coefficents for some reason other than to evaluate the polynomial. If all you need is to evaluate the polynomial then skip the entire simplification. If you stick f, g, h, x, y, z and t into the variable pool you can just evaluate f*g*h. For that matter you can just make the coefficents variables and life gets a whole lot easier.
Overall stick the expression tree in a tree view as you are doing it. It is complex only in everything that is going on and not in any individual thing you are doing. When you can see what is going on there is less to track in your head.
I bit the bullet a little while ago and learned enough about Flex and Bison to get by.
They are well worth the effort
They are well worth the effort
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
