Rosetta Code

Parsing/Shunting-yard algorithm: Difference between revisions

Page Discussion

Parsing/Shunting-yard algorithm (view source)

Revision as of 14:41, 11 March 2017

687 bytes removed ,  7 years ago
→‎{{header|OCaml}}: simplifiy implementation slightly by using list instead of queue, functions instead of hashtable
m (Change header from →‎{{header|XOJO}}: to →‎{{header|Xojo}})
(→‎{{header|OCaml}}: simplifiy implementation slightly by using list instead of queue, functions instead of hashtable)
Line 2,149:
 
 
let op_tblprec op =
match op with
let t = Hashtbl.create 5 in
| "^" -> 4
let () = List.iter (fun (op, prec, assoc) ->
| "*" -> 3
Hashtbl.add t op (prec, assoc))
| [ ("^/", 4,-> Right)3
| ; ("*+", 3,-> Left)2
| ; ("/-", 3,-> Left)2
| _ -> -1;;
; ("+", 2, Left)
 
; ("-", 2, Left) ]▼
 
in t;;
let assoc op =
match op with
| "^" -> Right
▲ | _ ; ("-", 2,> Left) ];;
 
 
(* equivalent to (takeWhile p xs, dropWhile p xs) *)
let split_while p =
let rec go ls xs =
Line 2,170 ⟶ 2,173:
 
 
(* converts list to queue, with most recently added at head *)
let list_of_queue =
Queue.fold (fun xs x -> x::xs) [];;
 
 
(* create string from list of strings, seperated by `sep` *)
let rec intercalate sep xs =
match xs with
Line 2,183 ⟶ 2,180:
 
 
let shunting_yard tkns =
let qrec =pusher Queue.createstack ()queue intkns =
let rec pusher tkns stack =
match tkns with
| [] -> List.rev (list_of_queue q)queue @ stack
| "("::tkns' -> pusher tkns' ("("::stack) queue tkns'
| ")"::tkns' ->
let mv, "("::stack' = split_while ((<>) "(") stack in
letpusher () = List.iterstack' (funmv x@ -> Queue.add x qqueue) mv intkns'
| t::tkns' when prec pushert tkns'< 0 -> pusher stack (t::queue) tkns'
| top::tkns' ->
(trylet mv_to_queue op2 =
let(match op1_prec,assoc op1_assocop = Hashtbl.find op_tbl t inwith
let mv_to_queue op2| Left -> prec op <= prec op2
(try| Right -> prec op < prec op2)
in▼
let op2_prec, op2_assoc = Hashtbl.find op_tbl op2 in
let mv, stack' = split_while mv_to_queue (matchstack op1_assoc within
pusher tkns' (top::stack') (mv @ queue) tkns'▼
| Left -> op1_prec <= op2_prec
in pusher tkns[] [];;▼
| Right -> op1_prec < op2_prec)
with Not_found ->
false)
▲ in
let mv, stack' = split_while mv_to_queue stack in
let () = List.iter (fun x -> Queue.add x q) mv in
▲ pusher tkns' (t::stack')
with Not_found ->
let () = Queue.add t q in
pusher tkns' stack)
▲ in pusher tkns [];;
 
 
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/209104"