Haskell

Question

我正在努力想出转换正则表达式的算法（在正则语言的上下文中，只有 3 个操作 '.' 用于 concat，'+' 用于 "or" 和 '*' 用于迭代) 对正则表达式树进行反向波兰表示法。

例如我有一个正则表达式

aa.bb.+

为此我需要构建以下表达式树

      +
    /   \
   .     .
  / \   / \
 b   b a   a

非常感谢任何帮助。谢谢！

Answer 1

使用基于堆栈的算法（在 Haskell 中转换为 foldl）并不难做到：

data Tree
  = Symbol Char
  | Op Char Tree Tree
  deriving Show

type Stack = [Tree]

step :: Stack -> Char -> Stack
step (r:l:s) '.' = (Op '.' l r):s
step (r:l:s) '+' = (Op '+' l r):s
step s c         = (Symbol c):s

parse :: String -> Stack
parse = foldl step []

这会产生这样的结果：

λ> parse "aa.bb.+"
[Op '+' (Op '.' (Symbol 'a') (Symbol 'a')) (Op '.' (Symbol 'b') (Symbol 'b'))]

你没有写 任何关于你的数据结构的东西 所以我采取了一些自由 - 一旦你理解了 step 和foldl 在 parse

如果你想改变 left/right，就像你的例子一样，你只需要在 step 中做：

step :: Stack -> Char -> Stack
step (l:r:s) '.' = (Op '.' l r):s
step (l:r:s) '+' = (Op '+' l r):s
step s c         = (Symbol c):s

示例：

λ> parse "aa.bb.+"
[Op '+' (Op '.' (Symbol 'b') (Symbol 'b')) (Op '.' (Symbol 'a') (Symbol 'a'))]

但如果顺序很重要，我希望第一个（这里你在 aa 之前有 bb，这很奇怪......

当然很奇怪 star 操作也是二进制的所以我建议：

data Tree
  = Symbol Char
  | Concat Tree Tree
  | Star Tree
  deriving Show

type Stack = [Tree]

step :: Stack -> Char -> Stack
step (r:l:s) '.' = (Concat r l):s
step (t:s)   '+' = (Star t):s
step s c         = (Symbol c):s

parse :: String -> Stack
parse = foldl step []

这会稍微改变你的语法：

λ> parse "aa.bb..+"
[Star (Concat (Concat (Symbol 'b') (Symbol 'b')) (Concat (Symbol 'a') (Symbol 'a')))]

但在我看来这更明智

将列表转换为可能

当然你可能不喜欢 [Stack] return 所以你可以这样做：

parse :: String -> Maybe Tree
parse input =
  case result of
    [t] -> Just t
    []  -> Nothing
    _   -> error "syntax error"
  where result = foldl step [] input

示例：

λ> parse "aa.bb..+"
Just (Star (Concat (Concat (Symbol 'b') (Symbol 'b')) (Concat (Symbol 'a') (Symbol 'a'))))
λ> parse ""
Nothing
λ> parse "aa.bb.+"
*** Exception: syntax error

Haskell - 反向波兰符号正则表达式到表达式树

Haskell - Reverse polish notation regular expression to expression tree

regex

expression-trees

postfix-notation

将列表转换为可能