//
// University of California, Irvine
// School of Information and Computer Sciences
// Department of Informatics
//
// Informatics 102
// Autor: Crista Lopes
//


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Collection;
import java.util.Enumeration;
import java.util.Iterator;
import java.util.List;
import java.util.LinkedList;
import java.util.regex.Pattern;
import java.util.regex.Matcher;

class Interpreter {

    private static Object eval(String exp, Environment env) {
	Object ret = null;
	if (isSelfEvaluating(exp)) {
	    System.out.println("[DEBUG] >> isSelfEval? " + exp);
	    ret = literal(exp);
	    System.out.println("[DEBUG] << isSelfEval? " + ret);
	    return ret;
	}
	else if (isVariable(exp)) {
	    System.out.println("[DEBUG] >> isVariable? " + exp);
	    ret = env.lookupVariableValue(exp);
	    System.out.println("[DEBUG] << isVariable? " + ret);
	    return ret;
	}
	else if (isQuoted(exp)) {
	    System.out.println("[DEBUG] >> isQuoted? " + exp);
	    ret = textOfQuotation(exp);
	    System.out.println("[DEBUG] << isQuoted? " + ret);
	    return ret;
	}
	else if (isApplication(exp)) {
	    System.out.println("[DEBUG] >> isApplication? " + exp);
	    ret = apply(eval(operator(exp), env), 
			 listOfValues(operands(exp), env));
	    System.out.println("[DEBUG] << isApplication? " + ret);
	    return ret;
	}
	
	System.out.println("[DEBUG] OUT eval: unrecognized expression type");
	return "ok";
    }

    private static final String inputPrompt  = "Eval>>";
    private static final String outputPrompt = "Value>>";

    /**
     * SELF-EVALUATING Expressions
     */
    private static boolean isSelfEvaluating(String exp) {

	try {
	    int number = Integer.parseInt(exp);
	    return true;
	}
	catch (NumberFormatException e) {
	    if (exp.startsWith("\"") && exp.endsWith("\"")) 
		return true;
	}
	return false;
    }

    // Basic types in Scheme: list, symbol, string, and number
    private static Object literal(String exp) {
	Object lit = null;
	if (exp.startsWith("\'")) {// a quoted value
	    if (exp.length() > 1 && exp.substring(1).startsWith("(")) // a list
		lit = new SchList(exp.substring(1));
	    else // a symbol
		lit = new SchSymbol(exp.substring(1));
	}
	else if (exp.startsWith("\"")) // a string
	    lit = new SchString(exp.substring(1, exp.length()-1));
	else // must be a number
	    try {
		int number = Integer.parseInt(exp);
		lit = new SchNumber(number);
	    } catch (NumberFormatException e) {
		throw new InterpreterException("Internal interpreter error on literal");
	    }
	return lit;
    }

    private static boolean isQuoted(String exp) { 
	if (exp.startsWith("\'") || exp.startsWith("(quote"))
	    return true;
	else
	    return false;
    }

    private static Object textOfQuotation(String exp) {
	if (exp.startsWith("\'"))
	    return literal(exp);
	else { // (quote a)
	    ArrayList<String> parts = split(exp);
	    if (parts.size() <=1)
		return null;
	    else
		return literal("\'" + parts.get(1));
	}	    
    }

    /**
     * VARIABLES
     */
    private static boolean isVariable(String exp) {
	//	return exp.startsWith("\\w");
	return exp.matches("\\w+");
    }

    /**
     * APPLY 
     */
    private static boolean isApplication(String exp) {
	if (exp.startsWith("(") && exp.endsWith(")"))
	    return true;
	return false;
    }

    private static String operator(String exp) {
	exp = exp.substring(1, exp.length()-1);
	String[] parts = exp.split("\\s+");
	if (parts.length == 0)
	    throw new InterpreterException("Application without operator");
	else {
	    return parts[0];
	}
    }

