使用方法
開啟Ocaml
複製下面的code
接著輸入
startSimplize 字串
即可處理
ex
# startSimplize "x+y+2*3+2x+x^2+y^2";;
- : string = "x^2+3x+y^2+y+6"
Created
December 15, 2012 14:35
-
-
Save eva0919/4295676 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 [] ) | |
| (**) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment