eva0919/Simplize_Ocaml.md

## Simplize_Ocaml.md

      
    Raw
  

              Simplize_Ocaml.md
            
          
    解說Simplize的ocaml版本


使用方法

開啟Ocaml 

複製下面的code

接著輸入 

startSimplize 字串

即可處理

ex

# startSimplize "x+y+2*3+2x+x^2+y^2";;
- : string = "x^2+3x+y^2+y+6"


## Simplize_Ocaml.ml
type bitree = Leaf of int array | Node of string * bitree * bitree | Empty
exception Oops
exception WrongType

(*Julia's code*)


let left = function Node (x, y, z) -> y
let right = function Node (x, y, z) -> z
(* let getVal a = match a with
	Node (x, y, z) -> x
	| Leaf (w) -> w *)
let getType a = match a with
	"+" -> "operator"
	| "-" -> "operator"
	| "*" -> "operator"
	| "/" -> "operator"
	| "^" -> "power"
	| "(" -> "parenthese"
	| ")" -> "parenthese"
	| _ -> try if int_of_string a = 123 then "number"
			   else "number" with Failure "int_of_string" -> "variable"	(* include both single variable ex. x, y AND compound variable ex. x^2, y^3 *)


let explode s =
  let rec exp i l t c =
    if i < 0 then
    	if t = "" then l
    	else if c = true then t::l
    	else t :: "*" :: l
    else if (Char.escaped s.[i]) = " " then exp (i - 1) l t c
	else if getType (Char.escaped s.[i]) = "operator" then
		if t = "" then exp (i - 1) ((Char.escaped s.[i]) :: l) "" true
		else if c = true then exp (i - 1) ((Char.escaped s.[i]) :: (t :: l)) "" true
			 else exp (i - 1) ((Char.escaped s.[i]) :: t :: "*" :: l) "" true
 	else if getType (Char.escaped s.[i]) = "parenthese" then
		if (Char.escaped s.[i]) = ")" then
			if c = true then
				if t = "" then exp (i - 1) ((Char.escaped s.[i]) :: l) "" true
				else exp (i - 1) ((Char.escaped s.[i]) :: "*" :: t :: l) "" true
			else if t = "" then exp (i - 1) ((Char.escaped s.[i]) :: "*" :: l) "" true
				else exp (i - 1) ( (Char.escaped s.[i]) :: "*" :: t :: "*" :: l ) "" true
		else if List.hd l = "(" || List.hd l = ")" then exp (i - 1) ((Char.escaped s.[i]) :: l) "" false (* for "(("或"))"的狀況 *)
			else if t != "" then
				if c = true then exp (i - 1) ( (Char.escaped s.[i]) :: t :: l ) "" false
				else exp (i - 1) ( (Char.escaped s.[i]) :: t :: "*" :: l ) "" false
			else exp (i - 1) ((Char.escaped s.[i]) :: l) "" false
	else if getType (Char.escaped s.[i]) = "variable" then
		if c = true then
			if t = "" then exp (i - 1) ((Char.escaped s.[i]) :: l) "" false
			else exp (i - 1) ((Char.escaped s.[i]) :: "*" :: t :: l) "" false
		else if t = "" then exp (i - 1) ((Char.escaped s.[i]) :: "*" :: l) "" false
			else exp (i - 1) ( (Char.escaped s.[i]) :: "*" :: t :: "*" :: l ) "" false
	else if getType (Char.escaped s.[i]) = "power" then
		if c = true then
			if t = "" then 	exp (i - 2) ( ( (Char.escaped s.[i-1])^(Char.escaped s.[i])^(Char.escaped s.[i+1]) ) :: (List.rev (List.tl (List.rev l))) ) "" false
			else exp (i - 2) ( ( (Char.escaped s.[i-1])^(Char.escaped s.[i])^t ) :: l ) "" false
		else if t = "" then exp (i - 2) ( ( (Char.escaped s.[i-1])^(Char.escaped s.[i])^(Char.escaped s.[i+1]) ) :: (List.rev (List.tl (List.rev l))) ) "" false
			 else exp (i - 2) ( ( (Char.escaped s.[i-1])^(Char.escaped s.[i])^t ):: "*" :: l ) "" false
	else exp (i - 1) l ((Char.escaped s.[i])^t) c in
  exp (String.length s - 1) [] "" true


(* 遇到＋、-時考慮有沒有被壓在下面且沒有用括號隔開的*、/，有則移到result的stack *)
let rec s1ToPlusOrMinus s =
	if s = [] then []
    else match (List.hd s) with
	  "+" -> s
	| "-" -> s
	| ")" -> s
	| _ -> s1ToPlusOrMinus (List.tl s)
let resultToPlusOrMinus inputS1 inputResult =
  let rec resultToPlusOrMinusDetail (s:string list) (result:string list) =
    if s = [] then result
    else match (List.hd s) with
	  "+" -> result
	| "-" -> result
	| ")" -> result
	| _ -> resultToPlusOrMinusDetail (List.tl s) ((List.hd s)::result) in
(resultToPlusOrMinusDetail inputS1 [])@inputResult
(* ******************************************************************* *)

(* 遇到右括號直接放入stack，但遇到左括號的時候，要將operator stack（s1)中，在右括號之前的東西都pop出來 *)
let rec s1ToLeftParenthesis s =
	if s = [] then []
    else match (List.hd s) with
	  ")" -> List.tl s
	| _ -> s1ToLeftParenthesis (List.tl s)
