list - 如何根据一组步骤重新排列列表？

Question

我正在尝试根据以下步骤重新排列列表:

首先将每个运算符 (+,-,*) 1 个索引向左移动，方法是将其与左侧的元素进行切换。

然后找到*前面的任何'+'或'-'两个索引，并将'+'或'-'移动到*前面的索引。

示例
["a","-","2","*","b","+","c"]
["-","a","*","2","+","b","c"]
["-","a","+","*","2","b","c"]
我有命令式编程背景，所以我最初的想法是将迭代器作为参数，并像这样跟踪索引中的位置，但我无法让它工作。我的第二个想法是拥抱 Haskell 并在生成器中使用列表理解，但我也在那里挣扎。任何想法或解决方案表示赞赏!

Answer 1

您可以使用显式递归。例如，您可以使用以下命令将元素向左移动一个位置:

isOperator :: String -> Bool
isOperator "+" = True
isOperator "-" = True
isOperator "*" = True
isOperator _ = False

stepOne :: [String] -> [String]
stepOne (x:xs@(o:xs'))
    | isOperator o = o : x : stepOne xs'
    | otherwise = x : stepOne xs
stepOne xa@[_] = xa
stepOne [] = []

这里 (x:xs@(o:xs'))模式与具有两个或更多元素的列表匹配。第一个元素是 x ，第二个是 o ，其余元素存储在 xs'中多变的。 xs是“外部”缺点的尾部。我们检查是否 o是一个运算符，如果是这种情况，我们与 x 交换并在尾部递归 xs' .如 o不是运算符，我们在尾部递归 xs' .
对于给定的样本数据，我们得到:

Prelude> stepOne ["a","-","2","*","b","+","c"]
["-","a","*","2","+","b","c"]

我将第二步留作练习。
话虽如此，Haskell 的成功案例之一可能是解析。存在多个库和工具，例如 parsec [Hackage]和 attoparsec [Hackage] . happy [haskell.org]是一个编译器编译器，可以基于语法在 Haskell 中构建解析器。因此，您本身不需要执行中缀到前缀的转换，而是让工具为您完成工作。