I am trying to implement simple algorithm "Shunting yard" (to parse infix to postfix notation) using SML (Standart ML)
fun parseToRPN(input:string) =
val _input = explode input
val digits = [#"0", #"1", #"2", #"3", #"4", #"5", #"6", #"7", #"8", #"9"]
val stack = 
val output = 
fun member(n:char, nil) = false
| member(n:char, h::t) = if n = h then true else member(n:char, t);
fun parse(nil) = raise Empty
| parse(h::t) = if member(h, digits) then h::parse(t)
else if h = #"(" then ???
But I have no idea how to push to stack in SML. Can somebody give some tips! Thank you!
Best How To :
The stack is passed as an additional argument to
parse. You'll want to pass the accumulated RPN as well.
Although the shunting-yard algorithm is usually presented as an algorithm for converting infix to postfix notation, it is actually just a parsing algorithm; you can directly evaluate infix expressions or create parse trees from them instead of doing the infix→postfix. If you choose to do the latter, then you can use a single stack, which is a stack of partial parse trees (a forest, in other words); at the end of the algorithm, if the input was syntactically correct, the stack will consist of a single parse tree which can be returned.