[Haskell-cafe] Arithmetic expressions with random operators
ok at cs.otago.ac.nz
ok at cs.otago.ac.nz
Thu Jun 8 22:54:47 UTC 2017
>
> On Thu, Jun 08, 2017 at 04:03:55PM +0300, Mahmoud Murad wrote:
>> I have the following problem, I want to randomly generate arithmetic
>> expressions based on a number, for example:
>> if I have n = 3, then the expression must have 3 operators like this
>> (4)*(((3+5)-2)).
>
I don't seem to have the original message in my mailbox,
so my response may be inappropriate. Generating random
arithmetic expressions in Haskell has two parts: how to
generate random arithmetic expressions at all, and how to
do it in Haskell.
Assuming that "arithmetic expressions" means expressions
using numbers and the four binary operations + - * / (or
possibly the exponentiation operator as well), the basic
problem reduces to
* generate a random binary tree with n internal nodes
* assign random numbers to the leaves
* assign random operators to the internal nodes
The last two subtasks are pretty easy. This leaves
generating random binary trees as the main problem.
This paper may help:
http://www.cs.otago.ac.nz/staffpriv/mike/Papers/RandomGeneration/RandomBinaryTrees.pdf
There's a survey paper at
http://www.sis.uta.fi/cs/reports/A-1998-3.ps.Z
and the Atkinson/Sack approach does seem to be pretty good,
at least if you want to make *large* expressions.
This only matters if you want all expressions to be equally
likely. You may not.
More information about the Haskell-Cafe
mailing list