递归调车码算法

Question

所有人

我正在尝试使用SML (Standart ML)实现简单的算法“分流场”(，用于将infix解析为后缀符号)。

fun parseToRPN(input:string) = 
    let
        val _input =  explode input
        val digits = [#"0", #"1", #"2", #"3", #"4", #"5", #"6", #"7", #"8", #"9"]
        val stack = []
        val output = []
        exception Empty

        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   ???                 
    in
    ...
    end

但我不知道如何在SML中进行堆栈。谁能给点建议吗？谢谢!

Answer 1

堆栈作为附加参数传递给parse。您也需要传递累积的RPN。

虽然调车场算法通常是作为将infix转换为后缀符号的算法提出的，但它实际上只是一个解析算法；您可以直接计算infix表达式或从它们创建解析树，而不是执行infix→后缀。如果您选择了后者，那么您可以使用一个堆栈，它是一个部分解析树的堆栈(换句话说，是一个林)；在算法的末尾，如果输入在语法上是正确的，那么堆栈将由一个可以返回的解析树组成。