9

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.

smci
  • 32,567
  • 20
  • 113
  • 146
Ori Shavit
  • 255
  • 2
  • 5
  • 8
  • 1
    http://docs.python.org/reference/simple_stmts.html#exec – nlucaroni Oct 09 '09 at 18:38
  • 1
    Have a look at: http://stackoverflow.com/questions/400050/reading-and-running-a-mathematical-expression-in-python – Bart Kiers Oct 09 '09 at 18:44
  • 1
    Try "evaluate" instead of "solve" which suggests being able to find "x" given "4x - 6 = 4". – dmckee --- ex-moderator kitten Oct 09 '09 at 18:50
  • 3
    "I want to configure other operators". Sigh. Couldn't you have said that from the beginning? – Lennart Regebro Oct 09 '09 at 19:05
  • 3
    Compiler resources: http://stackoverflow.com/questions/1669/learning-to-write-a-compiler and some very short implementations: http://stackoverflow.com/questions/1384811/code-golf-mathematical-expression-evaluator-full-pemdas and http://stackoverflow.com/questions/1538964/code-golf-reverse-polish-notation-postfix-evaluator and http://stackoverflow.com/questions/928563/code-golf-evaluating-mathematical-expressions – dmckee --- ex-moderator kitten Oct 09 '09 at 19:34

5 Answers5

16

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!

Martin B
  • 23,670
  • 6
  • 53
  • 72
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.

Kathy Van Stone
  • 25,531
  • 3
  • 32
  • 40
  • 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. – PaulMcG Oct 09 '09 at 23:24
  • 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. – PaulMcG Oct 11 '09 at 14:44
1

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.

Thomas Owens
  • 114,398
  • 98
  • 311
  • 431
  • 18
    So their calling parsing a "pattern" now too? This must be the most overused word in computer science... – Noldorin Oct 09 '09 at 18:41
  • It's not just parsing. It's parsing "sentences" in a given "language" in a clean, understandable way. – Thomas Owens Oct 09 '09 at 18:42
  • 1
    @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 – Noldorin Oct 09 '09 at 19:10
  • 2
    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. –  Oct 09 '09 at 19:29
  • 1
    @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. – geowa4 Oct 09 '09 at 19:29
  • @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. –  Oct 09 '09 at 19:40
  • @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. – Thomas Owens Oct 09 '09 at 19:43
  • 1
    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, ... –  Oct 09 '09 at 20:00
1

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.

Lennart Regebro
  • 167,292
  • 41
  • 224
  • 251
  • 2
    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. – Thomas Owens Oct 09 '09 at 18:47
  • 2
    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. – Lennart Regebro Oct 09 '09 at 18:49
  • 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. – Thomas Owens Oct 09 '09 at 18:51
  • 1
    @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. – D.Shawley Oct 09 '09 at 18:53
  • 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. – Thomas Owens Oct 09 '09 at 18:55
  • Heh, I didn't know about the `__import__` trick. However, you can get around that too. I updated the answer. – Lennart Regebro Oct 09 '09 at 19:03
  • 1
    @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? – Martin B Oct 09 '09 at 19:18
  • And how about eval("[2**(10**a) for a in range(100000)]", vars, {})? – MatthewWilkes Jan 31 '14 at 10:22
  • @MatthewWilkes Then you'll run out of memory. :) – Lennart Regebro Jan 31 '14 at 11:51
  • Not for quite a while. The point is, if you allow generator expressions or comprehensions you open yourself up for denial of service attacks. – MatthewWilkes Jan 31 '14 at 12:28
-1

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.

Philippe F
  • 11,776
  • 5
  • 29
  • 30