# Generating random math expression

I have this idea running around in my head, to generate and evaluate random mathematical expressions. So, I decided to give it a shot and elaborate an algorithm, before coding it to test it.

## Example:

Here are some example expressions I want to generate randomly:

``````4 + 2                           [easy]
3 * 6 - 7 + 2                   [medium]
6 * 2 + (5 - 3) * 3 - 8         [hard]
(3 + 4) + 7 * 2 - 1 - 9         [hard]
5 - 2 + 4 * (8 - (5 + 1)) + 9   [harder]
(8 - 1 + 3) * 6 - ((3 + 7) * 2) [harder]
``````

The easy and medium ones are pretty straight-forward. Random `int`s separated by random operators, nothing crazy here. But I'm having some trouble getting started with something that could create one of the hard and harder examples. I'm not even sure a single algorithm could give me the last two.

## What I am considering:

I can't say I tried those ideas, because I didn't really want to waste much time going in a direction that had no chance of working in the first place. But still, I thought of a couple solutions:

• Using trees
• Using regular expressions
• Using a crazy "for-type" loop (surely the worst)

## What I'm looking for:

I'd like to know which way you believe is the best to go, between the solutions I considered, and your own ideas.

If you see a good way to start, I'd appreciate a lead in the right direction, e.g. with the beginning of the algorithm, or a general structure of it.

Also note that I will have to evaluate those expressions. This can be done either after the expression is generated, or during its creation. If you take that in consideration in your answer, that's great.

I'm not looking for anything language-related, but for the record, I'm thinking of implementing it in Objective-C, as that's the language I'm most working with recently.

Those examples did not include the `:` operator, as I only want to manipulate `int`s, and this operator adds many verifications. If your answer gives a solution handling this one, that's great.

• hmmm, add a fitness function and it looks like you're headed towards genetic programming. Apr 23 '13 at 15:19

Here's a theoretic interpretation of your problem.

You are looking to randomly generate words (algebraic expression) from a given language (the infinite set of all syntactically correct algebraic expressions). Here's a formal description of a simplified algebraic grammar supporting only addition and multiplication:

``````E -> I
E -> (E '+' E)
E -> (E '*' E)
``````

Here, `E` is an expression (i.e., a word of your language) and `I` is a terminal symbol (i.e., it's not expanded any further) representing an integer. The above definition for `E` has three production rules. Based on this definition, we can randomly build a valid arithmetic as follows:

1. Start with `E` as the single symbol of the output word.
2. Choose uniformly at random one of the non-terminal symbols.
3. Choose uniformly at random one of the production rules for that symbol, and apply it.
4. Repeat steps 2 - 4 until only terminal symbols are left.
5. Replace all terminal symbols `I` by random integers.

Here's an example of the application of this algorithms:

``````E
(E + E)
(E + (E * E))
(E + (I * E))
((E + E) + (I * E))
((I + E) + (I * E))
((I + E) + (I * I))
((I + (E * E)) + (I * I))
((I + (E * I)) + (I * I))
((I + (I * I)) + (I * I))
((2 + (5 * 1)) + (7 * 4))
``````

I assume you would choose to represent an expression with an interface `Expression` which is implemented by classes `IntExpression`, `AddExpression` and `MultiplyExpression`. The latter two then would have a `leftExpression` and `rightExpression`. All `Expression` subclasses are required to implement an `evaluate` method, which works recursively on the tree structure defined by these objects and effectively implements the composite pattern.

Note that for the above grammar and algorithm, the probability of expanding an expression `E` into a terminal symbol `I` is only `p = 1/3`, while the probability to expand an expression into two further expressions is `1-p = 2/3`. Therefore, the expected number of integers in a formula produced by the above algorithm is actually infinite. The expected length of an expression is subject to the recurrence relation

``````l(0) = 1
l(n) = p * l(n-1) + (1-p) * (l(n-1) + 1)
= l(n-1) + (1-p)
``````

where `l(n)` denotes the expected length of the arithmetic expression after `n` applications of production rules. I therefore suggest that you assign a rather high probability `p` to the rule `E -> I` such that you end up with a fairly small expression with high probability.

EDIT: If you're worried that the above grammar produces too many parenthesis, look at Sebastian Negraszus' answer, whose grammar avoids this problem very elegantly.

• Whoa.. That's great, I like that a lot, thanks ! I still have to look a bit more into all the solutions suggested to make the right choice. Thanks again, great answer. Apr 23 '13 at 9:23
• Thanks for your edit, that's something I didn't think of. Do you think limiting the number of times you go through steps 2-4 could work ? Say, after 4 (or whatever) iterations of steps 2-4, only allow the rule E->I ? Apr 23 '13 at 9:32
• @rdurand: Yes, of course. Say after `m` iterations of 2-4, you 'ignore' the recursive production rules. This will lead to an expression of expected size `l(m)`. Note however, that this is (theoretically) not necessary, since the probability of generating an infinite expression is zero, even though the expected size is infinite. However, your approach is favorable since in practice, memory is not only finite, but also small :) Apr 23 '13 at 9:36
• With your solution, I don't see a way I could solve the expression while building it. Is there any ? I can still solve it afterwards, but I'd rather not. Apr 23 '13 at 12:01
• If you want that, why not start with a random number as the base expression and randomly decompose it (rewrite it) into operations, in the manner blubb described? Then, not only would you have the solution for the entire expression, but you would also easily get subsolutions for each of the branches of the expression tree. Apr 23 '13 at 12:59

