递归调车场算法

Question

大家

我正在尝试使用 实现简单算法“调车场”（将中缀解析为后缀表示法） SML（标准 ML）

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。

虽然shunting-yard算法通常被描述为一种中缀转后缀的算法，但它实际上只是一种解析算法；您可以直接评估中缀表达式或从中创建解析树，而不是执行中缀→后缀。如果你选择后者，那么你可以使用一个单一的堆栈，它是一个堆栈的部分解析树（森林，换句话说）；在算法结束时，如果输入在语法上是正确的，堆栈将由一个可以返回的解析树组成。

递归调车场算法

Recursive shunting yard algorithm

algorithm

recursion

sml