Number(self): return the number of iterations required to step through the iterator, assuming it started at rank one.

Rank(self,L): return the rank of the current iteration. Optionally pass L, a list or one-dimensional rtable, and return its rank.

Unrank(self,rnk): return a one-dimensional Array corresponding to the iterator output with rank rnk.

DigitalPuzzle := module()
export ModuleApply;
local Expr, Print;

    # Given the L and R Arrays from the BinaryTree iterator,
    # construct an expression corresponding to the tree,
    # where o[v[i]] is the arithmetic operator of the i-th
    # internal node (the v-Array is used to change the operators
    # for a given tree).
    Expr := proc(L,R)
    local leaf,prefix;
    global o,v;
        leaf := 0;
        prefix := proc(i)
            if i=0 then leaf := leaf+1;
            else 'o'['v'[i]](prefix(L[i]),prefix(R[i]));
            end if;
        end proc;
        prefix(1);
    end proc:

    # Given the L and R arrays of the current tree, and an array, v,
    # that maps the internal nodes to the arithmetic operators (stored
    # in o), print a string corresponding to the desired equality.
    # Avoid most superfluous parentheses.
    Print := proc(L,R,v,o,targ)
    local leaf,infix,top;
        leaf := 0;
        top := true;
        infix := proc(i)
            if i=0 then leaf := leaf+1;
            elif top then
                top := false;
                sprintf("%A %A %A", infix(L[i]), o[v[i]], infix(R[i]));
            elif v[i]=2 then
                sprintf("%A %A %A", infix(L[i]), o[v[i]], infix(R[i]));
            else
                sprintf("(%A %A %A)", infix(L[i]), o[v[i]], infix(R[i]));
            end if;
        end proc;
        printf("%s = %a\n", infix(1), targ);
    end proc:

    ModuleApply := proc(n::posint, targ:=100)
    local A,Accept,cnt,ops,Op,BT,LR,R,s;
    uses Iterator;

        # Array of arithmetic operators
        ops := Array(0..3,[`+`,`-`,`*`,`/`]);

        # Template for the accept predicate.
        Accept := proc(v,o:=ops)
        local j;
            # Prune trees with a right branch that connects
            # two additive or two multiplicative operators.
            for j to n do
                if R[j]<>0 and (v[j] <= 1 xor v[R[j]] > 1) then
                    return false;
                end if;
            end do;
            # Use try/catch to handle division by zero.
            try
                evalb(_ex=targ);
            catch:
                false;
            end try;
        end proc;

        # Construct an iterator that generates all possible values of
        # arithmetic operators (as an Array with values from 0 to 3
        # corresponding to the four operations), but accepts (outputs)
        # only those that meet the criteria.
        Op := MixedRadixTuples([4$n]);

        # Construct an iterator that generates all binary trees
        # with n-internal nodes (and n+1 leaves).
        BT := BinaryTrees(n);

        cnt := 0; # success counter

        # Loop through all binary trees
        for LR in BT do
            R := LR[2];
            # Assign A, by specializing Accept to the
            # selected tree.
            A := subs('_ex'=Expr(LR),op(Accept));

            # Loop through all possibilities of assigning
            # the arithmetic operators to the internal nodes of the
            # tree, keeping only those that evaluate to the target.
            for s in Op do
                if A(s) then
                    cnt := cnt+1;
                    Print(LR,s,ops,targ);
                end if;
            end do;
        end do;
        cnt;
    end proc:
end module:

$\mathrm{DigitalPuzzle}\left(6\right)$

((1 + (2 + 3) * 4 * 5) + 6) - 7 = 100
((1 - 2) + 3) + (4 * 5 - 6) * 7 = 100
(1 - 2 * 3) + ((4 + 5) + 6) * 7 = 100
1 * 2 * ((3 + (4 + 5) * 6) - 7) = 100
(1 + 2 * 3 * 4) * ((5 + 6) - 7) = 100
(1 - 2 * 3) * 4 * 5 * (6 - 7) = 100
(1 - 2 * 3) * 4 * 5 / (6 - 7) = 100

$7$

