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