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

Question

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 !

Answer 1

You should familiarize yourself with postfix and prefix notation, the basic algorithms for converting between these (in both directions) and infix notation, and finally the Shunting Yard Algorithm.

These will answer your algorithm questions. SYA is even amenable to function tokens and nested functions.

You will want to spend some time learning the precedence and left/right-associativity of the various operators.

Answer 2

Although your algebraic language is quite limited, this is not a trivial endeavor.

You could certainly go about and write your own parser as suggested by other answers. Or you could use a parser generator to have your parser generated from grammar rules.

Here is one possible solution sketch:

You first need to define a grammar for your algebraic language. On Wikipedia there is a formal grammar for a similar language.

The language you are trying to evaluate seems to be context free.

There are different kinds of rules for specifying formal grammars. One is called EBNF (Extended Backus Naur Form).

Grammars for context free languages are usually defined as production rules containing terminal symbols and non-terminal symbols with the left hand side of the rules containing exactly one non-terminal symbol.

Terminal symbols in your case are digits (0 to 9), parenthesis, and operators +-/*^.

For your language I guess a sinlge non-terminal symbol S would be sufficient.

Your rules might look as follows:

S        -> ( <S> + <S> );
S        -> ( <S> - <S> );
S        -> ( <S> / <S> );
... 
S        -> 0|1|2|3|4|5|6|7|8|9;

This is a nice tool to try out your context free rules:

Once you have specified your grammar, you can use a parser generator (e.g. ANTLR) to generate a parser that will transform your input string into an parse tree, if the input string conforms to your query, and throws an exception otherwise.

Wikipedia provides a list of parser generators for different kinds of languages. You should be looking at the section for context free languages.

Then you will need to evaluate the abstract syntax tree using structural recursion.

Answer 3

One thing you might want to consider is a bottom-up parser. You can use it by filtering based on order-of-operations, using regular expressions inside of a recursive parse method. First, you take what's inside your parentheses and pass them down to parse. Then, you take your powers and pass those into parse. Then you take your multiplications and divisions and pass them into parse, from left to right. Finally, you take your additions and subtractions and pass them into parse, again from left to right. At the bottom level, (i.e. *, /, -, +, ^) you evaluate your expressions before passing them back. A wikipedia article on the subject can be found here.

Answer 4

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.