Ordering math equation from pseudo code.

Discussion in 'Game Design' started by Antypodish, Nov 26, 2018.

1. Antypodish

Joined:
Apr 29, 2014
Posts:
8,615
Hi,

I am trying figure out, best way to order execution sequence of equation, from pseudo code string.
These code my vary, so is not fixed.

Lets consider following example:
Code (CSharp):
1. a = i * ((4 - k * (3 + 1)) + pow(i, -2 - sin(45 / 180 * PI)));
For simplicity, narrowing the problem down to:
Code (CSharp):
1. i * (4 - k * (3 + 1) )
So, I got this equation as string.
Now I am thinking to split it into terms and store into array, or list.
For example:
1. i
2. *
3. (
4. 4
5. -
6. k
7. *
8. (
9. 3
10. +
11. 1
12. )
13. )

However, from that form, it is hard to extract relevant groups and set ordering.

Another thought was, to use array / list with nested class.
For example:
Code (CSharp):
1. class Term
2. {
3.     Term [] localTerms ;
4. }
Now I can store nested structure, where brackets are involved.
So at depth level 0, I would have something like:
localTerms [0] = 1
localTerms [1] = *
localTerms [2] = 4 - k * (3 + 1)

Them at depth 1, localTerms [2], I can have
localTerms [0] = 4
localTerms [1] = -
localTerms [2] = k
localTerms [3] = *
localTerms [4] = 3 + 1

And finally at dept 2, localTerms [4]
localTerms [0] = 3
localTerms [1] = +
localTerms [2] = 1

From this case, I am mostly concerned, regarding dept 1, where I have both - and * signs.
Of course * equation should be executed before -.

What I am thinking of, is adding some sort of weight, to mathematical signs.
For example,
• - = 0
• + = 0
• * = 1
• / = 1
Then from here, I probably could prioritize and sort pairs of terms, to execute in right order.
But I am not convinced, this is best approach.

Have you any better thoughts, how to bite the problem?

Last edited: Nov 26, 2018
2. kdgalla

Joined:
Mar 15, 2013
Posts:
2,614
I've seen expressions like this stored as a tree. where each leaf is an operand and each non-leaf node is an operator (including parentheses). You could use a binary tree, since most of your operators are binary.

SparrowGS, Socrates and Antypodish like this.
3. Antypodish

Joined:
Apr 29, 2014
Posts:
8,615
This is good thought.
Actually I quite like it.
I shall give try.

4. Lurking-Ninja

Joined:
Jan 20, 2015
Posts:
5,716
You may be interested in this lib: https://github.com/dharmatech/Symbolism

Oh, and the most simple solution: just include an interpreter language (Lua, Python, PHP, whatever) and just solve the string. I did similar thing with a Lua library.

On the other hand, if you want to do it by getting your hands dirty (I do sometimes ), then the tree is your best bet.

Or the stack method (Shunting-yard): https://en.wikipedia.org/wiki/Shunting-yard_algorithm (which is essentially the same as the tree, you just don't build the tree but use a stack to store intermediate results...)

Last edited: Nov 26, 2018
SparrowGS and Antypodish like this.
5. Antypodish

Joined:
Apr 29, 2014
Posts:
8,615
I checked briefly, but not sure, if I is use any of this for my project. I will look again in more details.

Using lua actually may be the thing to solve the equation. I need to think more about it, if is actual use for me too.
I did use lua in previous project, and worked fine, but on single thread of course. Hence I am trying implement multi threaded solution, using ECS

I got ECS core part working, but now I need link, between stringified expressions, to ECS.

So far best candidate

I do remember reading similar topic while ago. I forgot about it. This is good too in fact.

Definitely something to thinkering

6. Lurking-Ninja

Joined:
Jan 20, 2015
Posts:
5,716
You're right I remembered incorrectly, this is not the tool which had the string parser. It's just simplifies the equations. Somewhere I have a script which does that, I can't find it among my bookmarks at the moment. Probably they didn't name it very well.

Last edited: Nov 26, 2018
7. Antypodish

Joined:
Apr 29, 2014
Posts:
8,615
No worry. If you find it that would be nice. But likely I will go with one of already covered solutions.

8. Antypodish

Joined:
Apr 29, 2014
Posts:
8,615
I think I will give a try to convert this algorithm
rmbreak/calc-project
And see where it will lead me.

Looks like is complete, among few i found, of which state is uncertain.
However, this one even supports basics math functions. But is least of my concerns atm.

Lurking-Ninja likes this.
9. TonicMind

Joined:
Nov 9, 2014
Posts:
1,211
That is what's known as BNF (Backus Naur form). I think it would be a good idea to look it up. Its an essential part of compiler development, specifically text parsing, which is what the OP is doing here in some ways.

