Parsing Implementation - Algebra Parsing Advice?

[Aarowaim]

Hello everyone,

I'm an amateur programmer, and I am working on a program to help me practice my mental math. The essence of this program is that the user inputs an expression which will be the form of each question. Their goal is to solve those expressions as fast as they can.

For example, let's say I input a quadratic formula of (ax^2 + bx + c). My program will then read each variable in the equation, and allow the user to specify minimum and maximum values for each variable, as well as the increments. From this, it will randomly generate values for each variable in these limits and provide questions such as "(6)5^2 + 5 + 3 = ?". Hopefully, this program will help bolster my mental math abilities, and in the future, I intend to add questions about graphing, discriminants, and transformations to it.

The reason that I am here is because I need a parser in order to extract the variables and ensure that the equation is valid. My area of expertise is not in parsing, so I would appreciate advice and input as to how to implement it.

Currently, my understanding is that I need two pieces; a lexer, and a parser. The lexer is the piece that reads character by character, converting the characters into tokens for the parser to use. The parser then reads through these tokens and ensures that they match a grammar by building a tree. As of now, the approach I am considering is something of a predictive algorithm; it simply reads the values, and then checks if the next value matches what is expected. I imagine that it would be something like if Term or (Term), then Operator or (Term) or End; if Operator, then Term or (Term). Thus, I solve the problem of validating the equation. Whenever term resolves into a number, it is ignored. When it resolves into a letter, then that letter is returned and the user is prompted for the boundaries of that variable. Finally, when the questions are generated, the randomly generated numbers are substituted into the equation, and then solved by the computer to check whether the user is correct in their calculations.

Is there anything wrong with my approach? If so, what would you recommend or suggest? Finally, if you know of any good java libraries which already do this, I am open to suggestions.

Thank you very much for reading this, and hopefully this isn't a silly question. I tried very hard to research and also tried my utmost to avoid asking any questions that haven't already been asked on this forum.

[ddanbe]

In my code snippets I have 3 parts, who together form a small expression console calculator. But it is in C# rather then Java. But as C# took many things from Java, translation is perhaps not that big of a problem.Click Here for the scanner(lexer). Hope it helps a bit.

[gusano79]

Definitely keep the lexer/parser concept; it makes things much easier to deal with.

You'll see lost of people online recommending that you write a recursive descent parser or use a parser generator, both of which are fine if you want to learn about them.

My preferred approach to parsing algebraic expressions is the shunting-yard algorithm. It's powerful enough to deal with any expression you want (including functions and operator precedence), and it's not hard to extend (new functions or operators, variable substitution) if you're smart about the implementation. But it's also not overwhelmingly general-purpose, so you can focus on the algebra.