Re: 求个脚本或工具能合并ip地址段的脚本
发表于 : 2015-02-05 12:11
这不是一道标准的ACM竞赛题么,以前还在某个OJ系统上作过类似的
代码: 全选
open Ok_parsec
open Parsec
let decimalToBinary dec=
let rec decimalToBinary= function
| 0-> []
| n-> string_of_int (n mod 2) :: decimalToBinary (n / 2)
in
decimalToBinary dec |> List.rev |> String.concat ""
let binaryToDecimal bin=
("0b" ^ bin) |> int_of_string |> string_of_int
(* 将 subnet, 类型为 string * int 转换为字符串,用于输出 *)
let subnetToStr subnet=
let (ip, mask)= subnet in
let cleanUp ip=
(String.sub ip 0 mask) ^ (String.make (32-mask) '0')
in
let ip= cleanUp ip in
let sec1= String.sub ip 0 8
and sec2= String.sub ip 8 8
and sec3= String.sub ip 16 8
and sec4= String.sub ip 24 8 in
([sec1; sec2; sec3; sec4]
|> List.map binaryToDecimal
|> String.concat ".")
^ "/"
^ string_of_int mask
(* 定义 ip地址各小段的 parser *)
let ipSec=
many num_dec |>> BatString.of_list
(* 定义后面的 mask 位的 parser *)
let mask=
many num_dec |>> BatString.of_list
(* 得到 ip 地址的值表示 *)
let ip ipSecS=
let (sum, _)= List.fold_right
(fun num (sum, shift)->
(sum + (int_of_string num) lsl shift, shift+8))
ipSecS
(0, 0)
in sum
(* 定义 subnet 的分析器 *)
let subnet=
let%m ipSecS= sepBy (char '.') ipSec in
char '/' >>
let%m mask= mask |>> int_of_string in
let ip= ip ipSecS |> decimalToBinary in
let ip= String.make (32 - (String.length ip)) '0' ^ ip in
return (ip, mask)
(* 从输入产生一份 subnet 的列表 *)
let subnets input=
input
|> BatIO.lines_of
|> BatEnum.fold
(fun content line-> line::content)
[]
(* 尝试合并两个网域 *)
let merge net1 net2=
let rec merge net1 net2=
let (ip1, mask1)= net1
and (ip2, mask2)= net2 in
if mask1 = mask2 then
if String.sub ip1 0 mask1 <> String.sub ip2 0 mask1 then
if String.sub ip1 0 (mask1-1) = String.sub ip2 0 (mask1-1)
then merge (ip1, (mask1-1)) (ip2, (mask1-1))
else None
else Some net1
else
if String.sub ip1 0 mask1 = String.sub ip2 0 mask1
then Some net1
else None
in
let (ip1, mask1)= net1
and (ip2, mask2)= net2 in
if mask1 > mask2 then
merge net2 net1
else
merge net1 net2
(* 合并一份列表里面的所有网域 *)
let rec mergeAll res nets=
let mergeRes net=
match res with
| []-> None
| res::_-> merge res net
in
match nets with
| net::left->
(match mergeRes net with
| Some net-> mergeAll (net::List.tl res) left
| None-> mergeAll (net::res) left)
| []-> res
let main ()=
let subnets= subnets BatIO.stdin in (* 从 stdin 输入,得到网域列表 *)
let subnets=
subnets
|> List.map (parse_string subnet) (* 对列表里面的每个网域通过 subnet 语法分析器进行并发分析,得到 subnet list 结构,也就是 (string * int) list *)
|> List.map (fun thread-> (* 检查分析是否有误 *)
match Lwt.state thread with
| Lwt.Return Parsec.Ok (r, _)->r
| _-> failwith "parse_error")
|> List.rev
in
mergeAll [] subnets (* 无误就开始合并作业 *)
|> mergeAll []
|> List.map subnetToStr (* 然后将列表里的每个 subnet 转换为字符串 *)
|> List.iter print_endline (* 并输出到标准输出 *)
let ()= main ()