Math Expression Evaluation

Question

What is the best way to implement a python program that will take a string and will output its result according to operator precedence (for example: "4+3*5" will output 19). I've googled for ways to solve this problem but they were all too complex, and I'm looking for a (relatively) simple one.

clarification: I need something slightly more advanced than eval() - I want to be able to add other operators (for example a maximum operator - 4$2 = 4) or, also I am more interested in this academically than professionaly - I want to know how to do this.

Lavinalavine

docs.python.org/reference/simple_stmts.html#exec – Micronesian

Have a look at: #400550 – Musser

Try "evaluate" instead of "solve" which suggests being able to find "x" given "4x - 6 = 4". – Protero

"I want to configure other operators". Sigh. Couldn't you have said that from the beginning? – Schutt

Compiler resources: https://mcmap.net/q/63539/-learning-to-write-a-compiler-closed and some very short implementations: #1385311 and #1539464 and #929063 – Protero

Answer 1

If you're "academically interested", you want to learn about how to write a parser with operator precedence.

Simple Top-Down Parsing in Python is a nice article that builds an example parser to do exactly what you want to do: Evaluate mathematical expressions.

I can highly recommend having a go at writing your own first parser -- it's one of those "ah, that's how that works" moments!

Fourflusher

I took a very quick look, and it appears that the article you linked to implements the Interpreter pattern in Python. – Adumbral

The link returns a 404 error – Flori

Answer 2

Another possibility is to look at Pyparsing, which is a general parser builder. It is more powerful than you need, but it may be faster to implement.

Nordrheinwestfalen

The pyparsing wiki (pyparsing.wikispaces.com) includes a couple of examples of an arithmetic expression parser - fourFn.py and simpleArith.py. Even if you don't use pyparsing, fourFn.py is likely to be enlightening in how such a parser implements operator precedence. – Enchantress

I just realized that the OP wanted to add other operators. simpleArith.py shows how to add a factorial (!) operator - evalArith.py (at the bottom of the page) expands simpleArith.py and shows how to evaluate the parsed values. – Enchantress

Answer 3

I'm not terribly familiar with Python and any extremely Pythonic methods, but you could look at the Interpreter pattern, which is defined in the Gang of Four book. It's designed for processing a "language", and mathematical expressions do follow a particular language with rules. In fact, the example on Wikipedia is actually a Java implementation of a RPN calculator.

Adumbral

So their calling parsing a "pattern" now too? This must be the most overused word in computer science... – Merger

It's not just parsing. It's parsing "sentences" in a given "language" in a clean, understandable way. – Adumbral

@Thomas: That's not more specific than generic parsing, really. I mean, all parsing involves "sentences" of some sort; and any decent parser ia clean/understandable, at least in some form. (See recursive descent as an example.) Also, s/their/they're :P – Merger

Interpreter was an original GOF pattern. The example is the (very) high level design of a simple regex library. It suggests using an AST for the language description, essentially, rather than (maybe as well as) for the parsed input. Should work for recursive descent, but it doesn't cover how to do it. Really, I don't think it should be in the book - you only need one regex library and (maybe) one expression evaluator library, not a pattern. Beyond that its time for lex, yacc and friends. – Palaeography

@Noldorin: "So their calling parsing a "pattern" now too?" I like how you say that, as if the GoF book was released in the past couple months. The Interpreter pattern is a bit more than parsing. It defines a proven method of reading in data and structuring it in a usable way. I have seen other attempts at parsing that resulted in a garbled mess. – Repertory

@Thomas - RPN isn't very impressive. The only real parsing is the regular grammar for the tokens - and the original GOF example was a regex handler. For a sufficiently simple token representation, you don't need a grammar at all for RPN - you only need a stack. That's the whole point of RPN. – Palaeography

@Steve314 I didn't recall what the example in the GoF book. I don't have it next to me at work. However, you are correct - RPN doesn't demonstrate the true power of the Interpreter pattern. – Adumbral

Hmmm - I may need to retract that "shouldn't be a pattern claim". I keep thinking of other examples. XML parsers, nested-block binary file handlers, declarative event-stream handlers - e.g. game entity AIs and complex configurable GUI controls, ... – Palaeography

Answer 4

That's what the "eval" function does in Python.

result = eval(expression)

Beware though it can do a whole lot more, primarily call functions, so to be safe you should make sure it can't access the locals or globals. Also, you can access the builtin methods, including the tricky import so you need to block access to that as well:

result = eval(expression, {'__builtins__': None}, {})

But that's only if you need security, that is if you allow anybody to type in any expression.

Of course since you this way block all locla variables from use, then you don't have any variables to use, so to have that you need to pass in just those variables which should be accessed in the dictionaries.

vars = {'__builtins__': None, 'x': x}
result = eval(expression, vars, {})

or similar.

Schutt

The problem with eval comes when expression = "system.os(rm -rf )". If you run it as root in *nix, boom goes the machine. Or if it's the Windows equivalent, especially since there are far too many people running Windows as Administrator. – Adumbral

Only if you have done from os import system and doesn't provide the globals and locals directory. Which I do in my examples for this reason. – Schutt

Inside expression, you can once again import system from os and then use it. So yes, my example would only work if you already import os from system, but by expanding my expression, you can import anything you want and use it. – Adumbral

@Thomas: if you are running as root in a Linux environment or Administrator in Windows land, then you deserve the justice that this results in. – Pyrethrum

D.Shawley: That's true, but you can never know what your end users are doing. For example, right now, at work, I'm running as Administrator in Windows. No restrictions. – Adumbral

Heh, I didn't know about the __import__ trick. However, you can get around that too. I updated the answer. – Schutt

@D.Shawley: So what about the poor user who isn't running as root and only loses all of his own files -- does he/she deserve what this results in? – Fourflusher

And how about eval("[2**(10**a) for a in range(100000)]", vars, {})? – Apoplectic

@MatthewWilkes Then you'll run out of memory. :) – Schutt

Not for quite a while. The point is, if you allow generator expressions or comprehensions you open yourself up for denial of service attacks. – Apoplectic

Answer 5

This receipe gives the proper answer to your problem:

http://code.activestate.com/recipes/496746-restricted-safe-eval/

It allows you to eval limited statement that can not harm your computer or your program.

Kneepad