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

Question

我对 F# 有点陌生，我正在尝试编写一个简单的程序来读取数学表达式并计算它。

我成功地计算了以下表达式:"5+3 *3 - 1/2"、"10 + 50/50" 等。因为这是由于相当简单并且通过简单的递归完成，我想使用其他数学函数(cos，sin 等)将其提升到一个新的水平，但是。 。 。我偶然发现了括号，因为我不知道如何递归“((5+3) * 5) - (4-5)”等模式，因为这是 1 个定义列表所谓的标记(我用正则表达式“标记”输入字符串)以及具有无限表达式的外层和内层的列表!

这是我用于第一个计算原型(prototype)的代码:

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"

注意标记:加号、减号、整数等。这与我尝试用来计算更复杂表达式的方法相同。

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

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

更新:有没有一种方法可以将 token 列表的一部分“替换”为 token 列表类型的一个 token ？ 像这样:

"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)。那么只需从左到右并内联计算表达式即可。