How do you program a way to create mathematics formulas?

For one of my project ideas, I want to create a dice rolling app. It would allow people to setup somewhat complex combinations of dice roll cascades in a visual way.

I have a pretty good idea on how I would program the logic for the dice, namely as if you're creating a math formula;

Class:

``````Formula
``````

Properties:

``````Left formula
Right formula
Function
``````

Thus, adding `X = A + B` would consist of Formula `X`, with left `Formula A`, right `Formula B` and function `Add`. Formula A and B would consist of left `a` or `b`, right `null` and function `Constant`.

This approach seems fine to me, but I like to try and find approaches others have come up with. However, because 'programming math' tends to lead to completely different questions (of the 'Do I need to learn math to program' or 'How do I program this formula' variety), I'm having difficulties finding other approaches.

-
I'm new to this StackExchange site, so anyone is encouraged to give this more appropriate tags. – SpacyRicochet Jan 15 '14 at 21:27
You might be interested in Abstract Syntax Trees (AST), especially how Lisp written in S-Expressions is an AST serialization. You could basically give the user some means to assemble the AST (e.g. by parsing a text expression), and then evaluate the AST with a simple interpreter. – amon Jan 15 '14 at 21:39
@amon Thanks! AST is apparently a proper term to search for. Googling already yielded this useful question: stackoverflow.com/questions/1721553/… – SpacyRicochet Jan 15 '14 at 21:42
If no one else give you what you need let me know after a week or so. It's been quite a number of years since I've written this sort of parser and I would have to think about how it worked exactly. I know the general idea, but trying to describe it to you would take a little more of my gray cells than I have available right now. – Eliptical view Jan 16 '14 at 10:07

One way to do this is to convert your math / dice expression to Reverse Polish Notation (postfix). Once converted, the expression is fairly easy to evaluate.

To do the conversion, you can use the Shunting Yard Algorithm. This can handle not only basic operators, but also nested expressions and function calls.

The only area you would have to extend is handling the nD dice notation. So instead of `5 + 5`, you'd be interpreting `5d6 + 5d6`. That should be easy enough to handle once you have the expression reduced to tokens.

An expression evaluator like this is a very good learning project.

-

If I was implementing a formula-based dice calculator, my tendency would be to start by implementing a standard calculator (i.e., supporting PEMDAS). This would normally involve tokenizing and parsing an input string (into a tree), evaluating the root node of the tree (which cascades down the tree). Most popular programming languages usually have a wide variety of tutorials describing how to do this.

E.g., 5+2*6 would become

``````    +
/ \
5   *
/ \
2   6
``````

then

``````    +
/ \
5   12
``````

then

`````` 17
``````

After implementing a standard calculator, I would add one additional operator, the "d" operator, defined as follows:
XdY = Summation of X randomly generated integers between (inclusive) 1 and Y.
For example, 2D6+1D3 means "roll 2 6-sided dice and 1 3-sided die." Many audiences interested in dice rollers (particularly role-players) are already familiar with this notation.