Search code examples
pythonalgorithmmathcalculatorevaluation

Python: How can I evaluate algebraic expressions with a logic algorithm?


I am new to programming and started a little project to get better. I want to do a not so basic shell calulator, the basic methods were quickly done and I learned a lot. But my new goal is it to evaluate full algebraic expressions like:(2+3)^(80/(3*4)) I thought an algorithm would come in handy to do it 'step by step' as a human would - solving 1 bit of the whole thing and start over. So i wanted to check for all the interessting algebraic signs first: (term is the user input)

    open_brackets     =[i.start() for i in re.finditer('\(',str(term))]
    close_brackets    =[i.start() for i in re.finditer('\)',str(term))]
    powers            =[i.start() for i in re.finditer('\^',str(term))]
    mult              =[i.start() for i in re.finditer('\*',str(term))]
    div               =[i.start() for i in re.finditer('\/',str(term))]
    plus              =[i.start() for i in re.finditer('\+',str(term))]
    minus             =[i.start() for i in re.finditer('\-',str(term))]

Now that I have this information I thought it could be useful to look for the far most right open bracket and find the corresponding closed bracket:

last_open_bracket = open_brackets[len(open_brackets)-1]
    next_closed_bracket = 0
    for i in close_brackets : 
        if last_open_bracket < i :
            next_closed_bracket = i
            break

From there on I only run into problems as I dont know how to structure the whole thing and I messed up quite a few times already. It is obviously useful to look inside those brackets, and check for algebraic sign between them. An example for powers since they`re first would be :

for i in powers : 
        if (last_open_bracket < i) and (next_closed_bracket > i) :

I now could ,once I found the position of a "^" , go stepwise left of the "^" until I hit something which isn't of the type int or "." since this is used in floats, more specifically , I search for the next algebraic sign or bracket. And so on and so on until I have 2 numbers which I can then take the power of. Then slice out all the symbols and numbers which were used for this calculation in the original input and add the calculated result at the right place and start over again.

My problem is to handle all the different scenarios that could happen inside the brackets e.g.

  • multiple operations i.e (2+3+4)
  • recognize the "-" in (-9) or -(9) not as call to subtract something

But also how to handle different brackets in certain situations e.g. , I earlier proposed to slice off all the symbols and numbers used, but in different cases we need different means:

  1. (9) --> 9
  2. (2+3) --> 5
  3. (-2)^2 -/-> -2^2

As you can see I need a little thinking assistance, I dont know how to conceptualize this algorithm. I hope you can help me , and have a nice day !


Solution

  • I have seen a few parsers and written a couple of my own, but I have never seen an algorithm like the one you are trying. Your difficulties may imply that you should use another overall algorithm.

    I suggest you just scan through the expression string one character at a time, left to right, and act on each character appropriately. If you want simplicity, you could make a recursive algorithm, using PEMDAS and group of routines. Your top level evaluates an expression, the next a parentheses group, the next exponentiation, the next multiplication and division, and the last addition and subtraction. You also need a routine to evaluate the numeric literals, one for negation, and one for unary plus.

    There are also other approaches, such as using a token for each operator, putting things on a stack, and using a dictionary that gives the order of operation for each operator. Be careful here with exponentiation, since its order is right-to-left rather than left-to-right. But your needs seem rather simple, and the recursive approach would be simpler for you.