Algorithmically generating all valid expressions-CodePudding

Let's say I have some unary operations (negate, bitwise not, etc...), some binary operations (subtract, add, multiply, divide, bit shift, etc...), one possible operand (we'll say the operand must be the number 1), and allow grouping by parentheses. Is there a way to generate all valid expressions (and only valid expressions) of a given length which can be created using these operators?

For instance, let's say I want all expressions of 4 characters. The following might be a subset of the generated list:

    (-1)
    -1*1
    ~(1)
    ~-~1
    // etc...

Some 7 character expressions:

    (1 1)<<1 // let's assume bitshifting is 1 character, since it's 1 operation.
    1/(1>>1) // expressions which fail to be evaluated (1/0) are fine, as long as they can be parsed.
    -~(1-1)
    // etc...

An example of a longer expression to show some complexity in grouping:

    ((1<<(1 1 1))*(1 1))/((1<<(1 1)) 1)

CodePudding user response：

You could bootstrap the process by first concentrating on producing expressions that only consist of an operand with zero or more wrapped parentheses.

Here is a generator (in JavaScript syntax) that yields valid expressions with that limitation in mind:

const operands = ["1"];

function* generateOperands(n) { // n is the size of the strings to generate
    if (n < 1) return;
    for (let operand of operands) {
        if (operand.length === n) {
            yield operand;
        }
    }
    // Use recursion to add a pair of parentheses:
    for (let operand of generateOperands(n - 2)) {
        yield "("   operand   ")";
    }
}

NB: If you're not happy with the yield syntax, then just replace that with a push of the expression in some result array, or call a callback with that expression as argument.

Now extend this to use unary operators:

const operands = ["1"];
const unaries = ["!", "~", "-"];

function* generateOperands(n) {
    if (n < 1) return;
    for (let operand of operands) {
        if (operand.length === n) {
            yield operand;
        }
    }
    for (let operand of generateOperands(n - 2)) {
        yield "("   operand   ")";
    }
}

function* generateUnary(n) {
    yield* generateOperands(n);
    if (n < 2) return;
    for (let unary of unaries) {
        for (let expression of generateUnary(n - unary.length)) {
            yield unary   expression;
        }
        for (let expression of generateUnary(n - unary.length - 2)) {
            yield "("   unary   expression   ")";
        }
    }
}

And finally add the possibility to include binary operator(s). Use the idea of the following recursive grammar:

expression := unary-expression [binary-operator expression]

...with this runnable code:

const operands = ["1"];
const unaries = ["!", "~", "-"];
const binaries = ["-", " ", "*", "/", ">>", "<<"];

function* generateOperands(n) {
    if (n < 1) return;
    for (let operand of operands) {
        if (operand.length === n) {
            yield operand;
        }
    }
    for (let operand of generateOperands(n - 2)) {
        yield "("   operand   ")";
    }
}

function* generateUnary(n) {
    yield* generateOperands(n);
    if (n < 2) return;
    for (let unary of unaries) {
        for (let expression of generateUnary(n - unary.length)) {
            yield unary   expression;
        }
        for (let expression of generateUnary(n - unary.length - 2)) {
            yield "("   unary   expression   ")";
        }
    }
}

function* generate(n) {
    yield* generateUnary(n);
    if (n < 3) return;
    for (let binary of binaries) {
        for (let i = 1; i < n - binary.length; i  ) {
            for (let left of generateUnary(i)) {
                for (let right of generate(n - i - binary.length)) {
                    yield left   binary   right;
                }
            }
            for (let left of generateUnary(i - 2)) {
                for (let right of generate(n - i - binary.length)) {
                    yield "("   left   binary   right   ")";
                }
            }
        }
    }
}

// Demo
for (let expression of generate(4)) {
    console.log(expression);
}