Sign in to follow this  

equation parsing

This topic is 4864 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 :)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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. ^_^

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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 :)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
there are good explanations there, but those are not equations, those are expressions. equations have some unknown values inside them. happy programming

Share this post


Link to post
Share on other sites

This topic is 4864 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this