first of all I'd actually generate the expression in postfix notation, you can easily convert to infix or evaluate after generating your random expression, but doing it in postfix means you don't need to worry about parenthesis or precedence.

I'd also keep a running total of the number of terms available to the next operator in your expression (assuming you want to avoid generating expressions that are malformed) i.e. somthing like this:

``````string postfixExpression =""
int termsCount = 0;
while(weWantMoreTerms)
{
if (termsCount>= 2)
{
var next = RandomNumberOrOperator();
postfixExpression.Append(next);
if(IsNumber(next)) { termsCount++;}
else { termsCount--;}
}
else
{
postfixExpression.Append(RandomNumber);
termsCount++;
}
}
``````

obviously this is pseudo code so is not tested/may contain mistakes and you probably wouldn't use a string but a stack of some discriminated union like type

• this currently assumes all operators are binary, but its fairly easy to extend with operators of different arity
– jk.
Apr 23 '13 at 8:50
• Thanks a lot. I didn't think of RPN, that's a good idea. I'll look into all the answers before accepting one, but I think I could make this work. Apr 23 '13 at 9:04
• @rdurand Part of the advantage of post-fix means you don't have to worry about precedence (that has already been taken into consideration prior to adding it to the post-fix stack). After which, you simply pop all operands you find until you pop the the first operator you find on the stack and then push onto the stack the result and you continue in this way until you pop the last value off the stack.
– Neil
Apr 23 '13 at 9:47
• @rdurand The expression `2+4*6-3+7` gets converted into post-fix stack `+ 7 - 3 + 2 * 4 6` (top of the stack being right-most). You push off 4 and 6 and apply operator `*`, then you push 24 back on. You then pop 24 and 2 and apply operator +, then you push 26 back on. You continue in this way and you'll find you'll get the right answer. Notice that `* 4 6` are the first terms on the stack. That means it is performed first because you've already determined precedence without requiring parentheses.
– Neil
Apr 23 '13 at 10:07
• Late response, but @Neil's comment isn't quite accurate, even if it evaluates to the same thing. In postfix, that expression becomes `2 4 6 * + 3 - 7 +` -- conversion between representations always leaves the operands in the same order. Nov 2 '14 at 1:12

blubb's answer is a good start, but his formal grammar creates too many parantheses.

Here's my take on it:

``````E -> I
E -> M '*' M
E -> E '+' E
M -> I
M -> M '*' M
M -> '(' E '+' E ')'
``````

`E` is an expression, `I` an integer and `M` is an expression that is an argument for a multiplication operation.

• Nice extension, this one certainly looks less cluttered! Apr 23 '13 at 15:31
• As I commented on blubb's answer, I'll keep some unwanted parenthesis. Maybe make the random "less random" ;) thanks for the add-on ! Apr 23 '13 at 15:36

The parentheses in the "hard" expression represent order of evaluation. Rather than trying to generate the displayed form directly, just come up with a list of operators in random order, and derive the display form of the expression from that.

Numbers: `1 3 3 9 7 2`

Operators: `+ * / + *`

Result: `((1 + 3) * 3 / 9 + 7) * 2`

Deriving the display form is a relatively simple recursive algorithm.

Update: here is an algorithm in Perl to generate the display form. Because `+` and `*` are distributive, it randomizes the order of the terms for those operators. That helps keep the parentheses from all building up on one side.

``````use warnings;
use strict;

sub build_expression
{
my (\$num,\$op) = @_;

my \$last_num = pop @\$num;
my \$last_op = pop @\$op;

#Base case: return the number if there is just a number
return \$last_num unless defined \$last_op;

#Recursively call for the expression minus the final term.
my \$rest = build_expression(\$num,\$op);

#Add parentheses if there is a bare + or - and this term is * or /
\$rest = "(\$rest)" if (\$rest =~ /[+-][^)]+\$|^[^)]+[+-]/ and \$last_op !~ /[+-]/);

