[CentralOH] Python Parsing Puzzle

[Eric Floehr]

These are all great solutions! Quite a few different implementations, and
I'm glad everyone had fun with it. Just for closure, I realized I never
shared the solution that I created prior to posting the puzzle.

My solution was closest to XY's in that I used Python abstract syntax tree
parsing library (ast). This is the same code that parses Python code, and I
took advantage of the fact that the formulas were valid Python code (with a
little sanitizing, like XY did).

I ended up making a generator, that parsed the formula and returned pairs
of variable name and the coefficient, like so:


def coefficients(op):
    # Parse the string formula and turn into AST
    if isinstance(op, str):
        for coefficent in coefficients(ast.parse(op).body[0].value):
            yield coefficent
    # If there is only a number, it's the constant
    elif isinstance(op, ast.Num):
        yield 'CONST', op.n
    # If the operator is multiplication, it's a variable, coefficient pair
    elif isinstance(op.op, ast.Mult):
        yield op.right.id, op.left.n
    else:
        # We want all pairs to be added, so negate the coefficient if
subtraction
        if isinstance(op.op, ast.Sub):
            negate(op.right) # Just a helper function
        # Split the tree and work on each half
        for coefficient in itertools.chain(coefficients(op.left),
coefficients(op.right)):
            yield coefficient


You can pass in the string formula line, and use it like this:


for name, coefficient in coefficients(formula_string):
    ... do something ...


Thanks again everyone!



On Sun, Dec 7, 2014 at 3:34 PM, Erik Welch <erik.n.welch at gmail.com> wrote:

> Thanks for posting the puzzle, Eric.  It's great to see the different
> approaches people are taking.
>
> Here's my solution using regular expressions and pandas (which I'm sure
> could be cleaned up and simplified):
>
> http://nbviewer.ipython.org/url/pastebin.com/raw.php/%3Fi%3DS7fRWFwS
>
> Cheers,
> Erik
>
> On Sat, Dec 6, 2014 at 11:37 PM, Thomas Winningham <winningham at gmail.com>
> wrote:
>
>> I was curious about ast as well. I played with it once one time. So it is
>> true that parsing then shouldn't evaluate the code? I'm trying to think if
>> there are there any other possible "gotchas" ? I guess I should just read
>> more. I always figured things like Hy and PyPy make extensive use of
>> concepts in this general area. I played once on time with parser generators
>> in Java until I found a different solution for whatever I was doing. I
>> guess had I ever taken a compiler class I may know better how to Google
>> these things, or even post about them, heh.
>> On Dec 6, 2014 8:58 PM, "iynaix" <iynaix at gmail.com> wrote:
>>
>>> My solution: http://pastebin.com/nbGprTtV
>>>
>>> Quick explanation:
>>>
>>> As the formulas are basically valid python, minus undefined identifiers,
>>> I sanitize the formulas a little, then feed the formulas into the python
>>> ast module (https://docs.python.org/2/library/ast.html).
>>>
>>> Some quick walking of the parse tree yields the needed numbers and
>>> coefficients, which is then placed into a dict. Parsing an ast does not
>>> trigger an eval, so it should be safe, if that is a concern. After that
>>> it's just python data structure manipulation, pretty straightforward.
>>>
>>> This was pretty fun! Always wanted to play with the python ast module,
>>> but never had a problem to apply it on.
>>>
>>> Cheers,
>>> Xianyi
>>>
>>> On Sun, Dec 7, 2014 at 4:34 AM, <jep200404 at columbus.rr.com> wrote:
>>>
>>>> On Sat, 6 Dec 2014 10:59:21 -0500, Eric Floehr <eric at intellovations.com>
>>>> wrote:
>>>>
>>>> > How would you solve this problem?
>>>>
>>>> Release early, release often: http://colug.net/python/dojo/20141206/
>>>>
>>>> I would normally use grep, awk, sed, awk, tr, and friends,
>>>> but here's some very sloppy Python code to start things.
>>>>
>>>> What program, ala indent or cb, do folks like for cleaning up
>>>> Python code?
>>>> _______________________________________________
>>>> CentralOH mailing list
>>>> CentralOH at python.org
>>>> https://mail.python.org/mailman/listinfo/centraloh
>>>>
>>>
>>>
>>> _______________________________________________
>>> CentralOH mailing list
>>> CentralOH at python.org
>>> https://mail.python.org/mailman/listinfo/centraloh
>>>
>>>
>> _______________________________________________
>> CentralOH mailing list
>> CentralOH at python.org
>> https://mail.python.org/mailman/listinfo/centraloh
>>
>>
>
> _______________________________________________
> CentralOH mailing list
> CentralOH at python.org
> https://mail.python.org/mailman/listinfo/centraloh
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/centraloh/attachments/20150204/cf2fd027/attachment.html>