    private static String[] operands(String exp) {
	//	System.out.println("[DEBUG] IN operands for " + exp);
	ArrayList<String> parts = split(exp);

	String[] operandsArray = new String[parts.size()-1];
	for (int i = 1; i < parts.size(); i++) {
	    //	    System.out.print("\t" + parts.get(i) + "; ");
	    operandsArray[i-1] = parts.get(i);
	}
	
	return operandsArray;
    }

    // Split takes a list and returns its top-level constituents
    // For example: (car '(a b c)) --> [car, '(a b c)]
    //              (if (...) (ttt) (fff)) --> [if, (...), (ttt), (fff)]
    static ArrayList<String> split(String exp) {
   
	ArrayList<String> parts = new ArrayList<String>();
	// Let's get rid of the enclosing parenthesis
	exp = exp.substring(1, exp.length()-1);
	while (exp.length() > 0) {
	    int i = 0;
	    // skip over spaces
	    while (exp.charAt(i) == ' ')
		i++;
	    exp = exp.substring(i);
	    int nchars = scan(exp);
	    parts.add(exp.substring(0, nchars));
	    exp = exp.substring(nchars);
	}
	return parts;
    }

    static int scan(String exp) {
	String part = null;
	int nchars = 0;

	if (exp.startsWith("("))
	    nchars = scanList(exp);
	else if (exp.startsWith("\'"))
	    nchars = scan(exp.substring(1)) + 1;
	else  // must be a word
	    if ((nchars = exp.indexOf(" ")) == -1) // end of string
		nchars = exp.length();

	return nchars;
    }

    static int scanList(String exp) {
	int counter = 1, i = 0;
	for (i = 1; i < exp.length() && counter > 0; i++) {
	    if (exp.charAt(i) == '(')
		counter++;
	    else if (exp.charAt(i) == ')')
		counter--;
	}
	return i;
    }

    private static Object[] listOfValues(String[] exps, Environment env) {
	//	System.out.println("[DEBUG] listOfValues: " + exps);
	Object[] values = new Object[exps.length];
	for (int i = 0; i < exps.length; i++) {
	    values[i] = eval(exps[i], env);
	}
	return values;
    }

    private static Object apply(Object proc, Object[] arguments) {
	System.out.println("[DEBUG] \tapply: proc=" + proc.toString());
	if (!(proc instanceof Procedure))
	    throw new InterpreterException("Can't apply non-procedure");
	Object ret = null;
	if (isPrimitiveProcedure(proc)) 
	    ret = applyPrimitiveProcedure((Procedure)proc, arguments);
	else {
	    System.out.println("Compound procedure not implemented yet");
	}
	return ret;
    }


    private static boolean isPrimitiveProcedure(Object proc) {
	if (proc instanceof PrimitiveProcedure)
	    return true;
	else return false;
    }

    private static Object applyPrimitiveProcedure(Procedure proc, Object[] arguments) {
	return proc.procedure(arguments);

    }

    /**
     *
     *    ------ PRIMITIVE PROCEDURES ------
     * 
     * The primitive procedures of this language
     *
     */
    private static Hashtable<String, Procedure> primitiveProcedures = new Hashtable<String, Procedure>();
    
    private static List<String> primitiveProcedureNames() {
	List<String> namelist = new LinkedList<String>();
	Enumeration<String> keys =  primitiveProcedures.keys();
	while (keys.hasMoreElements()) {
	    String name = keys.nextElement();
	    namelist.add(name);
	}
	return namelist;
    }

    private static List<Procedure> primitiveProcedureObjects() {
	List<Procedure> procs = new LinkedList<Procedure>();
	Collection<Procedure> values = primitiveProcedures.values();
	Iterator<Procedure> iter = values.iterator();
	while (iter.hasNext()) {
	    procs.add(iter.next());
	}

	return procs;
    }

    private static Procedure Car = new CarImplementation();

    /**
     *
     *    ------ ENVIRONMENT ------
     *
     * Functions and utilities pertaining to the Environment and its management by the iterpreter
     */
    private static class Environment {

	private Environment _baseEnv = null;
	// This variable is called "frame" to keep somewhat in sync with the original interpreter
	// In reality, the data structures used here and in the SICP book are quite different
	private Hashtable   frame = new Hashtable();

