Ordering math equation from pseudo code.

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:

Spoiler

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.

Spoiler

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?

 

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.

 

This is good thought.
Actually I quite like it.
I shall give try.

 

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

 

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

 

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.

 

No worry. If you find it that would be nice. But likely I will go with one of already covered solutions.

 

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.

 

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.

 

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.

 

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!

 

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

 

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.

 

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.

 

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/

 

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.

Spoiler

 

Super cool!