equation parsing

Started by
7 comments, last by meeshoo 19 years, 8 months ago
Hi, I would like to write a program that lets you write simple equations like 4+4*3 and solve it. Does anyone know what technique this is. Is it string parsing? :) I'm using c# Any tips would be great Thanks :)
Advertisement
It depends on how complicated the expression are, but for simple arithemetic expressions, use two stacks.

Here's an example. I'll leave it to you to figure out the algorithm.

1 + 2 * 3 - 4 / 5:

Read 1. Push it on the operand stack. Operands: 1 Operators: empty
Read +. Push it on the operator stack. Operands: 1 Operators: +
Read 2. Push it on the operand stack. Operands: 2 1 Operators: +
Read *. Push it on the operator stack. Operands: 2 1 Operators: * +
Read 3. Push it on the operand stack. Operands: 3 2 1 Operators: * +
Read -.
Pop *, 3, and 2. Evaluate 2*3 and push the result (6) on the operand stack. Operands: 6 1 Operators: +
Pop +, 6, and 1. Evaluate 1+6 and push the result (7) on the operand stack. Operands: 7 Operators: empty
Push - on the operator stack. Operands: 7 Operators: -
Read 4. Push it on the operand stack. Operands: 4 7 Operators: -
Read /. Push it on the operator stack. Operands: 4 7 Operators: / -
Read 5. Push it on the operand stack. Operands: 5 4 7 Operators: / -
Read null.
Pop 5, 4 and /. Evaluate 4/5 and push the result (.8) on the operand stack. Operands: .8 7 Operators: -
Pop -, .8, and 7. Evaluate 7-.8 and push the result (6.2) on the operand stack. Operands: 6.2 Operators: empty
The answer is on the top of the operand stack.
John BoltonLocomotive Games (THQ)Current Project: Destroy All Humans (Wii). IN STORES NOW!
First, this isn't a good question for a game programming site.
But I'll answer it since a)its my specialty and b)I'm bored.
What you are trying to do IS a extremely well known topic, and searches will turn up good results.
Second, the langauge isn't important. Just so ya know.

There are two steps: making each meaningful group in your input string meaningful, and then actually running that now-meaningful
string so you can get a result.

Step 1.
What you have to do is break the string up into numbers and operators.
Formally, this is known as tokenizing; also goes by lexical analysis: breaking a string up into tokens, which will be meaningful to the program.
Heres pseudocode illustrating the idea:
define constant ASTERIX 2;
vector token_vector;

if(string[lowerindex, upperindex] == *)
begin
token_vector.put_on_end(ASTERIX);
end

So you will end up with a list of all tokens.
The usual tool for defining a valid "token" is a regular expression.
The seminal program that does lexical analysis is called lex or GNU flex.

2nd step.
This is the tricky part.
Using the same amount of detail will take half the night, and I'm not minded to do that.
You need to know about Backus-Naur Form(BNF), in relation to context-free grammars, depth-first evaluation of n-ary trees, and
semantic parse trees before you continue reading.

Generally, one writes his grammar for the string he wants to parse.
Then in the actual parsing, he forms a logical tree. It may either be a actual tree in memory, or just how its evaulated, etc.
Next, you put the semantic tags on each node in the tree-(so its a '+' operator- that means I need to add).
The task then is to, via a depth-first evaluation of the tree, actually put it into whats known as intermediate code.
Then you actually manipulate(link) the intermediate code. In your case, generating and manipulating(running the equation)will happen one right after the other.
What you are interested in here is the task of parsing.

Issues you will need to consider:
Correctness of your arethmatic grammar- how do you handle parens?
Separation of semantic content from syntactic content.
Ambiguity:

Now, say you have a grammar:
A -> aBc
A -> aB
You now have ambiguity.
This can happen in terms of precedence of operators.
2+3*4 is an excellent example.
Does 2+3 get evaluated first or does 3*4 happen first?
Parentheses are a bear to construct in terms of grammar as well.
[edit] oh yes- The seminal program that does this is called yacc, or GNU bison.

At any rate:
The resources you will find will mostly deal with the task of compiling source code.
Yours is really the same task, but rather simpler.
As a matter of fact, you don't really _need_ to know most of what I've said, and you can write it off of gut instinct, but if you ever want to do stuff like write your own functions in your mathmatical interpreter, you will then need to know this kind of stuff.
Before you ask more questions, I recommend a hard-core google session and some coding of what you've learned. ^_^
~V'lionBugle4d
Look into something called "Regular Expressions". C# Has a great Regex class that will parse a string down into it's component parts given a set of rules. More over, you will probably find someone has already written a regular expression to do something very similar to what you are doing.

As JohnBolton said, equation solving like that, dual stacks can be useful (one for values, another for operators) - the equation put into "Reverse Polish Notation" or similar and a very simple loop can go through and using a switch .. case to switch on the operator stack to work on the operand stacks.

Good luck!
Anything posted is personal opinion which does not in anyway reflect or represent my employer. Any code and opinion is expressed “as is” and used at your own risk – it does not constitute a legal relationship of any kind.
Thanks guys :)

The reason i posted it here is cause it is a math forum. I want to make a game and I suck at math and you need math to make games. I figured if i make a program that does math i would learn math while doing it. Can i say math one more time?

Anyway, it seems this simple program turns out to be quite complicated :P

I think i will find a different way to learn math
hmmmm work sheets...snore :P

Thanks anyway :)
Have a look at boost::spirit and write a simple parser for the input. The writers of the library have ever written a simple Calculator Grammar for their parser which you should be able to use with little or no modification.
Check the Forum FAQ. There are other sites that may be more appropriate for this question.
Graham Rhodes Moderator, Math & Physics forum @ gamedev.net
I would agree general programming would be a more appropriate forum, but I would view it as relevant to game programming. Particularly when it comes to tools for use by level designers. Even in AutoCAD with about any alignment tool you could imagine you find yourself needing to calculate a value.
Keys to success: Ability, ambition and opportunity.
there are good explanations there, but those are not equations, those are expressions. equations have some unknown values inside them. happy programming

This topic is closed to new replies.

Advertisement