#Return the two components in a random order for + or *.
return \$last_op =~ m|[-/]| || rand(2) >= 1 ?
"\$rest \$last_op \$last_num" : "\$last_num \$last_op \$rest";
}

my @numbers   = qw/1 3 4 3 9 7 2 1 10/;
my @operators = qw|+ + * / + * * +|;

print build_expression([@numbers],[@operators]) , "\n";
``````
• This algorithm seems to always generate imbalanced trees: left branch is deep, while the right one is just a single number. There would be too much opening parans in the beggining of each expression, and the order of operations is always left to right. Apr 23 '13 at 8:56
• Thanks for your answer, dan, it helps. But @scriptin, I don't understand what you don't like in this answer ? Could you explain a bit ? Apr 23 '13 at 9:08
• @scriptin, that can be fixed with simple randomization of the display order. See the update.
– user82096
Apr 23 '13 at 9:10
• @rdurand @dan1111 I've tried the script. The issue of big left subtree is fixed, but generated tree is still very imbalanced. This picture shows what I mean. This may not be considered a problem, but it leads to situation where subexpressions like `(A + B) * (C + D)` are never presented in generated expressions, and there are also a lot of nested parens. Apr 23 '13 at 9:20
– user82096
Apr 23 '13 at 9:23

To expand on the tree approach, let's say each node is either a leaf or a binary expression:

``````Node := Leaf | Node Operator Node
``````

Note that a leaf is just a randomly-generated integer here.

Now, we can randomly generate a tree. Deciding the probability of each node being a leaf allows us to control the expected depth, although you might want an absolute max depth as well:

``````Node random_tree(leaf_prob, max_depth)
if (max_depth == 0 || random() > leaf_prob)
return random_leaf()

LHS = random_tree(leaf_prob, max_depth-1)
RHS = random_tree(leaf_prob, max_depth-1)
return Node(LHS, RHS, random_operator())
``````

Then, the simplest rule for printing the tree is to wrap `()` around each non-leaf expression and avoid worrying about operator precedence.

For example, if I parenthesize your last sample expression:

``````(8 - 1 + 3) * 6 - ((3 + 7) * 2)
((((8 - 1) + 3) * 6) - ((3 + 7) * 2))
``````

you can read off the tree that would generate it:

``````                    SUB
/      \
MUL        MUL
/     6     /   2
/   3        3   7
SUB
8   1
``````

I would use trees. They can give you great control on the generation of the expressions. E.g. you can limit the depth per branch and width of each level separately. Tree based generation also gives the answer already during the generation, which is useful if you want to ensure that also the result (and subresults) are hard enough and/or not too hard to solve. Especially if you add division operator at some point, you can generate expressions that evaluate to whole numbers.

• Thanks for your answer. I had the same idea about trees, being able to evaluate/check subexpressions. Maybe you could give a tiny bit more details about your solution ? How would you build such a tree (not how really, but what would the general structure be)? Apr 23 '13 at 9:06

Here's a slightly different take on Blubb's excellent answer:

What you're trying to build here is essentially a parser that operates in reverse. What your problem and a parser have in common is a context-free grammar, this one in Backus-Naur form:

``````digit ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
number ::= <digit> | <digit> <number>
op ::= '+' | '-' | '*' | '/'
expr ::= <number> <op> <number> | '(' <expr> ')' | '(' <expr> <op> <expr> ')'
``````

Parsers start with a stream of terminals (literal tokens like `5` or `*`) and try to assemble them into nonterminals (things composed of terminals and other nonterminals, such as `number` or `op`). Your problem starts with nonterminals and works in reverse, picking anything between the "or" (pipe) symbols at random when one is encountered and recursively repeating the process until reaching a terminal.

A couple of the other answers have suggested that this is a tree problem, which it is for a certain narrow class of cases where there are no nonterminals that reference themselves directly or indirectly through another nonterminal. Since grammars allow that, this problem is really a directed graph. (Indirect references through another nonterminals count toward this as well.)

There was a program called Spew published on Usenet in the late 1980s which was originally designed to generate random tabloid headlines and also happens to be a great vehicle for experimenting with these "reverse grammars." It operates by reading a template that directs the production of a random stream of terminals. Beyond its amusement value (headlines, country songs, pronounceable English gibberish), I've written numerous templates that are useful for generating test data that's ranged from plain text to XML to syntactically-correct-but-uncompilable C. Despite being 26 years old and written in K&R C and having an ugly template format, it compiles just fine and works as advertised. I whipped up a template that solves your problem and posted it on pastebin since adding that much text here doesn't seem appropriate.