import java.util.ArrayList;
import java.util.List;

public class AST {
  private final List<AST> children = new ArrayList<>();
  private final String token;

  public AST(String token) {
    this.token = token;
  }

  public void add(AST child) {
    children.add(child);
  }

  public String token() {
    return token;
  }

  public Double numValue() {
    return Double.parseDouble(token);
  }

  public boolean boolValue() {
    if (token.equals("true") || token.equals("false"))
      return Boolean.parseBoolean(token);
    else
      throw new IllegalArgumentException("not a boolean: " + token());
  }

  public boolean isAtom() {
    return children.isEmpty();
  }

  public AST head() {
    return children.get(0);
  }

  public List<AST> tail() {
    return children.subList(1, children.size());
  }

  public int size() {
    return children.size();
  }

  public AST at(int i) {
    return children.get(i);
  }

  @Override
  public String toString() {
    return isAtom() ? token : children.toString();
  }
}
//////////
import java.util.HashMap;
import java.util.Map;

public class Environment {
  private final Map<String, Object> vars = new HashMap<>();
  private final Environment parent;

  public Environment(Environment parent) {
    this.parent = parent;
  }

  public Object put(String key, Object value) {
    return vars.put(key, value);
  }

  public Object at(String key) {
    if (vars.containsKey(key))
      return vars.get(key);
    else if (parent != null)
      return parent.at(key);
    else
      return null;
  }
}
//////////
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import static java.util.stream.Collectors.toList;

public class Interpreter {
  private final Map<String, SpecialForm> specialForms = new HashMap<>();
  private final Environment environment = new Environment(null);

  public interface Func {
    Object call(List<Object> parameters);
  }

  public interface SpecialForm {
    Object call(Environment env, List<AST> parameters);
  }

  public Interpreter() {
    addSpecialForm("lambda", this::lambda);
    addSpecialForm("or", (env, args) -> args.stream().anyMatch(each -> (boolean)eval(env, each)));
    addSpecialForm("and", (env, args) -> args.stream().allMatch(each -> (boolean)eval(env, each)));
    addSpecialForm("if", (env, args) -> (boolean) eval(env, args.get(0))
              ? eval(env, args.get(1))
              : (args.size() > 2 ? eval(env, args.get(2)) : null));
    addSpecialForm("define", (env, args) -> env.put(args.get(0).token(), eval(env, args.get(1))));
    environment.put("=", (Func) args -> args.get(0).equals(args.get(1)));
    environment.put("+", (Func) args -> (Double) args.get(0) + (Double) args.get(1));
    environment.put("-", (Func) args -> (Double) args.get(0) - (Double) args.get(1));
    environment.put("*", (Func) args -> (Double) args.get(0) * (Double) args.get(1));
    environment.put("/", (Func) args -> (Double) args.get(0) / (Double) args.get(1));
    environment.put("not", (Func) args -> !(boolean) args.get(0));
  }

  private Object lambda(Environment parent, List<AST> lambda) {
    AST paramNames = lambda.get(0);
    AST lambdaBody = lambda.get(1);
    return (Func) arguments -> {
      Environment env = new Environment(parent);
      for (int i = 0; i < paramNames.size(); i++)
        env.put(paramNames.at(i).token(), arguments.get(i));
      return eval(env, lambdaBody);
    };
  }

  public void addSpecialForm(String name, SpecialForm func) {
    specialForms.put(name, func);
  }

  public Object eval(AST ast) {
    return eval(environment, ast);
  }

  private Object eval(Environment env, AST ast) {
    if (ast.isAtom())
      return evalAtom(env, ast);
    SpecialForm specialForm = specialForms.get(ast.head().token());
    if (specialForm != null)
      return specialForm.call(env, ast.tail());
    Func func = (Func) eval(env, ast.head());
    return func.call(ast.tail().stream().map(a -> eval(env, a)).collect(toList()));
  }

  private static Object evalAtom(Environment env, AST ast) {
    try {
      return ast.numValue();
    } catch (NumberFormatException e) {
      try {
        return ast.boolValue();
      } catch (IllegalArgumentException ie) {
        return env.at(ast.token());
      }
    }
  }
}
/////////
import java.io.IOException;
import java.io.PushbackReader;
import java.io.StringReader;

public class Parser {
  public AST parse(String str) throws IOException {
    try (PushbackReader reader = new PushbackReader(new StringReader(str))) {
      AST ast = parse(reader);
      String rest = peek(reader);
      if (rest != null)
        throw new RuntimeException("Unexpected tokens: " + rest);
      return ast;
    }
  }

  private AST parse(PushbackReader reader) throws IOException {
    String token = nextToken(reader);
    if (")".equals(token) || "".equals(token))
      throw new RuntimeException("Unbalanced parenthesis");
    if ("(".equals(token)) {
      AST list = new AST(token);
      while (!")".equals(peek(reader)))
        list.add(parse(reader));
      nextToken(reader); // skip )
      return list;
    }
    return new AST(token); // atom
  }

  private String nextToken(PushbackReader reader) throws IOException {
    String chr = peek(reader);
    return "(".equals(chr) || ")".equals(chr)
            ? String.valueOf((char) reader.read())
            : nextAtom(reader);
  }

  private String nextAtom(PushbackReader reader) throws IOException {
    StringBuilder buffer = new StringBuilder();
    int chr = reader.read();
    while (chr != -1 && !Character.isWhitespace(chr) && ')' != chr) {
      buffer.append((char)chr);
      chr = reader.read();
    }
    if (chr == ')')
      reader.unread(')');
    return buffer.toString();
  }

  private String peek(PushbackReader reader) throws IOException {
    int chr = reader.read();
    while (chr != -1 && Character.isWhitespace(chr))
      chr = reader.read();
    if (chr == -1)
      return null;
    reader.unread(chr);
    return String.valueOf((char) chr);
  }
}