how to parse standard algebraic notation

[Steven D'Aprano]

math math wrote:

> Hi,
> 
> I am trying to learn Python while solving exercises.
> 
> I want to basically write a program that inputs a polynomial in standard
> algebraic notation and outputs its derivative.
> 
> I know that I need to get the exponent somehow, but I am not sure how to
> accomplish this in python (3.3)
> 
> Do you have any ideas or suggestions? I don't want to use existing modules
> as this is meant to be a didactic experience.

Code for evaluating mathematical expressions are very common, if you google
for "expression parser" I am sure you will find many examples. Don't limit
yourself to Python code, you can learn from code written in other languages
too, e.g. I have a Pascal programming book that develops a parser for both
polynomials and arithmetic expression. The code is fairly long, but quite
straightforward to translate into Python (and Pascal code is quite
readable.)

Look at an standard infix expression, using ^ for powers:

4*x^3 + x^2 - 5*x + 1

There are four terms:

4*x^3 
x^2 
-5*x
1

So if you replace "-" with "+-" and then split on "+", you will get terms:

py> expr = "4*x^3 + x^2 - 5*x + 1"
py> terms = expr.replace("-", "+-").split("+")
py> terms
['4*x^3 ', ' x^2 ', '- 5*x ', ' 1']

Strip spaces from each term:

py> terms = [s.replace(' ', '') for s in terms]
py> terms
['4*x^3', 'x^2', '-5*x', '1']

Unfortunately, terms can include optional parts. The coefficient is
optional, and may be just a minus sign; the power is optional. To make
processing easier, we can do this:

term = term.replace('-x', '-1*x')
if term.startswith('x'):
    term = term.replace('x', '1*x')
if term.endswith('x'):
    term = term.replace('x', 'x^1')

to each term, which will give us something like:

['4*x^3', '1*x^2', '-5*x^1', '1']

If a term is all digits (with an optional leading minus sign) then it is the
constant term. Otherwise, it will be of the form:

[optional minus sign][one or more digits]*x^[one or more digits]

which can now be easily parsed by splitting it up around the *, x or ^
symbols. Or use a regular expression.



-- 
Steven