How to parse polynomials from a string equation

Question

I am wondering, given the string n*3/7+9-5, I could get the Polynomial from that, as an array or a string, such as [4, 3/7]. How should I go about doing this?

Also, There is a library allows me to turn it into a string like so: subtract(add(divide(multiply(n,3),7),9),5), if that helps.

Also, I am using Javascript And Objective - C (Server And Client), if that helps at all.

I have tried representing each operation as an object, and storing them in an array, then sorting the array by the order of operations, and evaluating each operation, and using that, but I got really lost, and could not figure out how to make it work.

Let me know if your need any more info.

My question is, what a good algorithm for converting n*3/7+9-5 to it's polynomials([4, 3/7])?

Thanks, Ari

Answer 1

There are two steps: parsing and differentiation/simplification.

There are multiple ways to do the parsing. You could use something existing, or what I do is a simple recursive-descent parser. Either way, the result is a parse tree data structure.

To differentiate/simplify, one can write fairly simple recursive functions.

(If all you need is the answer, I'm a big fan of Maxima.)

Otherwise you can write these kind of things:

Simplifier: This takes as input a parse tree and generates a new one by applying rules like this:
- anything times 0 is zero
- anything times 1 is that thing
- anything plus 0 is that thing
- any numeric value plus/minus any other is just a new numeric value
- any numeric value times/divided by any other is just a new numeric value

Substitution: This takes a parse tree A, a token name like "n", and another tree B, walks tree A, and wherever "n" appears, replace it by a copy of B. The result is a copy of A all "n"s replaced by copies of B.

So, for example, to get the constant part of the expression, you could just replace "n" by zero and simplify the result. All the terms with "n" in them will drop out, leaving the constant.

To differentiate by "n", you can use the basic rules:
- d(n) = 1
- d(anything not containing n) = 0
- d(a +/- b) = d(a) +/- d(b)
- d(a * b) = bd(a) + ad(b)
- d(a / b) = (bd(a) - ad(b))/(b^2)

So the overall strategy, say for terms up to n^2, could be:
- replace n^2 by x, differentiate by x, and the resulting constant q is the factor of n^2.
- to the original expression, subtract qn^2, and simplify it. That's the new expression minus the n^2 term.
- now differentiate that by n, and the resulting constant p is its factor.
- subtract pn and simplify, to produce the final additive constant r.

You can see if it's right by writing an simple calculator to interpret parse trees. Just plug a weird value for n into the original formula and see what you get. You should get the same thing if you interpret (qn^2 + pn + r).

Scared? It's easier than it looks and is a great skill to have.

EDIT: Here's Maxima:

HISTORY: Maxima descends from Macsyma (MAC Symbolic Manipulation) started in the early 70s at the MIT AI Lab and based on MacLisp and starting from Joel Moses' symbolic integration program. It can do algebra, differential and integral calculus, matrix and tensor math, differential equations, blah, blah.