Antypodish likes this.
10. kdgalla

Joined:
Mar 15, 2013
Posts:
2,614
Now that you mention it, I think it was a university course on compilers where i'd seen this. That was a looong time ago, though.

Lurking-Ninja and TonicMind like this.
11. TonicMind

Joined:
Nov 9, 2014
Posts:
1,211
You know whats funny?

In the past I sort of 'hoarded' my knowledge of things in computer science. IDK. I had some weird irrational fear about sharing it, yet it doesn't matter too much anymore. It feels good to share what I've learned over my time at university.

Going back to the topic I created on these boards about 'free' work and open sourcing things, I think it is mutually beneficial to share knowledge. Not only does it feel good, it is good. This does not mean that I will work on a game for revenue share or just give away the product of hard work, that has to be of my choosing, but if someone needs help I am happy to provide.

As a related note I am not too bothered if someone takes inspiration by things I've done, and it has already happened. Just don't expect me to give you a formula.

I forgot to mention I absolutely love my major. I am in an advanced algorithms class. For every algorithms class I took before, I found it exceedingly boring and monotonous. I'll chalk that up to the depression. However this semester has been eye opening and a blast! I retain knowledge better. For the first time in my life I feel I am a competent computer scientist.

I have always said grades and GPA don't mean much. I didn't believe it 100% but now that is the case. My GPA isn't the best. Yet I have a good friend with a higher GPA, who had trouble with the basic things like Git, and data structures when we last sat down to work on a project. It was really eye opening!

12. Antypodish

Joined:
Apr 29, 2014
Posts:
8,615
Just let you guys know, so far I choose Shunting Yard algorithm.
Hence, thank you all for highly valuable inputs.

Further, I have modified and expanded this algorithm accordingly.
Then I will execute it only at code parsing time.

Seams along with general mathematical expressions, I got basics custom functions and if / else loops working on that level. Later I need add while and for loops and I think, it will be it on that part.

Now is just building nice interface to work with ECS.

Well, of course. I do share sometimes snipets, rather full scripts. I love doing experimenting, hence I never got code, which is fully ready for publication. Well, other than mods to the game, which I did in past. But by sharing, like in example Shunt Algorithm link above, etc. it speeds up work significantly.

Making games / apps which are open source, are also good source for knowledge.

There are ROS (Robotic Operating System) projects on github. Initially sponsored for almost decade, spending multimillion \$\$\$ on it. But with main purpose, to keep it open source and mostly MIT licence.
Thx to that, we have significant progress in robotic academia, hobbyists and even industry, rather than keeping it proprietary. So is definitely good.

On side note, all best in study

Lurking-Ninja likes this.
13. ClaudiaTheDev

Joined:
Jan 28, 2018
Posts:
303
You already have a solution and I dont know about ECS -> so perhaps this answer will be totally not fitting but it could be still helpful.

If very good performance isnt crucial on this part and you have c# code:

System:Linq.Dynamic can intepret and execute C# code at runtime. It is very easy and comofortable to use.
For varying syntax/code you can use Regular Expressions to replace keywords to make the inital string to c# code.

14. Antypodish

Joined:
Apr 29, 2014
Posts:
8,615
Thank you for suggestion.
I need admit, I am not familiar with System:Linq.Dynamic
But my requirement is, to convert string, into strictly numeric representation, rather than evaluate expression itself.
This is for ECS purposes, since it can not handle strings.

So lets assume I got x = 2 + y expression, where y = 3 ;
x become reference to variable indexed 0, and y become reference to index 1. Where indexes reference relevant value in an array of variables.
= and + have own reference indexes.
And each component, number, variable operator, has assigned type index as well.
So in the end, after evaluation, I have something like
x = 2 + y (expression as string)
0 0 2 1 1 (Data type in ECS)
5 - - - 3 (Corresponding value to data type in ECS )

Just to add, if anyone is interested, I am using RPN (Reverse Polish Notation) for evaluation.

Hence I am unsure, if proposed Linq solution would be suitable for that reason.

15. Lurking-Ninja

Joined:
Jan 20, 2015
Posts:
5,716
Finally, I have found it. I know it won't be any help at this point, but I just found it among my bookmarks today and I remembered that I promised.

https://github.com/davideicardi/DynamicExpresso/

Antypodish likes this.
16. Antypodish

Joined:
Apr 29, 2014
Posts:
8,615
Thx. Looks good for reference indeed.
But I see it uses Linqu and Reflections. So not sure how good could it be, if I would dig in deeper. And how compliant with ECS I could make it.
But anyway, I have done it mostly.

Lurking-Ninja likes this.

Joined:
Jan 20, 2015
Posts:
5,716
Super cool!

unityunity