ansaurus

Question

Answer 1

+2 A:

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 2009-10-09 18:39:03

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

Noldorin 2009-10-09 18:41:27

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

Thomas Owens 2009-10-09 18:42:52

@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 2009-10-09 19:10:30

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.

Steve314 2009-10-09 19:29:55

@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 2009-10-09 19:29:55

@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.

Steve314 2009-10-09 19:40:06

@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 2009-10-09 19:43:39

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, ...

Steve314 2009-10-09 20:00:46

Answer 2

A:

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 2009-10-09 18:45:36

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 2009-10-09 18:47:34

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 2009-10-09 18:49:29

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 2009-10-09 18:51:14

@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 2009-10-09 18:53:33

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 2009-10-09 18:55:29

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

Lennart Regebro 2009-10-09 19:03:26

@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 2009-10-09 19:18:42

Answer 3

+9 A:

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 2009-10-09 18:59:59

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

Thomas Owens 2009-10-09 19:03:27

Answer 4

+1 A:

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 2009-10-09 20:08:43

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.

Paul McGuire 2009-10-09 23:24:10

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.

Paul McGuire 2009-10-11 14:44:45

Answer 5

A:

take a look at calculation engine

Tony Q 2010-10-21 01:39:10

Answer 6

A:

The java alternative is here http://code.google.com/p/expressionoasis/

Kaouni 2010-10-29 18:45:30

ansaurus

tags:

views:

answers:

Math Expression Evaluation

related questions