Parsing basic math equations for children's educational software?

Answer 1

You might look at the Shunting Yard Algorithm. The linked wikipedia page has a ton of info and links to various examples of the algorithm.

Basically, given an expression in infix mathematical notation, it give back an AST or Reverse Polish Notation, whatever your preference might be.

This page is pretty good. There are also a couple related questions on SO.

Answer 2

In a lot of modern languages there are methods to evaluate arithmetic string expressions. For example in Python

>>> a = '1+3*3'     
>>> eval(a)         
10

You could use exception handling to catch the invalid syntax.

Alternatively you can build arithmetic expression trees, there are some examples of these here in SO: Expression Trees for Dummies.

Answer 3

As pointed out above, I'd convert the normal string (infix notation) to a post fix expression.

Then, given the post-fix expression it is easy to parse through and evaluate the expression. For example, add the operands to a stack and when you find an operator, pop values off the stack and apply them operator to the operands. If your code to convert it to a post fix expression is correct, you shouldn't need to worry about the order of operations or anything like that.

The majority of the work in this case would probably be done in the conversion. you could store the converted form in a list or array for easy access so you don't really need to parse each value again too.

Answer 4

You say that several operators in a row are not valid. But think about:

5 + -2

Which is perfectly valid.

The most basic expression grammar is like:

Expression = Term | Expression, AddOp, Term
Term       = Factor | Term, MulOp, Factor
Factor     = Number | SignOp, Factor | '(', Expression, ')'

AddOp      = '+' | '-'
MulOp      = '*' | '/'
SignOp     = '+' | '-'

Number     = Digit | Number, Digit
Digit      = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

I once wrote a simple lightweight expression parser/evaluator (string in number out) which could handle variables and functions. The code is in Delphi but It shouldn't be that hard to translate. If you are interested I can put the sourcecode online.

Answer 5

Another note is that there are many parsing libraries available that a person can use to accomplish this task. It is not trivial to write a good expression parser from scratch, so I would recommend checking out a library.

I work for Singular Systems which specializes in mathematics components. We offer two math parsers Jep Java and Jep.Net which might help you in solving your problem. Good luck!

Answer 6

For this audience you'd want to give error feedback quite different than to programmers used to messages like "Syntax error: unexpected '/' at position foo." I tried to make something better for education applets here:

http://github.com/darius/expr

The main ideas: go to unusual lengths to find a minimal edit restoring parsability (practical since input expressions aren't pages long), and generate a longer plain-English explanation of what the parser is stuck on.