// 文字列式微分エンジン
// 1998 N.Inoue

public class Differentiate{
	/**
	 * 与えられた関数の導関数を返す
	 * @param str 関数
	 * @param c 文字
	 * @return 導関数
	 */
	public static String differentiate(String str, char c)
	{
		return replace(differentiate(replace(str, c, 'x')), 'x', c);
	}
	private static boolean isLowerAlpha(char c)
	{
		if((c >= 'a')&&(c <= 'z')) return true; else return false;
	}
	private static String replace(String str, char fc, char tc)
	{
		int strlen = str.length();
		StringBuffer strbuf = new StringBuffer(str);
		for(int i=0; i<strlen; i++)
			if(str.charAt(i) == fc)
				if((i == 0)||(!isLowerAlpha(str.charAt(i-1))))
					if((i == strlen-1)||(!isLowerAlpha(str.charAt(i+1))))
						strbuf.setCharAt(i, tc);
		return new String(strbuf);
	}
	
	/**
	 * 与えられたｘの関数の導関数を返す
	 * @param str ｘの関数
	 * @return 導関数
	 */
	public static String differentiate(String str)
	{
		//debug System.out.println("differantial in="+str); 
		int strlen = str.length();
		
		// 長さ０の文字列には０を返す
		if(strlen == 0) return "0";
		
		// 絶対値を含む文字列には???を返す
		if(str.indexOf('|') != -1) return "???";
		
		// 式を項に分解してkousubに渡す
		String result = "";
		String substr = "+";
		char buf;
		int strpos = 0;
		int kdepth = 0;
		for(strpos=0; strpos<strlen; strpos++)
		{
			buf = str.charAt(strpos);
			switch(buf)
			{
			  case '+': // fall through
			  case '-':
			  	if(kdepth == 0)
			  	{
				  	result = result + kousub(substr);
				  	substr = String.valueOf(buf);
				  	continue;
				}
				break;
			  case '(': kdepth++; break;
			  case ')': kdepth--; break;
			}
			substr = substr + buf;
		}
		result = result + kousub(substr);
		
		// ここで空文字列の場合は０にする
		if(result.length() == 0) result = "0";
		
		// 最初の符号が＋の場合は省略
		if(result.charAt(0) == '+') result = result.substring(1);
		
		//debug System.out.println("differantial out="+result);
		return result;
	}
	
