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 treesUsing regular expressionsUsing 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.
Generating random math expression
algorithms
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:Start with E as the single symbol of the output word.Choose uniformly at random one of the non-terminal symbols.Choose uniformly at random one of the production rules for that symbol, and apply it.Repeat steps 2 - 4 until only terminal symbols are left.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 relationl(0) = 1l(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.