16

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 ints 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 ints, and this operator adds many verifications. If your answer gives a solution handling this one, that's great.

If my question needs any clarification, please ask in the comments. Thanks for your help.

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

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.

| improve this answer | |
  • 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. – rdurand 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 ? – rdurand Apr 23 '13 at 9:32
  • 1
    @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 :) – blubb 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. – rdurand 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. – mikołak Apr 23 '13 at 12:59
9

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

| improve this answer | |
  • 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. – rdurand Apr 23 '13 at 9:04
  • 2
    @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
  • 1
    @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
  • 1
    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. – Schism Nov 2 '14 at 1:12
4

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.

| improve this answer | |
  • 1
    Nice extension, this one certainly looks less cluttered! – blubb 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 ! – rdurand Apr 23 '13 at 15:36
3

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) = @_;

    #Start with the final term.
    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";
| improve this answer | |
  • 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. – scriptin 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 ? – rdurand 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. – scriptin Apr 23 '13 at 9:20
  • 3
    @scriptin, after thinking about this, I agree this is a problem. – user82096 Apr 23 '13 at 9:23
2

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
          ADD          ADD
         /   3        3   7
       SUB
      8   1
| improve this answer | |
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.

| improve this answer | |
  • 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)? – rdurand Apr 23 '13 at 9:06
1

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.