let resultToLeftParenthesis inputS1 inputResult =
  let rec resultToLeftParenthesisDetail (s:string list) (result:string list) =
	if s = [] then result
    else match (List.hd s) with
	  ")" -> result
	| _ -> resultToLeftParenthesisDetail (List.tl s) ((List.hd s)::result) in
(resultToLeftParenthesisDetail inputS1 [])@inputResult
(* **************************************************************************************** *)

(* 主要function，revstr為使用者輸入的字串轉為string list後reverse後的結果；s1為operator（暫存）；result為最後要輸出的結果 *)
(* stack遇到*/)時直接放入s1，遇到+-時要考慮是不是有在s1中的*/被壓在下面，遇到(時要將)之前的operator pop出來 *)
let rec infixToPrefixDetail (revstr:string list) (s1:string list) (result:string list) =
	match revstr with
	  [] -> (List.rev s1)@result
	| x::y -> if x = "*" || x = "/" || x = ")" then infixToPrefixDetail y (x::s1) result
			  else if x = "+" || x = "-" then infixToPrefixDetail y (x::(s1ToPlusOrMinus s1)) (resultToPlusOrMinus s1 result)
			       else if x = "(" then infixToPrefixDetail y (s1ToLeftParenthesis s1) (resultToLeftParenthesis s1 result)
			       	    else infixToPrefixDetail y s1 (x::result)

(* 以 infixToPrefix "a*(b+c*(d+e))+f" 這樣的方式，可以將infix轉為prefix *)
let infixToPrefix input = infixToPrefixDetail (List.rev (explode input)) [] []


(* ****************************************** *)
(* hw8 start *)

(* let tempVariableIndex = [|"constant";"x";"y"|] *)

(* let tempVariableIndex = Array.of_list (List.rev tempList) *)

let variableIndex variable variableArray =
	let rec variableIndexDetail variable index variableArray =
		if index >= (Array.length variableArray) then -1
		else if variable = variableArray.(index) then index
		else variableIndexDetail variable (index+1) variableArray in
	variableIndexDetail variable 0 variableArray

exception Oops2


