Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #78505 > unrolled thread

how to parse standard algebraic notation

Back to article view | Back to comp.lang.python

Contents

  how to parse standard algebraic notation math math <mathematisch@gmail.com> - 2014-09-30 13:53 -0700
    Re: how to parse standard algebraic notation Gary Herron <gherron@digipen.edu> - 2014-09-30 14:05 -0700
      Re: how to parse standard algebraic notation math math <mathematisch@gmail.com> - 2014-10-01 00:01 -0700
        Re: how to parse standard algebraic notation Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-10-01 08:35 +0100
        Re: how to parse standard algebraic notation Chris Angelico <rosuav@gmail.com> - 2014-10-01 18:38 +1000
          Re: how to parse standard algebraic notation math math <mathematisch@gmail.com> - 2014-10-01 05:04 -0700
        Re: how to parse standard algebraic notation Marco Buttu <marco.buttu@gmail.com> - 2014-10-01 14:22 +0200
        Re: how to parse standard algebraic notation Marco Buttu <marco.buttu@gmail.com> - 2014-10-01 14:26 +0200
    Re: how to parse standard algebraic notation Chris Angelico <rosuav@gmail.com> - 2014-10-01 10:20 +1000
    Re: how to parse standard algebraic notation wxjmfauth@gmail.com - 2014-10-01 01:08 -0700
    Re: how to parse standard algebraic notation Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-10-02 02:45 +1000
      Re: how to parse standard algebraic notation Chris Angelico <rosuav@gmail.com> - 2014-10-02 03:01 +1000

#78505 — how to parse standard algebraic notation

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.

Regards

[toc] | [next] | [standalone]

#78506

On 09/30/2014 01:53 PM, 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.
>
> Regards

This depends on things you have not yet told us.

In particular -- what "standard algebraic notation"?  For x-squared: 
x**2 ?  or perhaps  x^2 ?  or something else like some Unicode 
characters or HTML to get a small superscript 2 above an x.

Once you give an example of what your input looks like, we can start 
hashing out how to read it.

Gary Herron

-- 
Dr. Gary Herron
Department of Computer Science
DigiPen Institute of Technology
(425) 895-4418

[toc] | [prev] | [next] | [standalone]

#78522

On Tuesday, 30 September 2014 23:15:24 UTC+2, Gary Herron  wrote:
> On 09/30/2014 01:53 PM, 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.
> 
> >
> 
> > Regards
> 
> 
> 
> This depends on things you have not yet told us.
> 
> 
> 
> In particular -- what "standard algebraic notation"?  For x-squared: 
> 
> x**2 ?  or perhaps  x^2 ?  or something else like some Unicode 
> 
> characters or HTML to get a small superscript 2 above an x.
> 
> 
> 
> Once you give an example of what your input looks like, we can start 
> 
> hashing out how to read it.
> 
> 
> 
> Gary Herron
> 
> 
> 
> -- 
> 
> Dr. Gary Herron
> 
> Department of Computer Science
> 
> DigiPen Institute of Technology
> 
> (425) 895-4418

Thanks Gary (and Chris),

I should have sent a sample expression indeed.

What would be a good starting strategy for writing a program to take the derivative of a polynomial expression, such as this below?:
"x**3 + x**2 + x + 1"

I am a bit confused about my overall strategy. Should one be writing a parser class to split the input on operators and then on the double asterisks? Are there more clever ways? Or is this something one should solve using mathematical formulas instead of parsing the characters?

I just wonder how a seasoned Pythonian would go about a problem like this without using a ready-made derivative function from some module.

Regards,
Felix

[toc] | [prev] | [next] | [standalone]

#78524

On 01/10/2014 08:01, math math wrote:

[mega-snip]

You are far more likely to get answers if you access this list via 
https://mail.python.org/mailman/listinfo/python-list or read and action 
this https://wiki.python.org/moin/GoogleGroupsPython to prevent us 
seeing double line spacing and single line paragraphs, thanks.

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

[toc] | [prev] | [next] | [standalone]

#78528

On Wed, Oct 1, 2014 at 5:01 PM, math math <mathematisch@gmail.com> wrote:
> What would be a good starting strategy for writing a program to take the derivative of a polynomial expression, such as this below?:
> "x**3 + x**2 + x + 1"
>
> I am a bit confused about my overall strategy. Should one be writing a parser class to split the input on operators and then on the double asterisks? Are there more clever ways? Or is this something one should solve using mathematical formulas instead of parsing the characters?
>
> I just wonder how a seasoned Pythonian would go about a problem like this without using a ready-made derivative function from some module.

