在带括号的一维列表上应用递归 [英] Applying recursion on 1d-list with parentheses

问题描述

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

I am kinda new to F# and I'm trying to write a simple program that reads a mathematical expression and calculates it.

我成功地计算出了诸如"5+3 *3 - 1/2"，"10 + 50 /50"等表达式.由于这相当简单并且可以通过直接递归来完成，因此我想使用其他数学函数(cos，sin)将其提升到一个新的水平.等)，但. . .我偶然发现括号，因为我不知道如何递归使用(((5 + 3)* 5)-(4-5)"等模式，因为这是1个单位列表的 Tokens (我用Regex'标记'输入字符串")和具有无穷表达式的外层和内层的列表！

I was successfully able to calculate expressions like: "5+3 *3 - 1/2", "10 + 50 /50" etc. As this is being fairly simple and done by straightforward recursion, I wanted to take it to the next level using other mathematical functions (cos,sin etc.) but . . . I stumbled upon parentheses as i can't get an idea of how to recurse on patterns such as "((5+3) * 5) - (4-5)" because this is 1 deminsional list of the so-called Tokens (I 'tokenize' the input string with Regex") and the list having outer and inner layers of endless expressions!

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

This is the code I used for the first prototype of calculations:

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"

请注意令牌:加号，减号，整数等.这是试图用于计算更复杂的表达式的相同方法.

Note the tokens : Plus,Minus, Int etc. this is the same appraoch im trying to use to calculate the more complex expressions.

更新:这是令牌化后得到的列表:

Update: this is the list I get after tokenization:

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

更新:是否可以将令牌列表的一部分替换"为令牌列表类型的一个令牌? 像这样:

Update : is there a way that i can 'replace' a segment of the token list to one token of type Token list? like this:

"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]]

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

Any ideas would be helpful, Thanks!

推荐答案

我认为要执行此操作，您可能需要将表达式转换为前缀表示法.这就需要遍历并推入堆栈，直到您准备好接受该术语为止，所以

I think to do this you probably need to convert your expression into prefix notation. this requires walking over it and pushing onto stacks until you are ready to take the term, so

例如((5 + 5)-10)

for example ((5+5) - 10)

成为

(+ 5,5)(-10).那么只需从左到右并内联评估表达式即可.

(+5,5)(-10). then it's simply a matter of going from left to right and evaluating the expressions inline.

这篇关于在带括号的一维列表上应用递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！