(* convert a variable (x, x^2, etc.) into array ( [|1,1,0|], [|1,2,0|], etc. *)
let convertToLeaf input variableArray =
	let tempArray = Array.make (Array.length variableArray) 0 in
	(* let convertToLeafDetail input tempArray finished =  *)
		(* if finished then tempArray *)
		if String.contains input '^' then
			let indexOfVariable = variableIndex (String.sub input 0 (String.index input '^')) variableArray in
			if indexOfVariable != -1 && (Array.set tempArray 0 1) = () && (Array.set tempArray indexOfVariable (int_of_string (String.sub input ((String.index input '^')+1) ((String.length input)-(String.index input '^')-1)))) = () then tempArray
			else raise Oops
		else if getType input = "variable" && (Array.set tempArray 0 1) = () && (Array.set tempArray (variableIndex input variableArray) 1) = () then tempArray
		else if (Array.set tempArray 0 (int_of_string input)) = () then tempArray
		else raise Oops
	(* convertToLeafDetail input (Array.make (Array.length tempVariableIndex) 0) false *)


(* let addTreeValue aTree a = match a with *)
let rec isLeft aTree = match aTree with
	Empty -> true
	| Leaf (w) -> false
	| Node (x, y ,z) -> isLeft y || isRight y
	and isRight aTree = match aTree with
	Empty -> true
	| Leaf (w) -> false
	| Node (x, y ,z) -> isLeft z || isRight z
let rec insertOperator aTree x = match aTree with
	Empty -> Node(x, Empty, Empty)
	| Node(a, l, r) -> if isLeft aTree then Node(a, (insertOperator l x), r)
					   else if isRight aTree then Node(a, l, (insertOperator r x))
					   else raise Oops
	| Leaf(a) -> raise Oops
let rec insertNumber aTree x variableArray = match aTree with
	Empty -> Leaf( convertToLeaf x variableArray )
	| Node(a, l, r) -> if isLeft aTree then Node(a, (insertNumber l x variableArray), r)
					   else if isRight aTree then Node(a, l, (insertNumber r x variableArray))
					   else raise Oops
	| Leaf(a) -> raise Oops


(* 製造variable list *)
(* 確認這個variable是否已應在variable list裡面了 *)
let rec meetVariableBefore input templist =
	match templist with
		[] ->  false
		| a::y -> if a = input then true
				  else meetVariableBefore input y
(* 確認該variable是否已在variable list中，如果不在則加到variable list並回傳list，若已在其中則直接回傳原本的list *)
let addVariableToList input tempList=
	if meetVariableBefore input tempList = false then input::tempList
	else tempList

(* 將inputList（在此為使用者輸入後經explode過的東西）中為variable的部份做檢視，若未出現過則加入variable list中，最後回傳新增過後的list *)
let rec makeVariableList inputList tempList =
	match inputList with
		[] -> tempList
		| a::y -> if getType a = "variable" then if String.contains a '^' then makeVariableList y (addVariableToList (String.sub a 0 (String.index a '^')) tempList)
												 else makeVariableList y (addVariableToList a tempList)
				  else makeVariableList y tempList

(* 將inputList（在此為使用者輸入後經explode過的東西）中為variable的部份做檢視，若未出現過則加入variable list中，最後回傳新增過後的variable Array *)
let makeVariableArray inputList tempList = (Array.of_list (List.rev (makeVariableList inputList tempList)))


let rec formAbstractTreeDetail aList ansTree variableArray = match aList with
	[] -> ansTree
	| x::y -> if getType x = "number" || getType x = "variable" then formAbstractTreeDetail y (insertNumber ansTree x variableArray) variableArray
			  else if getType x = "operator" then formAbstractTreeDetail y (insertOperator ansTree x) variableArray
			  else raise Oops

let formAbstractTree input = formAbstractTreeDetail (infixToPrefix input) Empty (makeVariableArray (explode input) ["y";"x";"Constant"])


(**)

(*Mike's code*)


let newCompare2 i l1 l2 =
	if l1.(i) <  l2.(i) then 1
    else if l1.(i) >  l2.(i) then -1
    else 0

let newCompare l1 l2 =
	if l1.(1) <  l2.(1) then 1
    else if l1.(1) >  l2.(1) then -1
    else 0

let rec doSort aList i =
	if i = 0  then aList
    else doSort (List.sort (newCompare2 i) aList ) (i-1)


let isZeroLeaf l =
	match l with
	| Leaf (a) -> if a.(0) = 0 then true
	              else false
	| _ -> false

let plusSimpling aTree =
	match aTree with
	| Node (o, l,r )-> if (isZeroLeaf l) then r
	                   else if (isZeroLeaf r) then l
	                   else Node (o, l, r)
	| _ -> raise Oops


let rec plusSimple aTree =
	match aTree with
	Empty -> raise Oops
	| Node(o, l,r ) -> if o = "+" then plusSimpling (Node (o,(plusSimple l),(plusSimple r)) )
	                   else Node (o,(plusSimple l),(plusSimple r))
	| Leaf(a)  -> Leaf(a)


let multiSimpling aTree =
	match aTree with
	| Node (o, l,r )-> if (isZeroLeaf l) then l
	                   else if (isZeroLeaf r) then r
	                   else Node (o, l, r)
	| _ -> raise Oops


let rec multiSimple aTree =
	match aTree with
	Empty -> raise Oops
	| Node(o, l,r ) -> if o = "*" then multiSimpling (Node (o,(multiSimple l),(multiSimple r)) )
	                   else Node (o,(multiSimple l),(multiSimple r))
	| Leaf(a)  -> Leaf(a)


(*減法中出現零的話  會將他簡單化   *)
(*使用方式就是 (fun) minusSimple aTree(你想要簡化的樹) *)
let minusSimpling aTree =
	match aTree with
	| Node (o, l,r )-> if (isZeroLeaf r) then l
	                   else Node (o, l, r)
	| _ -> raise Oops


let rec minusSimple aTree =
	match aTree with
	Empty -> raise Oops
	| Node(o, l,r ) -> if o = "-" then minusSimpling (Node (o,(minusSimple l),(minusSimple r)) )
	                   else Node (o,(minusSimple l),(minusSimple r))
	| Leaf(a)  -> Leaf(a)
let rec getLeaf leaf res i=
	if i >= Array.length leaf then res
    else leaf.(i)::(getLeaf leaf res (i+1))


let rec equalxy l r i=
	if i >= Array.length l then true
    else if l.(i) = r.(i) then equalxy l r (i+1)
    else false
let rec equalList l r =
	match r with
	[] -> false
	| a::y -> if (equalxy l a 1) then true
	          else equalList l y
let returnSetArray a i e =
	Array.set a i e;
	(a)
(*加法函式庫*)
let rec plused res target return i =
	if i >= Array.length res then return
    else if i = 0 then plused res target (returnSetArray return i (res.(i)+target.(i)) ) (i+1)
    else plused res target (returnSetArray return i (res.(i)))  (i+1)

let rec plusing2 l r i =
    match r with
    [] -> raise Oops
    |  a::y -> if (equalxy l a 1) then (plused l a (Array.create (Array.length l) 0 ) 0 )::y
	           else a::(plusing2 l y i)

let plusing l r i=
    if ( equalList l r ) then (plusing2 l r i)
    else l::r

let rec plus l r i =
	if l = [] then r
    else (plus (List.tl l) (plusing (List.hd l)  r i ) i )
(*加法函式庫   結束*)
(*減法函式庫*)

let rec minused res target return i =
	if i >= Array.length res then return
    else if i = 0 then minused res target (returnSetArray return i (res.(i)-target.(i)) ) (i+1)
    else minused res target (returnSetArray return i (res.(i)))  (i+1)

let rec minusing2 l r i =
    match l with
    [] -> raise Oops
    |  a::y -> if (equalxy a r 1) then (minused a r (Array.create (Array.length a) 0 ) 0 )::y
	           else a::(minusing2 y r i)

let minusing l r i=
    if ( equalList r l ) then (minusing2 l r i)
    else l@(  (returnSetArray r 0 (r.(0)*i) )::[] )


let rec minus l r i =
	if r = [] then l
    else (minus ( minusing l (List.hd r) i ) (List.tl r) i )
(*減法函式庫   結束*)
(*乘法函式庫*)
let rec domulti res target return i =
	if i >= Array.length res then return
    else if i = 0 then domulti res target (returnSetArray return i (res.(i)*target.(i)) ) (i+1)
    else domulti res target (returnSetArray return i (res.(i)+target.(i)))  (i+1)


let rec multiing l r  =
	if r <> [] then (domulti l (List.hd r) (Array.create (Array.length l) 0 ) 0 )::(multiing l (List.tl r))
    else []

let rec multi l r res =
	if l = [] then res
    else (multi (List.tl l ) r (plus (multiing (List.hd l) r ) res 1)  )
let rec doSimple aTree =
 	match aTree with
 	Empty -> raise Oops
 	| Leaf (a) -> a::[]
 	| Node(o, l,r ) -> if o = "+" then (plus (doSimple l) (doSimple r) 1)
 	                   else if o = "-" then (minus (doSimple l) (doSimple r) (-1))
 	                   else if o = "*" then (multi (doSimple l) (doSimple r) [])
 	                   (*else if o = "/" then (divi (doSimple l) (doSimple r) [])*)
 	                   else raise Oops
 	| _ -> raise WrongType

let rec anyVariable a i =
    if i >= Array.length a then false
    else if a.(i) > 0 then true
    else anyVariable a (i+1)

let rec newString aList aArray i result =
	if i >= Array.length aArray then result
    else if aList.(i) = 0 then newString aList aArray (i+1) result
    else if i = 0 then if (aList.(i)=1) && (anyVariable aList 1) then  newString aList aArray (i+1) result
                       else newString aList aArray (i+1) (result^(string_of_int aList.(i)) )
    else if aList.(i) = 1 then  newString aList aArray (i+1) (result^aArray.(i) )
    else newString aList aArray (i+1) (result^aArray.(i)^"^"^(string_of_int aList.(i)) )


let rec output aList aArray i result =
	match aList with
	[] -> result
	| a::y -> if i > 0 && a.(0) > 0 then "+"::(newString a aArray 0 "")::(output y aArray (i+1) result)
              else (newString a aArray 0 "")::(output y aArray (i+1) result)

let simplize aTree =
	let s = (doSimple ( minusSimple ( plusSimple aTree ) )  ) in
	doSort s ((Array.length (List.hd s))-1)
let startSimplize input =
	String.concat "" (output (simplize (formAbstractTree input) ) (makeVariableArray (explode input) ["y";"x";"Constant"]) 0 [] )

(**)
	type bitree = Leaf of int array \| Node of string * bitree * bitree \| Empty
	exception Oops
	exception WrongType

	(Julia's code)


	let left = function Node (x, y, z) -> y
	let right = function Node (x, y, z) -> z
	(* let getVal a = match a with
	Node (x, y, z) -> x
	\| Leaf (w) -> w *)
	let getType a = match a with
	"+" -> "operator"
	\| "-" -> "operator"
	\| "*" -> "operator"
	\| "/" -> "operator"
	\| "^" -> "power"
	\| "(" -> "parenthese"
	\| ")" -> "parenthese"
	\| _ -> try if int_of_string a = 123 then "number"
	else "number" with Failure "int_of_string" -> "variable" (* include both single variable ex. x, y AND compound variable ex. x^2, y^3 *)



	let explode s =
	let rec exp i l t c =
	if i < 0 then
	if t = "" then l
	else if c = true then t::l
	else t :: "*" :: l
	else if (Char.escaped s.[i]) = " " then exp (i - 1) l t c
	else if getType (Char.escaped s.[i]) = "operator" then
	if t = "" then exp (i - 1) ((Char.escaped s.[i]) :: l) "" true
	else if c = true then exp (i - 1) ((Char.escaped s.[i]) :: (t :: l)) "" true
	else exp (i - 1) ((Char.escaped s.[i]) :: t :: "*" :: l) "" true
	else if getType (Char.escaped s.[i]) = "parenthese" then
	if (Char.escaped s.[i]) = ")" then
	if c = true then
	if t = "" then exp (i - 1) ((Char.escaped s.[i]) :: l) "" true
	else exp (i - 1) ((Char.escaped s.[i]) :: "*" :: t :: l) "" true
	else if t = "" then exp (i - 1) ((Char.escaped s.[i]) :: "*" :: l) "" true
	else exp (i - 1) ( (Char.escaped s.[i]) :: "" :: t :: "" :: l ) "" true
	else if List.hd l = "(" \|\| List.hd l = ")" then exp (i - 1) ((Char.escaped s.[i]) :: l) "" false (* for "(("或"))"的狀況 *)
	else if t != "" then
	if c = true then exp (i - 1) ( (Char.escaped s.[i]) :: t :: l ) "" false
	else exp (i - 1) ( (Char.escaped s.[i]) :: t :: "*" :: l ) "" false
	else exp (i - 1) ((Char.escaped s.[i]) :: l) "" false
	else if getType (Char.escaped s.[i]) = "variable" then
	if c = true then
	if t = "" then exp (i - 1) ((Char.escaped s.[i]) :: l) "" false
	else exp (i - 1) ((Char.escaped s.[i]) :: "*" :: t :: l) "" false
	else if t = "" then exp (i - 1) ((Char.escaped s.[i]) :: "*" :: l) "" false
	else exp (i - 1) ( (Char.escaped s.[i]) :: "" :: t :: "" :: l ) "" false
	else if getType (Char.escaped s.[i]) = "power" then
	if c = true then
	if t = "" then exp (i - 2) ( ( (Char.escaped s.[i-1])^(Char.escaped s.[i])^(Char.escaped s.[i+1]) ) :: (List.rev (List.tl (List.rev l))) ) "" false
	else exp (i - 2) ( ( (Char.escaped s.[i-1])^(Char.escaped s.[i])^t ) :: l ) "" false
	else if t = "" then exp (i - 2) ( ( (Char.escaped s.[i-1])^(Char.escaped s.[i])^(Char.escaped s.[i+1]) ) :: (List.rev (List.tl (List.rev l))) ) "" false
	else exp (i - 2) ( ( (Char.escaped s.[i-1])^(Char.escaped s.[i])^t ):: "*" :: l ) "" false
	else exp (i - 1) l ((Char.escaped s.[i])^t) c in
	exp (String.length s - 1) [] "" true




	(* 遇到＋、-時考慮有沒有被壓在下面且沒有用括號隔開的、/，有則移到result的stack )
	let rec s1ToPlusOrMinus s =
	if s = [] then []
	else match (List.hd s) with
	"+" -> s
	\| "-" -> s
	\| ")" -> s
	\| _ -> s1ToPlusOrMinus (List.tl s)
	let resultToPlusOrMinus inputS1 inputResult =
	let rec resultToPlusOrMinusDetail (s:string list) (result:string list) =
	if s = [] then result
	else match (List.hd s) with
	"+" -> result
	\| "-" -> result
	\| ")" -> result
	\| _ -> resultToPlusOrMinusDetail (List.tl s) ((List.hd s)::result) in
	(resultToPlusOrMinusDetail inputS1 [])@inputResult
	(* ******************************************************************* *)

	(* 遇到右括號直接放入stack，但遇到左括號的時候，要將operator stack（s1)中，在右括號之前的東西都pop出來 *)
	let rec s1ToLeftParenthesis s =
	if s = [] then []
	else match (List.hd s) with
	")" -> List.tl s
	\| _ -> s1ToLeftParenthesis (List.tl s)
	let resultToLeftParenthesis inputS1 inputResult =
	let rec resultToLeftParenthesisDetail (s:string list) (result:string list) =
	if s = [] then result
	else match (List.hd s) with
	")" -> result
	\| _ -> resultToLeftParenthesisDetail (List.tl s) ((List.hd s)::result) in
	(resultToLeftParenthesisDetail inputS1 [])@inputResult
	(* **************************************************************************************** *)

	(* 主要function，revstr為使用者輸入的字串轉為string list後reverse後的結果；s1為operator（暫存）；result為最後要輸出的結果 *)
	(* stack遇到/)時直接放入s1，遇到+-時要考慮是不是有在s1中的/被壓在下面，遇到(時要將)之前的operator pop出來 *)
	let rec infixToPrefixDetail (revstr:string list) (s1:string list) (result:string list) =
	match revstr with
	[] -> (List.rev s1)@result
	\| x::y -> if x = "*" \|\| x = "/" \|\| x = ")" then infixToPrefixDetail y (x::s1) result
	else if x = "+" \|\| x = "-" then infixToPrefixDetail y (x::(s1ToPlusOrMinus s1)) (resultToPlusOrMinus s1 result)
	else if x = "(" then infixToPrefixDetail y (s1ToLeftParenthesis s1) (resultToLeftParenthesis s1 result)
	else infixToPrefixDetail y s1 (x::result)

	(* 以 infixToPrefix "a(b+c(d+e))+f" 這樣的方式，可以將infix轉為prefix *)
	let infixToPrefix input = infixToPrefixDetail (List.rev (explode input)) [] []






	(* ****************************************** *)
	(* hw8 start *)

	(* let tempVariableIndex = [\|"constant";"x";"y"\|] *)

	(* let tempVariableIndex = Array.of_list (List.rev tempList) *)

	let variableIndex variable variableArray =
	let rec variableIndexDetail variable index variableArray =
	if index >= (Array.length variableArray) then -1
	else if variable = variableArray.(index) then index
	else variableIndexDetail variable (index+1) variableArray in
	variableIndexDetail variable 0 variableArray

	exception Oops2


	(* convert a variable (x, x^2, etc.) into array ( [\|1,1,0\|], [\|1,2,0\|], etc. *)
	let convertToLeaf input variableArray =
	let tempArray = Array.make (Array.length variableArray) 0 in
	(* let convertToLeafDetail input tempArray finished = *)
	(* if finished then tempArray *)
	if String.contains input '^' then
	let indexOfVariable = variableIndex (String.sub input 0 (String.index input '^')) variableArray in
	if indexOfVariable != -1 && (Array.set tempArray 0 1) = () && (Array.set tempArray indexOfVariable (int_of_string (String.sub input ((String.index input '^')+1) ((String.length input)-(String.index input '^')-1)))) = () then tempArray
	else raise Oops
	else if getType input = "variable" && (Array.set tempArray 0 1) = () && (Array.set tempArray (variableIndex input variableArray) 1) = () then tempArray
	else if (Array.set tempArray 0 (int_of_string input)) = () then tempArray
	else raise Oops
	(* convertToLeafDetail input (Array.make (Array.length tempVariableIndex) 0) false *)




	(* let addTreeValue aTree a = match a with *)
	let rec isLeft aTree = match aTree with
	Empty -> true
	\| Leaf (w) -> false
	\| Node (x, y ,z) -> isLeft y \|\| isRight y
	and isRight aTree = match aTree with
	Empty -> true
	\| Leaf (w) -> false
	\| Node (x, y ,z) -> isLeft z \|\| isRight z
	let rec insertOperator aTree x = match aTree with
	Empty -> Node(x, Empty, Empty)
	\| Node(a, l, r) -> if isLeft aTree then Node(a, (insertOperator l x), r)
	else if isRight aTree then Node(a, l, (insertOperator r x))
	else raise Oops
	\| Leaf(a) -> raise Oops
	let rec insertNumber aTree x variableArray = match aTree with
	Empty -> Leaf( convertToLeaf x variableArray )
	\| Node(a, l, r) -> if isLeft aTree then Node(a, (insertNumber l x variableArray), r)
	else if isRight aTree then Node(a, l, (insertNumber r x variableArray))
	else raise Oops
	\| Leaf(a) -> raise Oops




	(* 製造variable list *)
	(* 確認這個variable是否已應在variable list裡面了 *)
	let rec meetVariableBefore input templist =
	match templist with
	[] -> false
	\| a::y -> if a = input then true
	else meetVariableBefore input y
	(* 確認該variable是否已在variable list中，如果不在則加到variable list並回傳list，若已在其中則直接回傳原本的list *)
	let addVariableToList input tempList=
	if meetVariableBefore input tempList = false then input::tempList
	else tempList

	(* 將inputList（在此為使用者輸入後經explode過的東西）中為variable的部份做檢視，若未出現過則加入variable list中，最後回傳新增過後的list *)
	let rec makeVariableList inputList tempList =
	match inputList with
	[] -> tempList
	\| a::y -> if getType a = "variable" then if String.contains a '^' then makeVariableList y (addVariableToList (String.sub a 0 (String.index a '^')) tempList)
	else makeVariableList y (addVariableToList a tempList)
	else makeVariableList y tempList

	(* 將inputList（在此為使用者輸入後經explode過的東西）中為variable的部份做檢視，若未出現過則加入variable list中，最後回傳新增過後的variable Array *)
	let makeVariableArray inputList tempList = (Array.of_list (List.rev (makeVariableList inputList tempList)))





	let rec formAbstractTreeDetail aList ansTree variableArray = match aList with
	[] -> ansTree
	\| x::y -> if getType x = "number" \|\| getType x = "variable" then formAbstractTreeDetail y (insertNumber ansTree x variableArray) variableArray
	else if getType x = "operator" then formAbstractTreeDetail y (insertOperator ansTree x) variableArray
	else raise Oops

	let formAbstractTree input = formAbstractTreeDetail (infixToPrefix input) Empty (makeVariableArray (explode input) ["y";"x";"Constant"])


	(**)

	(Mike's code)


	let newCompare2 i l1 l2 =
	if l1.(i) < l2.(i) then 1
	else if l1.(i) > l2.(i) then -1
	else 0

	let newCompare l1 l2 =
	if l1.(1) < l2.(1) then 1
	else if l1.(1) > l2.(1) then -1
	else 0

	let rec doSort aList i =
	if i = 0 then aList
	else doSort (List.sort (newCompare2 i) aList ) (i-1)


	let isZeroLeaf l =
	match l with
	\| Leaf (a) -> if a.(0) = 0 then true
	else false
	\| _ -> false

	let plusSimpling aTree =
	match aTree with
	\| Node (o, l,r )-> if (isZeroLeaf l) then r
	else if (isZeroLeaf r) then l
	else Node (o, l, r)
	\| _ -> raise Oops


	let rec plusSimple aTree =
	match aTree with
	Empty -> raise Oops
	\| Node(o, l,r ) -> if o = "+" then plusSimpling (Node (o,(plusSimple l),(plusSimple r)) )
	else Node (o,(plusSimple l),(plusSimple r))
	\| Leaf(a) -> Leaf(a)


	let multiSimpling aTree =
	match aTree with
	\| Node (o, l,r )-> if (isZeroLeaf l) then l
	else if (isZeroLeaf r) then r
	else Node (o, l, r)
	\| _ -> raise Oops


	let rec multiSimple aTree =
	match aTree with
	Empty -> raise Oops
	\| Node(o, l,r ) -> if o = "*" then multiSimpling (Node (o,(multiSimple l),(multiSimple r)) )
	else Node (o,(multiSimple l),(multiSimple r))
	\| Leaf(a) -> Leaf(a)


	(減法中出現零的話會將他簡單化 )
	(使用方式就是 (fun) minusSimple aTree(你想要簡化的樹) )
	let minusSimpling aTree =
	match aTree with
	\| Node (o, l,r )-> if (isZeroLeaf r) then l
	else Node (o, l, r)
	\| _ -> raise Oops


	let rec minusSimple aTree =
	match aTree with
	Empty -> raise Oops
	\| Node(o, l,r ) -> if o = "-" then minusSimpling (Node (o,(minusSimple l),(minusSimple r)) )
	else Node (o,(minusSimple l),(minusSimple r))
	\| Leaf(a) -> Leaf(a)
	let rec getLeaf leaf res i=
	if i >= Array.length leaf then res
	else leaf.(i)::(getLeaf leaf res (i+1))


	let rec equalxy l r i=
	if i >= Array.length l then true
	else if l.(i) = r.(i) then equalxy l r (i+1)
	else false
	let rec equalList l r =
	match r with
	[] -> false
	\| a::y -> if (equalxy l a 1) then true
	else equalList l y
	let returnSetArray a i e =
	Array.set a i e;
	(a)
	(加法函式庫)
	let rec plused res target return i =
	if i >= Array.length res then return
	else if i = 0 then plused res target (returnSetArray return i (res.(i)+target.(i)) ) (i+1)
	else plused res target (returnSetArray return i (res.(i))) (i+1)

	let rec plusing2 l r i =
	match r with
	[] -> raise Oops
	\| a::y -> if (equalxy l a 1) then (plused l a (Array.create (Array.length l) 0 ) 0 )::y
	else a::(plusing2 l y i)

	let plusing l r i=
	if ( equalList l r ) then (plusing2 l r i)
	else l::r

	let rec plus l r i =
	if l = [] then r
	else (plus (List.tl l) (plusing (List.hd l) r i ) i )
	(加法函式庫結束)
	(減法函式庫)

	let rec minused res target return i =
	if i >= Array.length res then return
	else if i = 0 then minused res target (returnSetArray return i (res.(i)-target.(i)) ) (i+1)
	else minused res target (returnSetArray return i (res.(i))) (i+1)

	let rec minusing2 l r i =
	match l with
	[] -> raise Oops
	\| a::y -> if (equalxy a r 1) then (minused a r (Array.create (Array.length a) 0 ) 0 )::y
	else a::(minusing2 y r i)

	let minusing l r i=
	if ( equalList r l ) then (minusing2 l r i)
	else l@( (returnSetArray r 0 (r.(0)*i) )::[] )


	let rec minus l r i =
	if r = [] then l
	else (minus ( minusing l (List.hd r) i ) (List.tl r) i )
	(減法函式庫結束)
	(乘法函式庫)
	let rec domulti res target return i =
	if i >= Array.length res then return
	else if i = 0 then domulti res target (returnSetArray return i (res.(i)*target.(i)) ) (i+1)
	else domulti res target (returnSetArray return i (res.(i)+target.(i))) (i+1)


	let rec multiing l r =
	if r <> [] then (domulti l (List.hd r) (Array.create (Array.length l) 0 ) 0 )::(multiing l (List.tl r))
	else []

	let rec multi l r res =
	if l = [] then res
	else (multi (List.tl l ) r (plus (multiing (List.hd l) r ) res 1) )
	let rec doSimple aTree =
	match aTree with
	Empty -> raise Oops
	\| Leaf (a) -> a::[]
	\| Node(o, l,r ) -> if o = "+" then (plus (doSimple l) (doSimple r) 1)
	else if o = "-" then (minus (doSimple l) (doSimple r) (-1))
	else if o = "*" then (multi (doSimple l) (doSimple r) [])
	(else if o = "/" then (divi (doSimple l) (doSimple r) []))
	else raise Oops
	\| _ -> raise WrongType

	let rec anyVariable a i =
	if i >= Array.length a then false
	else if a.(i) > 0 then true
	else anyVariable a (i+1)

	let rec newString aList aArray i result =
	if i >= Array.length aArray then result
	else if aList.(i) = 0 then newString aList aArray (i+1) result
	else if i = 0 then if (aList.(i)=1) && (anyVariable aList 1) then newString aList aArray (i+1) result
	else newString aList aArray (i+1) (result^(string_of_int aList.(i)) )
	else if aList.(i) = 1 then newString aList aArray (i+1) (result^aArray.(i) )
	else newString aList aArray (i+1) (result^aArray.(i)^"^"^(string_of_int aList.(i)) )


	let rec output aList aArray i result =
	match aList with
	[] -> result
	\| a::y -> if i > 0 && a.(0) > 0 then "+"::(newString a aArray 0 "")::(output y aArray (i+1) result)
	else (newString a aArray 0 "")::(output y aArray (i+1) result)

	let simplize aTree =
	let s = (doSimple ( minusSimple ( plusSimple aTree ) ) ) in
	doSort s ((Array.length (List.hd s))-1)
	let startSimplize input =
	String.concat "" (output (simplize (formAbstractTree input) ) (makeVariableArray (explode input) ["y";"x";"Constant"]) 0 [] )

	(**)