// Programmed by Dag Langmyhr (dag(a)ifi.uio.no) // for the 2002 Nordic ACM programming contest. import java.io.*; class Scanner { public char sy; private BufferedReader f; private static final boolean debug = false; public Scanner () throws IOException { f = new BufferedReader(new InputStreamReader(System.in)); next(); } public void next () { try { do { int c = f.read(); sy = c<0 ? '?' : (char)c; } while (sy!='(' && sy!=')' && sy!='.' && sy!='?' && ! Character.isLetter(sy)); } catch (IOException e) { System.err.println("Read error!"); System.exit(1); } if (debug) System.err.println("DEBUG> Scanner: sy='" + sy + "'"); } public void test (char c) { if (sy == c) return; System.err.println("A '" + c + "' was expected; a '" + sy + "' was found."); System.exit(2); } } abstract class Expression { private static final boolean debug = false; public static final int maxCycles = 1000; public static int cycles; public boolean lastExpr () { return false; } public Expression eval () { if (debug) { System.err.print("DEBUG> "); print(System.err); System.err.println(" evaluates to itself."); } return this; } public abstract void print (PrintStream p); public static Expression read (Scanner s) { if (s.sy == 'L') return Lambda.read(s); if (s.sy == '(') return FuncCall.read(s); return Variable.read(s); } public Expression replace (char v, Expression e) { return this; } } class Undefined extends Expression { public void print (PrintStream p) { p.print("unterminated"); } } class Variable extends Expression { char var; public Variable (char v) { var = v; } public boolean lastExpr () { return var == 'z'; } public void print (PrintStream p) { p.print(var); } public static Expression read (Scanner s) { char v = s.sy; s.next(); return new Variable(v); } public Expression replace (char v, Expression e) { return var==v ? e : this; } } class Lambda extends Expression { char var; Expression expr; private static final boolean debug = false; public Lambda (char v, Expression e) { var = v; expr = e; } public void print (PrintStream p) { p.print("L" + var + "."); expr.print(p); } public static Expression read (Scanner s) { s.next(); char v = s.sy; s.next(); s.test('.'); s.next(); Expression e = Expression.read(s); return new Lambda(v,e); } public Expression replace (char v, Expression e) { Expression r = var==v ? this : new Lambda(var,expr.replace(v,e)); if (debug) { System.err.print("DEBUG> Replacing " + v + " with "); e.print(System.err); System.err.print(" in "); print(System.err); System.err.print(" gives "); r.print(System.err); System.err.println(); } return r; } public static void main (String arg[]) throws Exception { Scanner s = new Scanner(); while (true) { Expression e = Expression.read(s); if (debug) { System.err.print("DEBUG> Read "); e.print(System.err); System.err.println(); } cycles = 0; e.eval().print(System.out); System.out.println(); if (debug) { System.err.println("DEBUG> Evaluation used " + cycles + " cycles."); } if (e.lastExpr()) break; } } } class FuncCall extends Expression { Expression func, param; private static final boolean debug = false; public FuncCall (Expression f, Expression p) { func = f; param = p; } public Expression eval () { if (++cycles > maxCycles) return new Undefined(); Expression f = func.eval(), p = param.eval(), res; if (f instanceof Lambda) { Lambda l = (Lambda)f; res = l.expr.replace(l.var,p).eval(); } else { res = new FuncCall(f,p); } if (debug) { System.err.print("DEBUG> "); new FuncCall(f,p).print(System.err); System.err.print(" evaluates to "); res.print(System.err); System.err.println(" after " + cycles + " cycles."); } return res; } public void print (PrintStream p) { p.print("("); func.print(p); p.print(")"); param.print(p); } public static Expression read (Scanner s) { s.next(); Expression f = Expression.read(s); s.test(')'); s.next(); Expression p = Expression.read(s); return new FuncCall(f,p); } public Expression replace (char v, Expression e) { return new FuncCall(func.replace(v,e),param.replace(v,e)); } }