Exp Exp /|\ /|\ / | \ / | \ Exp * Exp Exp * Exp /|\ | | /|\ / | \ | | / | \ Exp * Exp Num Num Exp * Exp | | | | | | | | | | | | Num Num 4 2 Num Num | | | | | | | | 2 3 3 4An example of the second is:
Exp Exp /|\ /|\ / | \ / | \ Exp ^ Num Exp * Exp /|\ | | /|\ / | \ | | / | \ Exp * Exp 4 Num Exp ^ Num | | | | | | | | | | Num Num 2 Num 4 | | | | | | 2 3 3
Exp ::= Exp * A | A A ::= A ^ Num | Num | (Exp) Num ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
class Merge extends Thread{ private Queue q1,q2,q3; //Input queues and output queue public Merge(Queue p1, Queue p2, Queue p3){ q1 = p1; q2 = p2; q3 = p3; } public void run() { for(;;){ boolAndInt x; x = q1.pop(); if (x.getBool()) q3.insert(x.getInt()); x = q2.pop(); if (x.getBool()) q3.insert(x.getInt()); } } } class Queue { private class Element{ public int info; public Element next; public Element(int n,Element e){ info = n; next = e; } } private Element first, last; public Queue() { first = last = null; } public synchronized boolAndInt pop() { boolAndInt x = new boolAndInt(); if (first == null) { x.setBool(false); x.setInt(0); return x; } else { x.setBool(true); x.setInt(first.info); first = first.next; if (first==null) last = null; return x; } } public synchronized void insert(int n) { if (first == null) last = first = new Element(n,null); else last = last.next = new Element(n,null); } } class boolAndInt { private int n; private boolean b; public int getInt() { return n; } public boolean getBool() { return b; } public void setInt(int k) { n = k; } public void setBool(boolean c) { b = c; } }
fun exists L p = reduce (fn (x,y) => p(x) orelse y) false L; fun forall L p = reduce (fn (x,y) => p(x) andalso y) true L;
fun aux [] = [] | aux (leaf x :: L) = x :: aux L | aux (node(t1,x,t2)::L) = x :: aux(L @ [t1,t2]); fun bftrav t = aux [t]; (* returns the breadth-first traversal of t *)Let us now solve the intended problem. We will use an auxiliary function split which returns the last two elements of a list, and the rest of the list.
fun split [x1,x2] = ([],x1,x2) | split (x :: L) = let val (K,x1,x2) = split L in (x::K,x1,x2) end; fun auxil [] n = [] | auxil (leaf x :: L) n = leaf n :: auxil L (n+1) | auxil (node(t1,x,t2) :: L) n = let val (K,u1,u2) = split (auxil (L @ [t1,t2]) (n+1)) in node(u1,n,u2) :: K end; fun enumerate t = hd (auxil [t] 1);
fun numnodes(t,1) = 1 | numnodes(leaf x,n) = 0 | numnodes(node(t1,x,t2),n) = numnodes(t1,n-1) + numnodes(t2,n-1);
solutions(M,N,X,Y) :- nat(X,M), nat(Y,M), M is X + Y, N is X * Y. nat(X,M) :- M >=0, X is M. /* gives all possible integers between 0 and M */ nat(X,M) :- M > 0, N is M - 1, nat(X,N).
flatten([],[]). flatten([X|L],[X|K]) :- not(list(X)), flatten(L,K). flatten([X|L],K) :- list(X), flatten(X,K1), flatten(L,K2), append(K1,K2,K). list([]). list([_|_]).
merge([],L,L). merge(L,[],L). merge([X|L],[Y|K],[X|M]) :- merge(L,[Y|K],M). merge([X|L],[Y|K],[Y|M]) :- merge([X|L],K,M).