open System
let satisfy p = function
| c::cs when p c -> Some(c, cs)
| _ -> None
let pstring cs s =
let rec aux = function
| [], s -> Some((), s)
| x::xs, c::s when x = c -> aux (xs, s)
| _ -> None
aux (Seq.toList cs, s)
let eos = function [] as xs -> Some((), xs) | _ -> None
let (|>>) p f = p >> Option.map (fun (x, s) -> f x, s)
let (>>%) p x = p |>> fun _ -> x
let (</>) p1 p2 s = p1 s |> Option.orElseWith (fun _ -> p2 s)
let (.>>.) p1 p2 s = p1 s |> Option.bind (fun (x1, s) -> p2 s |> Option.map (fun (x2, s) -> (x1, x2), s))
let (.>>) p1 p2 = (p1 .>>. p2) |>> fst
let (>>.) p1 p2 = (p1 .>>. p2) |>> snd
let many p =
let rec aux xs s =
match p s with
| None -> List.rev xs, s
| Some(x, s) -> aux (x::xs) s
aux [] >> Some
let many1 p = p .>>. many p |>> list.Cons
let chainl p op =
p .>>. many (op .>>. p)
|>> fun (x, xs) -> List.fold (fun x (op, y) -> op x y) x xs
let refParser() =
let ref = ref <| fun _ -> failwith ""
ref, fun s -> !ref s
let run p = Seq.toList >> p >> Option.map fst
let parser =
let t = pstring
let number = many1 (satisfy Char.IsDigit) |>> (List.toArray >> String >> double)
let mulOp = (t"*" >>% (*)) </> (t"/" >>% (/)) </> (t"" >>% (*))
let addOp = (t"+" >>% (+)) </> (t"-" >>% (-))
let _exp
, exp = refParser
() let prim
= (t
"(" >>.
exp .
>> t
")") </> number
let mul = chainl prim mulOp
let add = chainl mul addOp
_exp := add
add .>> eos
let eval s =
if 1000 < String.length s then None
else run parser s
|> Option.map (truncate >> string)
|> Option.defaultValue "Error"
|> stdout.WriteLine
let rec aux () =
match stdin.ReadLine() with
| null -> ()
| x -> eval x; aux()
aux()
lazy
eval "1+2*((3-4*5)/6+7)*8-9" // 58
eval "100/2(3+4)" // 350
eval "100/2*(3+4)" // 350
eval "*10" // Error
eval (String.replicate 1001 "0") // Error
eval "1/3*3" // 1
b3BlbiBTeXN0ZW0KCmxldCBzYXRpc2Z5IHAgPSBmdW5jdGlvbgogICAgfCBjOjpjcyB3aGVuIHAgYyAtPiBTb21lKGMsIGNzKQogICAgfCBfIC0+IE5vbmUKCmxldCBwc3RyaW5nIGNzIHMgPQogICAgbGV0IHJlYyBhdXggPSBmdW5jdGlvbgogICAgICAgIHwgW10sIHMgLT4gU29tZSgoKSwgcykKICAgICAgICB8IHg6OnhzLCBjOjpzIHdoZW4geCA9IGMgLT4gYXV4ICh4cywgcykKICAgICAgICB8IF8gLT4gTm9uZQogICAgYXV4IChTZXEudG9MaXN0IGNzLCBzKQpsZXQgZW9zID0gZnVuY3Rpb24gW10gYXMgeHMgLT4gU29tZSgoKSwgeHMpIHwgXyAtPiBOb25lCgpsZXQgKHw+PikgcCBmID0gcCA+PiBPcHRpb24ubWFwIChmdW4gKHgsIHMpIC0+IGYgeCwgcykKbGV0ICg+PiUpIHAgeCA9IHAgfD4+IGZ1biBfIC0+IHgKbGV0ICg8Lz4pIHAxIHAyIHMgPSBwMSBzIHw+IE9wdGlvbi5vckVsc2VXaXRoIChmdW4gXyAtPiBwMiBzKQpsZXQgKC4+Pi4pIHAxIHAyIHMgPSBwMSBzIHw+IE9wdGlvbi5iaW5kIChmdW4gKHgxLCBzKSAtPiBwMiBzIHw+IE9wdGlvbi5tYXAgKGZ1biAoeDIsIHMpIC0+ICh4MSwgeDIpLCBzKSkKbGV0ICguPj4pIHAxIHAyID0gKHAxIC4+Pi4gcDIpIHw+PiBmc3QKbGV0ICg+Pi4pIHAxIHAyID0gKHAxIC4+Pi4gcDIpIHw+PiBzbmQKCmxldCBtYW55IHAgPQogICAgbGV0IHJlYyBhdXggeHMgcyA9CiAgICAgICAgbWF0Y2ggcCBzIHdpdGgKICAgICAgICB8IE5vbmUgLT4gTGlzdC5yZXYgeHMsIHMKICAgICAgICB8IFNvbWUoeCwgcykgLT4gYXV4ICh4Ojp4cykgcwogICAgYXV4IFtdID4+IFNvbWUKCmxldCBtYW55MSBwID0gcCAuPj4uIG1hbnkgcCB8Pj4gbGlzdC5Db25zCgpsZXQgY2hhaW5sIHAgb3AgPQogICAgcCAuPj4uIG1hbnkgKG9wIC4+Pi4gcCkKICAgIHw+PiBmdW4gKHgsIHhzKSAtPiBMaXN0LmZvbGQgKGZ1biB4IChvcCwgeSkgLT4gb3AgeCB5KSB4IHhzCgpsZXQgcmVmUGFyc2VyKCkgPQogICAgbGV0IHJlZiA9IHJlZiA8fCBmdW4gXyAtPiBmYWlsd2l0aCAiIgogICAgcmVmLCBmdW4gcyAtPiAhcmVmIHMKCmxldCBydW4gcCA9IFNlcS50b0xpc3QgPj4gcCA+PiBPcHRpb24ubWFwIGZzdAoKbGV0IHBhcnNlciA9CiAgICBsZXQgdCA9IHBzdHJpbmcKICAgIGxldCBudW1iZXIgPSBtYW55MSAoc2F0aXNmeSBDaGFyLklzRGlnaXQpIHw+PiAoTGlzdC50b0FycmF5ID4+IFN0cmluZyA+PiBkb3VibGUpCiAgICBsZXQgbXVsT3AgPSAodCIqIiA+PiUgKCopKSA8Lz4gKHQiLyIgPj4lICgvKSkgPC8+ICh0IiIgPj4lICgqKSkKICAgIGxldCBhZGRPcCA9ICh0IisiID4+JSAoKykpIDwvPiAodCItIiA+PiUgKC0pKQoKICAgIGxldCBfZXhwLCBleHAgPSByZWZQYXJzZXIoKQogICAgbGV0IHByaW0gPSAodCIoIiA+Pi4gZXhwIC4+PiB0IikiKSA8Lz4gbnVtYmVyCiAgICBsZXQgbXVsID0gY2hhaW5sIHByaW0gbXVsT3AKICAgIGxldCBhZGQgPSBjaGFpbmwgbXVsIGFkZE9wCiAgICBfZXhwIDo9IGFkZAoKICAgIGFkZCAuPj4gZW9zCgpsZXQgZXZhbCBzID0KICAgIGlmIDEwMDAgPCBTdHJpbmcubGVuZ3RoIHMgdGhlbiBOb25lCiAgICBlbHNlIHJ1biBwYXJzZXIgcwogICAgfD4gT3B0aW9uLm1hcCAodHJ1bmNhdGUgPj4gc3RyaW5nKQogICAgfD4gT3B0aW9uLmRlZmF1bHRWYWx1ZSAiRXJyb3IiCiAgICB8PiBzdGRvdXQuV3JpdGVMaW5lCgpsZXQgcmVjIGF1eCAoKSA9CiAgICBtYXRjaCBzdGRpbi5SZWFkTGluZSgpIHdpdGgKICAgIHwgbnVsbCAtPiAoKQogICAgfCB4IC0+IGV2YWwgeDsgYXV4KCkKYXV4KCkKCmxhenkKICAgIGV2YWwgIjErMiooKDMtNCo1KS82KzcpKjgtOSIgLy8gNTgKICAgIGV2YWwgIjEwMC8yKDMrNCkiIC8vIDM1MAogICAgZXZhbCAiMTAwLzIqKDMrNCkiIC8vIDM1MAogICAgZXZhbCAiKjEwIiAvLyBFcnJvcgogICAgZXZhbCAoU3RyaW5nLnJlcGxpY2F0ZSAxMDAxICIwIikgLy8gRXJyb3IKICAgIGV2YWwgIjEvMyozIiAvLyAxCg==
MSsyKigoMy00KjUpLzYrNykqOC05CjEwMC8yKDMrNCkKMTAwLzIqKDMrNCkKKjEwCjAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAKMS8zKjMK
1+2*((3-4*5)/6+7)*8-9
100/2(3+4)
100/2*(3+4)
*10
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1/3*3