在带括号的一维列表上应用递归

Question

我是F#的新手，我正在尝试编写一个简单的程序来读取数学表达式并计算它。

我成功地计算了表达式，例如："5+3 *3 - 1/2"、"10 + 50 /50"等。由于这相当简单，并且通过直接递归完成，因此我想使用其他数学函数（cos，sin等）将其提升到一个新的水平，但是。我偶然发现了括号，因为我无法了解如何递归诸如"（（5+3） * 5） - （4-5）"之类的模式，因为这是所谓的令牌的 1 个最小列表（我用正则表达式"标记"输入字符串"）和具有无穷无尽表达式的外层和内层的列表！

这是我用于第一个计算原型的代码：

let rec parseEq (src:Expression) = 
match src with 
| [Int number] -> number
| _ ->
    match decompose src with
    Some(Int head,rest) -> 
        match decompose rest with
            | Some(Plus,  rest) -> head + parseEq rest
            | Some(Minus, rest) -> head - parseEq rest
            | Some(Times, rest) -> head * parseEq rest
            | Some(DevBy, rest) -> head / parseEq rest
            | _ -> failwith "input error"
    | _ -> failwith "input error"

注意标记：加号，减号，Int等，这与我试图用来计算更复杂的表达式的appraoch相同。

更新：这是我在标记化后得到的列表：

"((5+5) - 10)" |> tokenize;;
val it : Token list =
[Open; Open; Digit 5.0; Plus; Digit 5.0; Close; Minus; Digit 10.0; Close]

更新：有没有办法将令牌列表的一部分"替换"为令牌列表类型的一个令牌？喜欢这个：

"5 + (3-1)" = [Digit 5; Plus; Open; Digit 3; Minus; Digit 1; Close]

成为：

"5 + (3-1)" = [Digit 5; Plus; Expr [Digit 3; Minus; Digit 1]]

任何想法都会有所帮助，谢谢！

Answer 1

我认为要做到这一点，您可能需要将您的表达式转换为前缀表示法。 这需要走过它并推到堆栈上，直到您准备好接受该术语，因此

例如 （（5+5） - 10）

成为

（+5,5）（-10）。 然后，只需从左到右并内联评估表达式即可。

Answer 2

最好的解决方案是你添加的DU

|Bracket of Token list

然后将函数更改为

match decompose src with
|Some(Int head,rest) -> 
    match decompose rest with
        | Some(Plus,  rest) -> head + parseEq rest
        | Some(Minus, rest) -> head - parseEq rest
        | Some(Times, rest) -> head * parseEq rest
        | Some(DevBy, rest) -> head / parseEq rest
        | _ -> failwith "input error"
|Some(Bracket b,rest) ->
    let head = parseEq b
    match decompose rest with
        | Some(Plus,  rest) -> head + parseEq rest
        | Some(Minus, rest) -> head - parseEq rest
        | Some(Times, rest) -> head * parseEq rest
        | Some(DevBy, rest) -> head / parseEq rest
        | _ -> failwith "input error"
| _ -> failwith "input error"