import java.io.*;
import java.util.*;
import java.util.regex.*;

/**
 * S式を取り扱うクラス
 * created by Toyohisa Nakada (2008.11.15)
*/
public class SExp {
	/** S式の個々の要素 */
	private Vector<Object> m_atoms = new Vector<Object>();

	/** デフォルトコンストラクタ */
	protected SExp() throws Exception{
	}
	/** コンストラクタ */
	public SExp(String expression) throws Exception{
		parse(expression);
	}
	/** S式の文字列表現 */
	public String toString(){
		String expression = "";
		for(int cnt=0;cnt<m_atoms.size();cnt++){
			if(expression.length()!=0){
				expression += " ";
			}
			expression += m_atoms.get(cnt).toString();
		}
		return "("+expression+")";
	}
	/** S式のツリー形式の文字列表現 */
	public String toTreeString(){
		return toTreeString("");
	}
	/** S式のツリー形式の文字表現で利用する内部関数。引数にインデント文字を指定する。 */
	private String toTreeString(String indent){
		String str = "";
		for(int cnt=0;cnt<m_atoms.size();cnt++){
			if(str.length()!=0){
				str += "\n";
			}
			if(m_atoms.get(cnt) instanceof SExp){
				str += ((SExp)m_atoms.get(cnt)).toTreeString(" "+indent);
			}else{
				str += (indent+m_atoms.get(cnt).toString());
			}
		}
		return str;
	}
	public Vector<SExp> findAll(String first_element) throws Exception{
		Vector<SExp> rets = new Vector<SExp>();
		findAll(first_element,this,rets);
		return rets;
	}
	private static void findAll(String first_element,SExp exp,Vector<SExp> rets) throws Exception{
		if(exp.get(0).toString().equals(first_element)){
			rets.add(exp);
		}
		for(int cnt=1;cnt<exp.size();cnt++){
			if(exp.get(cnt) instanceof SExp){
				findAll(first_element,(SExp)exp.get(cnt),rets);
			}
		}
		return;
	}
	/** 引数のPatternは、Pattern.compile(String)を使うとよい。 */
	public Vector<SExp> findAll(Pattern ptn) throws Exception{
		Vector<SExp> rets = new Vector<SExp>();
		findAll(ptn,this,rets);
		return rets;
	}
	public Vector<SExp> findAll(Object name) throws Exception{
		if(name instanceof Pattern){
			return findAll((Pattern)name);
		}else if(name instanceof String){
			return findAll((String)name);
		}
		throw new Exception("[SExp] could not find a type of input object");
	}
	/** 引数のPatternは、Pattern.compile(String)を使うとよい。 */
	private static void findAll(Pattern ptn,SExp exp,Vector<SExp> rets) throws Exception{
		Matcher m = ptn.matcher(exp.get(0).toString());
		if(m.matches()){
			rets.add(exp);
		}
		for(int cnt=1;cnt<exp.size();cnt++){
			if(exp.get(cnt) instanceof SExp){
				findAll(ptn,(SExp)exp.get(cnt),rets);
			}
		}
		return;
	}
	/** S式の最初のアトムを指定して検索を行う。最初のアトムとは、(a b c)の場合はaである。
	  * さらに((a b) c)をaで検索すると(a b)が返り、(a b)で検索すると((a b) c)が返る。
	  * 最初のアトムは、正規表現で指定する。
	  * 正規表現は、http://www.hellohiro.com/regex.htm がわかりやすい。*/
	public SExp find(Pattern ptn) throws Exception{
		return find(ptn,this);
	}
	public SExp find(String first_element) throws Exception{
		return find(first_element,this);
	}
	public SExp find(Object name) throws Exception{
		if(name instanceof Pattern){
			return find((Pattern)name);
		}else if(name instanceof String){
			return find((String)name);
		}
		throw new Exception("[SExp] could not find a type of input object");
	}
	/** S式からの検索 */
	private static SExp find(String str,SExp exp) throws Exception{
		if(str.equals(exp.get(0).toString())){
			return exp;
		}
		for(int cnt=1;cnt<exp.size();cnt++){
			if(exp.get(cnt) instanceof SExp){
				SExp exp_in = find(str,(SExp)exp.get(cnt));
				if(exp_in != null){
					return exp_in;
				}
			}
		}
		return null;
	}
	private static SExp find(Pattern ptn,SExp exp) throws Exception{
		Matcher m = ptn.matcher(exp.get(0).toString());
		if(m.matches()){
			return exp;
		}
		for(int cnt=1;cnt<exp.size();cnt++){
			if(exp.get(cnt) instanceof SExp){
				SExp exp_in = find(ptn,(SExp)exp.get(cnt));
				if(exp_in != null){
					return exp_in;
				}
			}
		}
		return null;
	}
	private int parse(String expression) throws Exception{
		byte[] bytes = expression.getBytes();
		int index = 0;
		for(;bytes.length!=index && bytes[index]!='(';index++);
		if(bytes.length == index){
			throw (new Exception("[SExp] could not find first bracket"));
		}
		for(index++;bytes[index]==' ';index++);
		int point0 = index;
		for(;bytes.length!=index && bytes[index]!=')';index++){
			if(bytes[index]==' '){
				if(point0 < index){
					m_atoms.add(expression.substring(point0,index));
				}
				for(index++;bytes.length!=index && bytes[index]==' ';index++);
				point0 = index;
				index--;
			}else if(bytes[index]=='('){
				SExp exp = new SExp();
				int prog_index = exp.parse(expression.substring(index));
				m_atoms.add(exp);
				index += prog_index;
				point0 = index+1;
			}
		}
		if(bytes.length==index){
			throw (new Exception("[SExp] could not find second bracket"));
		}
		if(point0 != index){
			m_atoms.add(expression.substring(point0,index));
		}
		return index;
	}
	public int size(){
		return m_atoms.size();
	}
	public Object get(int index) throws Exception {
		return m_atoms.get(index);
	}
	public static boolean isSExp(String str){
		try{
			SExp exp = new SExp(str);
			return true;
		}catch(Exception e){
		}
		return false;
	}
	public static void main(String[] args) throws Exception{
		/*
		String expression = args.length == 0 ?
			"(see 25 ((f c) 37.7 1 -0 0) ((f c t) 50.4 -42) ((f c b) 50.9 42) ((f r t) 96.5 -20) ((f r b) 96.5 21) ((f g r b) 90 5) ((g r) 90 0) ((f g r t) 90 -4) ((f p r b) 76.7 16) ((f p r c) 73.7 0) ((f p r t) 75.9 -15) ((f p l c) 1.6 13 -0.096 1.4) ((f t r 10) 61.6 -39) ((f t r 20) 69.4 -34) ((f t r 30) 77.5 -30) ((f t r 40) 86.5 -26) ((f t r 50) 95.6 -24) ((f b r 10) 61.6 40) ((f b r 20) 69.4 34) ((f b r 30) 78.3 30) ((f b r 40) 87.4 27) ((f b r 50) 95.6 24) ((f r 0) 94.6 0) ((f r t 10) 95.6 -6) ((f r t 20) 97.5 -12) ((f r t 30) 99.5 -17) ((f r b 10) 95.6 6) ((f r b 20) 97.5 12) ((f r b 30) 99.5 18) ((b) 36.6 1) ((p \"SamplePlayer0\" 3) 11 -25 0 0.1 0 0) ((p \"SamplePlayer0\" 4) 12.2 25 0 0.1 0 0) ((p) 81.5 0) ((p) 73.7 10) ((p) 73.7 4) ((p) 73.7 -3) ((l r) 90 90))":
			args[0];
		SExp exp = new SExp(expression);
		System.out.println(exp.toTreeString());
		System.out.println("------------");
		Vector<SExp> objs = exp.findAll("\\(p \"SamplePlayer0\".*");
		for(int cnt=0;cnt<objs.size();cnt++){
			System.out.println(objs.get(cnt));
		}
		/**/

		String str = "aaa";
		if(SExp.isSExp(str)==true){
			SExp exp = new SExp(str);
			System.out.println(exp.toString());
		}else{
			System.out.println("["+str+"] is not S expression");
		}
		/**/
	}
}