DigitalPuzzle2 := module()
export ModuleApply, Accept, Flatten;
local Print;

    # Given the L and R arrays from the BinaryTrees iterator,
    # flatten the tree into postfix form.  The result is
    # stored in the one-dimensional Array Data.
    # The leaves are represented as the corresponding integer,
    # the internal nodes as the negative of the node number.
    Flatten := proc(L :: Array(datatype=integer[4])
                    , R :: Array(datatype=integer[4])
                    , Data :: Array(datatype=integer[4])
                    , n :: posint
                   )
    local leaf,postfix,node,data;
        leaf := 0;
        postfix := proc(node)
            if node=0 then
                leaf := leaf+1;
            else
                ( procname(L[node]), procname(R[node]), -node );
            end if;
        end proc;
        data := [postfix(1)];
        for node to 2*n+1 do
            Data[node] := data[node];
        end do;
        NULL;
    end proc;

    # Given the R array from BinaryTree iterator and the flattened
    # tree structure (Data), from Flatten, and the array, Ops, holding
    # the arithmetic operations, coded as 0=+, 1=-, 2=*, 3=/, for each
    # of the internal nodes, return true if the tree equals the target
    # value, targ.  This routine will be compiled.  The Stack argument
    # is used as a working stack.
    Accept := proc( R :: Array(datatype=integer[4])
                    , Data :: Array(datatype=integer[4])
                    , Stack :: Array(datatype=float[8])
                    , Ops :: Array(datatype=integer[4])
                    , n :: posint
                    , targ :: float
                  )
    local ptr :: integer
        , node :: integer
        , datum :: integer
        , l :: float
        , r :: float
        , f :: integer
        , val :: float
        ;

        # Prune trees with a right branch that connects
        # two additive or two multiplicative operators.
        for node to n do
            if R[node]<>0 and (Ops[node] <= 1 xor Ops[R[node]] > 1) then
                return false;
            end if;
        end do;

        # Evaluate the flattened tree
        ptr := 0;
        for node to 2*n+1 do
            datum := Data[node];
            if datum > 0 then
                # datum is a leaf value.  Push onto stack.
                ptr := ptr+1;
                Stack[ptr] := datum;
            else
                # -datum is an internal node number;
                # internal nodes correspond to arithmetic operations.
                # Pop the top two elements off the stack,
                # compute the result, and push onto the stack.
                r := Stack[ptr];
                ptr := ptr-1;
                l := Stack[ptr];
                f := Ops[-datum];
                if   f = 0 then Stack[ptr] := l + r;
                elif f = 1 then Stack[ptr] := l - r;
                elif f = 2 then Stack[ptr] := l * r;
                else            Stack[ptr] := l / r;
                end if;
            end if;
        end do;

        # Test whether the computed value matches the target.
        val := Stack[1];
        if abs(val - targ) < 1e-6 then
            return true;
        else
            return false;
        end if;
    end proc;

    Accept := Compiler:-Compile(Accept);

    # Given the L and R arrays of the current tree, and an array, v,
    # that maps the internal nodes to the arithmetic operators (stored
    # in o), print a string corresponding to the desired equality.
    Print := proc(L,R,v,o,targ)
    local leaf,infix,top;
        leaf := 0;
        top := true;
        infix := proc(i)
            if i=0 then leaf := leaf+1;
            elif top then
                top := false;
                sprintf("%A %A %A", infix(L[i]), o[v[i]], infix(R[i]));
            elif v[i]=2 then
                sprintf("%A %A %A", infix(L[i]), o[v[i]], infix(R[i]));
            else
                sprintf("(%A %A %A)", infix(L[i]), o[v[i]], infix(R[i]));
            end if;
        end proc;
        printf("%s = %a\n", infix(1), targ);
    end proc:

    ModuleApply := proc(n::posint, targ:=100)
    local Data
        , Stack
        , cnt,ops,Op,BT,LR,R,V;
    uses Iterator;

        # Array of arithmetic operators
        ops := Array(0..3,[`+`,`-`,`*`,`/`]);

        # Construct an iterator that generates all possible values of
        # arithmetic operators (as an Array with values from 0 to 3
        # corresponding to the four operations), but accepts (outputs)
        # only those that meet the criteria.
        Op := MixedRadixTuples([4$n]);

        # Construct an iterator that generates all binary trees
        # with n-internal nodes (and n+1 leaves).
        BT := BinaryTrees(n);

        Data := Array(1..2*n+1, 'datatype'=integer[4]);
        Stack := Array(1..2*n+1, 'datatype'=float[8]);

        cnt := 0; # success counter

        # Loop through all binary trees
        for LR in BT do
            # Assign Data the flattened structure of the tree
            Flatten(LR,Data,n);
            R := LR[2];
            # Loop through all possibilities of assigning
            # the arithmetic operators to the internal nodes of the
            # tree
            for V in Op do
                if Accept(R,Data,Stack,V,n,targ) then
                    cnt := cnt+1;
                    Print(LR,V,ops,targ);
                end if;
            end do;
        end do;
        cnt;
    end proc:
end module:

$\mathrm{DigitalPuzzle2}\left(6\right)$

((1 + (2 + 3) * 4 * 5) + 6) - 7 = 100
((1 - 2) + 3) + (4 * 5 - 6) * 7 = 100
(1 - 2 * 3) + ((4 + 5) + 6) * 7 = 100
1 * 2 * ((3 + (4 + 5) * 6) - 7) = 100
(1 + 2 * 3 * 4) * ((5 + 6) - 7) = 100
(1 - 2 * 3) * 4 * 5 * (6 - 7) = 100
(1 - 2 * 3) * 4 * 5 / (6 - 7) = 100

$7$