parsing math expression in python and solving to find an answer

Question

I am quite new to programming. This is in relation to python. So the idea is to take an expression such as 3/5 or, at most, 3/5*2(at most two operators, note that the operators can be any of +,-,/,*) and solve it. White space can exist anywhere within the expression.

The user enters the expression, say 3/5, and the program needs to solve the expression and display the answers. What I have tried is below. Note, I only have attempted the first part, once I can properly split the original expression that the user enters(which would be a string), creating functions would be the easy part:

expres= str(input("something:"))

ssplit= hit.partition("/")
onec= int((ssplit[0].lstrip()).rstrip())
twoc= (ssplit[1].lstrip()).rstrip()
threec= int((huns[2].lstrip()).rstrip())


print(onec,"...",twoc,"...",threec) #just a debug test print

So above, I can take an expression like 3/5 and split it into three separate strings:3 , /, and 5. I can also remove all whitespace before and after the operators/operands. I am having problems with splitting expressions like 4/5+6, Because I can't put code in for ssplit[3] or ssplit[4] and then enter an expression like 3/5, because it won't be defined. Basically I needed you help to find out how to split an expression like 3/4-6,etc. I also need help with the line "ssplit= hit.partition("/")" so that it will look at the entered expression and work with +,-, and * as well. Any and all help is appreciated. Also if my code above looks nasty and inefficient please give me criticism. Thanks!

Note I can't, and wouldn't want to use eval. Order of operations is required. I cant use complicated commands. I need to keep it simple, the most I can use is string libraries, converting between strings/integers/floats etc. and if,and,etc. statements. I can also use functions.

Whom

You shouldn't need str(input(...)). If you're on py3k, the output is already a string. If you're on py2k, then you should use raw_input. – Allege

How about eval(raw_input()) :P – Gareri

@JohnVinyard I would post that as an answer ... – Gaucho

Ha. Done. I just don't know sometimes... – Gareri

@user1716168 -- Do you need to worry about order of operations? For example, what do you expect to get out of 2+3*2 -- If you parse from left to right, you'll get 12, if you parse using order of operations, you'll get 8 ... – Allege

Yes I need to worry about order of operations. – Whom

@nneonneo -- ast.literal_eval doesn't handle any sort of operators -- e.g.: ast.literal_eval('1+3') fails. – Allege

As a side note on the eval discussion... even if you find a basic way to make it work for this application, you should never use eval() on a public facing web application. Doing so would open a security hole by allowing people to enter (non-mathematical) code expressions that would then be faithfully executed. – Lemaceon

@Lemaceon -- True. You can do some things to make it better though. You can pass global and local dictionaries to restrict what eval can do. Even with that there are some lesser known issues, but they can be worked around if you're careful and know what you're doing. That said, It's probably best to avoid if you're not certain that you know what you're doing. – Allege

Thanks for sharing this tip, @Allege ! Based on your comment, I found this article with more details (and examples) on quasi-securing eval(): lybniz2.sourceforge.net/safeeval.html . It might be of interest to the questioner. – Lemaceon

Given your restrictions you're clearly fishing for an answer to a homework problem. – Glidden

Answer 1

If I wasn't going to rely on external libraries, I'd do it something like this:

def parse(x):
    operators = set('+-*/')
    op_out = []    #This holds the operators that are found in the string (left to right)
    num_out = []   #this holds the non-operators that are found in the string (left to right)
    buff = []
    for c in x:  #examine 1 character at a time
        if c in operators:  
            #found an operator.  Everything we've accumulated in `buff` is 
            #a single "number". Join it together and put it in `num_out`.
            num_out.append(''.join(buff))
            buff = []
            op_out.append(c)
        else:
            #not an operator.  Just accumulate this character in buff.
            buff.append(c)
    num_out.append(''.join(buff))
    return num_out,op_out

print parse('3/2*15')

It's not the most elegant, but it gets you the pieces in a reasonable data structure (as far as I'm concerned anyway)

Now code to actually parse and evaluate the numbers -- This will do everything in floating point, but would be easy enough to change ...