	Environment() {
	}

	Environment(List vars, List values, Environment baseEnv) {
	    _baseEnv = baseEnv;
	    // place vars/vals in an Hashtable
	    for (int i = 0; i < vars.size(); i++)
		frame.put(vars.get(i), values.get(i));
	}

	Environment extendEnvironment(List vars, List values)  {
	    if (vars.size() == values.size()) {
		return new Environment(vars, values, this);
	    }
	    else if (vars.size() > values.size())
		throw new InterpreterException("Too many variables supplied");
	    else
		throw new InterpreterException("Too many values supplied");
	}

	void defineVariable(String name, Object value) {
	    // add the pair name/value to the hashtable, or change its value
	    frame.put(name, value);
	}

	Object lookupVariableValue(String exp) {
	    System.out.println("[DEBUG] \tlookupVariableValue: exp=" + exp);
	    if (this.equals(theEmptyEnvironment))
		throw new InterpreterException("Unbound variable " + exp);
	    else {
		Object value = frame.get(exp);
		if (value == null)
		    value = _baseEnv.lookupVariableValue(exp);
		return value;
	    }
	}

    }

    private static final Environment theEmptyEnvironment = new Environment();
    private static Environment theGlobalEnvironment;

    private static Environment setupEnvironment()  {
	Environment initialEnv = theEmptyEnvironment.extendEnvironment(primitiveProcedureNames(), primitiveProcedureObjects());
	initialEnv.defineVariable("true",  true);
	initialEnv.defineVariable("false", false);
	return initialEnv;
    }


    private static void setPrimitiveProcedures() {
	primitiveProcedures.put("car", Car);
    }


    private static void promptForInput(String prompt) {
	System.out.print(prompt);
	System.out.flush();
    }

    private static void announceOutput(String prompt, Object output) {
	System.out.println(prompt + output.toString());
    }

    private static void driverLoop() {
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	String input = "";
	boolean running = true;
	while (running) {
	    promptForInput(inputPrompt);
	    try {
		input = in.readLine().trim(); 
	    } catch (IOException e) {
		System.out.println("Exception reading stdin");
	    }
	    if ("stop".equals(input))
		running = false;
	    Object output = eval(input, theGlobalEnvironment);
	    announceOutput(outputPrompt, output);	    
	}
    }

    public static void main(String[] args) {
	setPrimitiveProcedures();
	theGlobalEnvironment = setupEnvironment();
	driverLoop();
    }
}


//----------------------------------

class InterpreterException extends RuntimeException {
    InterpreterException(String msg) {
	super(msg);
    }
}

/**
 * TYPE SYSTEM
 */
class SchList extends LinkedList {

    SchList(String elements) {
	elements = elements.substring(1, elements.length()-1);
	String[] parts = elements.split("\\s+");
	for (int i = 0; i < parts.length; i++)
	    super.add(parts[i]);
    }
}

class SchSymbol {
    String value = null;
    SchSymbol(String val) {
	value = val;
    }

    public String toString() {
	return value;
    }
}

class SchString {
    String value = null;
    SchString(String val) {
	value = val;
    }

    public String toString() {
	return value;
    }
}

class SchNumber {
    int value = 0;
    SchNumber(int val) {
	value = val;
    }

    public String toString() {
	return Integer.toString(value);
    }
}

class Lambda {
    String[] parameters;
    String body;

    Lambda(String params, String body) {
	// To Be Implemented by you
	// Note that this takes a string of params, so you have to split them
    }

    public String toString() {
	return "(lambda (" + parameters + ")\n" + body;
    }
}

interface Procedure {
    Object procedure(Object[] params);
}

interface PrimitiveProcedure extends Procedure {}

class CarImplementation implements PrimitiveProcedure {
    public Object procedure(Object[] params) {
	if (params.length == 0)
	    throw new InterpreterException("Can't car empty list");
	else {
	    if (params[0] instanceof SchList)
		return ((SchList)params[0]).get(0);
	    else
		throw new InterpreterException("car requires a list parameter");		
	}
    }
}