Well, let's see. Are you planning to use exact Python syntax
everywhere? For instance, will you use asterisks for multiplication
("5*x**3 + 2*x**2 - 5*x + 1")? If so, you could make use of the
ast.parse() module to do some of the work for you. Otherwise, you'll
have to start by writing up a grammar: exactly what is and isn't
allowed? Then write a parser, and see how things go from there.

ChrisA

[toc] | [prev] | [next] | [standalone]

#78542

Thanks a lot, I will give this a shot.

[toc] | [prev] | [next] | [standalone]

#78544

On 01/10/2014 09:01, math math wrote:
> What would be a good starting strategy for writing a program to take the derivative of a polynomial expression, such as this below?:
> "x**3 + x**2 + x + 1"

You can look at sympy:

 >>> from sympy import *
 >>> equation = simplify("x**3 + x**2 + x + 1")
 >>> equation
x**3 + x**2 + x + 1
 >>> diff(equation)
3*x**2 + 2*x + 1

-- 
Marco Buttu

INAF-Osservatorio Astronomico di Cagliari
Via della Scienza n. 5, 09047 Selargius (CA)
Phone: 070 711 80 217
Email: mbuttu@oa-cagliari.inaf.it

[toc] | [prev] | [next] | [standalone]

#78545

On 01/10/2014 09:01, math math wrote:

> What would be a good starting strategy for writing a program to take the derivative of a polynomial expression, such as this below?:
> "x**3 + x**2 + x + 1"

You can look at sympy:

 >>> from sympy import *
 >>> equation = simplify("x**3 + x**2 + x + 1")
 >>> equation
x**3 + x**2 + x + 1
 >>> diff(equation)
3*x**2 + 2*x + 1

-- 
Marco Buttu

[toc] | [prev] | [next] | [standalone]

#78518

On Wed, Oct 1, 2014 at 6:53 AM, math math <mathematisch@gmail.com> wrote:
> 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)

As Gary says, the form of input is really the critical part. How will
users type these?

One simple cheat you could do would be to prompt for each term
separately - something like this:

exponent = int(input("What is the highest exponent used? "))
terms = []
while exponent:
    terms.append(input("Enter coefficient of x^%d: " % exponent))
    exponent -= 1
terms.append(input("Enter constant term: "))

You could do something similar with a GUI toolkit like tkinter or
pygtk, too; provide input fields for the coefficients, and labels in
between that say "x² + " etc.

Otherwise, you're going to be primarily bound by the keyboard - your
program is useless if it takes longer to key data into it than to do
the work manually. Python 3.3 has excellent Unicode support, and
Unicode has excellent support for mathematical notations, so you
should be able to produce nice-looking output; but mathematical
notation is much easier to write on a blackboard than on a computer's
keyboard. (And even though some keyboards are black, like the one I'm
using right now, it doesn't make it any easier. Sorry.) Gary's
suggestions of the double asterisk and caret are two commonly-used
notations for exponentiation in computers, so either would make some
sense. Otherwise, you could come up with some other notation, but
mainly, it has to be typeable.

But hey! Once you have something you can type unambiguously, we can
help you parse that into something you can make use of! That part's
not too hard.

ChrisA

[toc] | [prev] | [next] | [standalone]

#78525

Le mardi 30 septembre 2014 22:53:22 UTC+2, math math a écrit :
> 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.
> 
> 

I would
- stick with a single algebric notation
- stick with a "variable"
- toy with string manipulations

Suggestion:
- split your polynomial in monomials
- extract the coefficients
- recompose the derivative

Eg, Transform
f(x) = azx**3 + 3x**2 +2y -x(3-2)
into
f'(x) = 3azx**2 + 6x - (3-2)

trap: 3*2 -> 6!

Simpler way
f(x) = a*z*x**3 + 3*x**2 +2*y -x*(3-2)
into
f'(x) = 3*a*z*x**2 + 3*2*x - (3-2)

jmf

[toc] | [prev] | [next] | [standalone]

#78557

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

[toc] | [prev] | [next] | [standalone]

#78558

On Thu, Oct 2, 2014 at 2:45 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> 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.

Building expression evaluators is good fun! And then you can add
specialty terms, like dice rolling.

> roll 2d6 + d6 "Electric" + 12 "Strength"
[ROLL] Rosuav rolls 2d6: 3, 6, totalling 9.
[ROLL] Rosuav rolls d6: 1 ("Electric")
[ROLL] Rosuav adds a bonus of 12 ("Strength")
[ROLL] For 2d6 + d6 "Electric" + 12 "Strength", Rosuav totals: 22

The code behind that follows a fairly similar pattern to what you
describe, only it deals with dice rolls (NdM -> roll N dice with M
sides each) instead of powers of x. (And it allows comments/tags.)

ChrisA

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web