parsing - Mathematical expression (string) to number in Java

Question

I'm trying to find something like Java Embedding Plugin (JEP) that can evaluate a mathematical formula (string) and give back the answer.

But it should also calculate a variable, for example: (25+36+x)*2 = 25 should give: x = -11

A little like http://www.wolframalpha.com/, but it shouldn't be that versatile, and it should work off-line.

Open source is preferred.

I need it for my little calculator project, http://sourceforge.net/projects/calex/.

Answer 1

This is called Arithmetic evaluation. One of the easiest way to implement this is using Edsger Dijkstra Shunting-yard_algorithm.

The shunting-yard algorithm is a method for parsing mathematical equations specified in infix notation. It can be used to produce output in Reverse Polish notation (RPN) or as an abstract syntax tree (AST). The algorithm was invented by Edsger Dijkstra and named the "shunting yard" algorithm because its operation resembles that of a railroad shunting yard. Like the evaluation of RPN, the shunting yard algorithm is stack-based. Infix expressions are the form of mathematical notation most people are used to, for instance 3+4 or 3+4*(2?1). For the conversion there are two text variables (strings), the input and the output. There is also a stack that holds operators not yet added to the output queue. To convert, the program reads each symbol in order and does something based on that symbol.

But I have seen exact solution what you are looking for on some stackoverflow user blog, but I can't remember the address (it was like 'code monkeyism'). It was lightweight class, that you could use in applets (you could also define constants and reset values).

Edit: Found it: http://tech.dolhub.com/Code/MathEval

A Linear-Recursive Math Evaluator

This math expression evaluator was born out of a need to have a small-footprint and efficient solution which could evaluate arbitrary expressions reasonably efficiently without requiring pre-compilation. I needed something which would do basic math with variables, expressions like: "Top+2", "Bottom-2" and "(Right+1-Left)/2".

Research on the Internet turned up a number of fairly good solutions, all of which revolved around creating parse trees (which makes sense). The problem was - they were all rather bulky, and I couldn't afford to add 100K to my applet size just for math. So I started wondering about a linear recursive solution to the problem. The end result is an acceptably performing single class with no external dependencies, weighing in under 10 KiB.