	private static String kousub(String kou)
	{
		//debug System.out.println("kou in=" + kou);
		
		int strlen = kou.length();
		
		// 長さ０の項には空文字列を返す（未想定）
		if(strlen == 0) return "";
		
		// 定数項には空文字列を返す
		if(kou.indexOf('x') == -1) return "";
		
		// 項を分解してｘの式はpartsubに渡す
		String result;
		String substr = "*";
		String partslist[] = new String[20];
		String difpartslist[] = new String[20];
		char buf;
		int partsindex = 0;
		int strpos = 0;
		int kdepth = 0;
		double number;
		
		// １文字目には必ず符号が入っている
		if(kou.charAt(0) == '+')
			number = 1.0;
		else
			number = -1.0;
		for(strpos = 1; strpos<strlen; strpos++)
		{
			buf = kou.charAt(strpos);
			switch(buf)
			{
			  case '*': // fall through
			  case '/':
			  	if(kdepth == 0)
			  	{
			  		if(substr.indexOf('x') == -1)
			  		{
				  		// 係数部分は計算して別に保存する
			  			if(substr.charAt(0) == '*')
			  				number *= Calc.calc(substr.substring(1));
			  			else
			  				number /= Calc.calc(substr.substring(1));
			  		}
			  		else
			  		{
			  			// 関数部分は配列に保存する
			  			partslist[partsindex] = substr.charAt(0) + substr.substring(1);
			  			difpartslist[partsindex] = substr.charAt(0) + partsub(substr.substring(1));
			  			partsindex++;
				  	}
				  	substr = String.valueOf(buf);
				  	continue;
				}
				break;
			  case '(': kdepth++; break;
			  case ')': kdepth--; break;
			}
			substr = substr + buf;
		}
		if(substr.indexOf('x') == -1)
  		{
			if(substr.charAt(0) == '*')
				number *= Calc.calc(substr.substring(1));
			else
				number /= Calc.calc(substr.substring(1));
  		}
  		else
  		{
  			partslist[partsindex] = substr.charAt(0) + substr.substring(1);
  			difpartslist[partsindex] = substr.charAt(0) + partsub(substr.substring(1));
  			partsindex++;
	  	}
		
		//debug
		//for(int i=0; i<partsindex; i++)
		//{
		//	//debug System.out.println("   partslist["+i+"]: "+partslist[i]);
		//	//debug System.out.println("difpartslist["+i+"]: "+difpartslist[i]);
		//}
		
		// 積の微分の公式でそれぞれの部品を組み立てる
		if(partsindex == 1)
		{
			// 関数が１つだけの場合は微分したものに括弧をつけて返す
			if(difpartslist[0].charAt(0) == '/')
				substr = "((-" + difpartslist[0].substring(1) + ")/" + partslist[0].substring(1)+"^2)";
			else
				substr = "(" + difpartslist[0].substring(1) + ")";
		}
		else
		{
			// (abcd)' = (a'bcd + ab'cd + abc'd + abcd')
			substr = "(";
			for(int i = 0; i<partsindex; i++)
			{
				for(int j = 0; j<partsindex; j++)
				{
					String part;
					if(i == j)
					{
						if(difpartslist[j].charAt(0) == '/')
							part = "*(-" + difpartslist[j].substring(1) + ")/" + partslist[j].substring(1)+"^2";
						else
							part = difpartslist[j];
					}
					else
						part = partslist[j];
					if(j == 0)
						substr += part.substring(1);
					else
						substr += part;
				}
				// 最後でなければ＋でつなぐ
				if(i != partsindex-1) substr += "+";
			}
			substr += ")";
		}
		
		// 係数が１なら省略、符号を明示的につける
		if(number > 0)
		{
			if(number == 1.0)
				result = "+" + substr.substring(1, substr.length()-1);
			else
			{
				if(substr.equals("(1)"))
					result = "+" + number;
				else
					result = "+" + number + "*" + substr;
			}
		}
		else
		{
			if(number == -1.0)
				result = "-" + substr.substring(1, substr.length()-1);
			else
			{
				if(substr.equals("(1)"))
					result = String.valueOf(number);
				else
					result = number + "*" + substr;
			}
		}
		
		//debug System.out.println("kou out=" + result );
		
		return result;
	}
	
	private static String partsub(String part)
	{
		//debug System.out.println("part in=" + part);
		
		String result;
		String functionstr;
		String exponentstr;
		int strlen = part.length();
		int strpos = strlen;
		int kdepth = 0;
		
		// 渡された部分を指数部分とその他の部分に分割
		char chr;
		do
		{
			strpos--;
			if(strpos < 0) break;
			if((chr = part.charAt(strpos)) == ')') kdepth++;
			else if(chr == '(') kdepth--;
		}while ((chr != '^')||(kdepth != 0));
		
		if(strpos < 0)
		{
			exponentstr = "1";
			functionstr = part;
		}
		else
		{
			exponentstr = part.substring(strpos+1);
			functionstr = part.substring(0, strpos);
		}
		
		// 指数関数を微分して中の関数はfinalpartsubに渡す
		if(exponentstr.indexOf('x') == -1)
		{
			// a = f(x)
			// (a^n)' =a^(n-1) * n * a'
			int num;
			if((num = (int)Calc.calc(exponentstr)) == 1)
				result = finalpartsub(functionstr);
			else
			{
				if(num == 2)
					result = exponentstr + "*" + functionstr;
				else
					result = exponentstr + "*" + functionstr + "^(" + exponentstr + "-1)";
				String difstr = finalpartsub(functionstr);
				if(!difstr.equals("1"))
					result += "*" + difstr;
			}
		}
		else
		{
			// a = f(x), b = g(x)
			// (a^b)' = a^b * b' * log a + b * a^(b-1) * a'
			String difstr = finalpartsub(exponentstr);
			if(difstr.equals("1"))
				result = part + "*log(" + functionstr + ")";
			else
				result = part + "*" + difstr + "*log(" + functionstr + ")";
			if(functionstr.indexOf('x') != -1)
			{
				String difstr_b = finalpartsub(functionstr);
				result = "(" + result;
				if(difstr_b.equals("1"))
					result += "+" + exponentstr + "*" + functionstr + "^(" + exponentstr + "-1))";
				else
					result += "+" + exponentstr + "*" + functionstr + "^(" + exponentstr + "-1)*" + difstr_b + ")";
			}
		}
		
		//debug System.out.println("part out="+result);
		
		return result;
	}
	