import operator
def my_eval(nums,ops):

    nums = list(nums)
    ops = list(ops)
    operator_order = ('*/','+-')  #precedence from left to right.  operators at same index have same precendece.
                                  #map operators to functions.
    op_dict = {'*':operator.mul,
               '/':operator.div,
               '+':operator.add,
               '-':operator.sub}
    Value = None
    for op in operator_order:                   #Loop over precedence levels
        while any(o in ops for o in op):        #Operator with this precedence level exists
            idx,oo = next((i,o) for i,o in enumerate(ops) if o in op) #Next operator with this precedence         
            ops.pop(idx)                        #remove this operator from the operator list
            values = map(float,nums[idx:idx+2]) #here I just assume float for everything
            value = op_dict[oo](*values)
            nums[idx:idx+2] = [value]           #clear out those indices

    return nums[0]

print my_eval(*parse('3/2*15'))

Allege

Probably should add .strip() somewhere there to skip whitespace. Also, unfortunately, this does not respect order of operations, which OP wants. – Isatin

@Isatin -- That shouldn't really matter though. Both int and float (which would be used at the next stage) would accept whitespace around the numbers ... – Allege

can you add some documentation for your opout numout and buff commands I get lost trying to follow it once I get to the if statement. – Whom

@user1716168 -- if I helps, you could get do buff = '' instead of buff = [] and buff += c instead of buff.append(c) and then you could just put buff into num_out rather than ''.join(buff). (but using a list is likely to be more efficient) – Allege

@Allege It clears it up a lot but could u just add a bit more about buff, what it is, and how it changes through the function? – Whom

@user1716168 -- buff is a list. You add characters to it until you find an operator (thats the else clause). When you find an operator, you take that list and turn it into a string (via join) and append it to the numbers. Then you reset/empty buff. If it helps, print buff` at each step through the loop and see what it looks like. – Allege

awesome thanks, now i just need to get the order thing working, Ill see if a few if statements can fix that – Whom

@Isatin -- It respects the order of operations now :) – Allege

Well...arithmetically, * and / have the same precedence. a/b*c is not a/(b*c), but (a/b)*c... – Isatin

@Isatin -- On second thought, I'm just stubborn. You're right. updated again ... – Allege

unfortuantely I can't use "set" or .append. or .join or eval or list or operator. Basiaclly I am limited to using sting commands from the python string dictionary and functions. I also can't use the import command – Whom

Thanks ive been researching this to learn it completely for many many many many hours since this post and it really is useful. – Whom

@Allege - You shouldn't use the buff = '' buff += 'blah' pattern. The preference is always to append() to a list and join at the end. This is because strings are immutable in python, and you're allocating ram for each incremental string. – Glidden

@AaronMcMillin -- True. That's what I used in my answer. I only mentioned it in the comments to try to make it more clear what the code is doing. That said, unless this is in a tight loop, or the strings are really long, it probably won't make a noticeable difference in actual runtime. :-) – Allege

Answer 2

That's not really the way to parse an expression, you should look more into lexers and parsers, something like PLY or pyparsing. However, if you just want to evaluate the expression you could use eval(expr). Note that eval will execute any code you feed it, so it's not really safe.

Edit There's an example here for using pyparsing, that should get you started:

pyparsing example

Teratology

eval cant be used, I will look into ply, although if the code is too high level I wont be able to use it. – Whom

Then you should start with pyparsing, I think it's easier to begin with. – Teratology

I checked the example and it is far to complicated for my needs and therefore I cant use it. It would be better if i didnt use external libraries. – Whom

It would really help if you could provide an example of the actual data you're trying to process, with more information about the specific application. This might allow someone with relevant domain expertise to chime in with information and resources tailored to your exact problem. – Lemaceon

Pyparsing website is dead – Eduction

Answer 3

Use the shlex and StringIO Python module. In Python 2.3+:

>>> from StringIO import StringIO
>>> import shlex
>>> input = StringIO('3/4+5')
>>> list(shlex.shlex(input))
['3', '/', '4', '+', '5']

Heaney