	private static String finalpartsub(String finalpart)
	{
		// finalpartsubに渡されるのは単一の関数
		
		//debug System.out.println("finalpart in="+finalpart);
		
		// 特例 (x)' = 1
		if(finalpart.equals("x"))
		{
			//debug System.out.println("finalpart out=1");
			return "1";
		}
		
		String result;
		String argstr;
		String difstr;
		
		int strpos;
		int strlen = finalpart.length();
		int kdepth = 0;
		char chr;
		
		// 指数関数の場合はpartsubに渡す
		for(strpos = 0; strpos<strlen; strpos++)
		{
			if((chr = finalpart.charAt(strpos))=='(') kdepth++;
			else if(chr == ')') kdepth--;
			else if((kdepth == 0)&&(chr == '^'))
			{
				result = partsub(finalpart);
				//debug System.out.println("finalpart out="+result);
				return result;
			}
		}
		
		if((strpos = finalpart.indexOf('x')) == -1)
		{
			// 定数は０
			//debug System.out.println("finalpart out=0");
			return "0";
		}
		else
		{
			// 関数の引数を取り出して微分する
			argstr = getKakkoFrom(finalpart, finalpart.indexOf('('));
			difstr = differentiate(argstr);
			
			// 関数を微分する
			// 引数を微分したものが１なら省略
			if(finalpart.substring(0, 3).equals("sin"))
			{
				if(difstr.equals("1"))
					result = "cos(" + argstr + ")";
				else
					result = "cos(" + argstr + ")*(" + difstr + ")";
			}
			else if(finalpart.substring(0, 3).equals("cos"))
			{
				if(difstr.equals("1"))
					result = "(-sin(" + argstr + "))";
				else
					result = "(-sin(" + argstr + ")*(" + difstr + "))";
			}
			else if(finalpart.substring(0, 3).equals("tan"))
			{
				if(difstr.equals("1"))
					result = "1/cos(" + argstr + ")^2";
				else
					result = "(" + difstr + ")/cos(" + argstr + ")^2";
			}
			else if(finalpart.substring(0, 3).equals("log"))
			{
				if(difstr.equals("1"))
					result = "1/(" + argstr + ")";
				else
					result = "(" + difstr + ")/(" + argstr + ")";
			}
			else
			{
				if(difstr.equals("1"))
					result = "1";
				else
					result = "(" + difstr + ")";
			}
			//debug System.out.println("finalpart out="+result);
			return result;
		}
	}
	
	final private static String getKakkoFrom(String str, int startpos)
	{
		// 指定された位置にある括弧の中の文字列を返す
		int strpos = startpos;
		int kdepth = 1;
		char chr;
		// 指定された位置に括弧がない場合は文字列をそのまま返す
		if(str.charAt(startpos) != '(')
			return str;
		else do
		{
			strpos++;
			if((chr = str.charAt(strpos)) == '(')
				kdepth++;
			else if(chr == ')')
				kdepth--;
		}while(kdepth > 0);
		return str.substring(startpos+1, strpos);
	}

}