我正在从事一个有趣的项目,该项目涉及从正则表达式生成解析树。我已经让它大部分工作了,但我对如何集成连接很感兴趣。
*Main> :l regex.hs
[1 of 1] Compiling Main ( regex.hs, interpreted )
Ok, modules loaded: Main.
*Main> toPostfix "a"
"a"
*Main> toPostfix "a|b"
"ab|"
*Main> toPostfix "((a|b)|c)"
"ab|c|"
*Main> toPostfix "((a|b)|c)de"
"ab|c|de"
*Main> toPostfix "((a|b)|c)*de"
"ab|c|*de"
*Main> toPostfix "(ab)*"
"ab*" -- Should be ab&*
*Main> toPostfix "(ab|bc)"
"abbc|" -- Should be ab&bc&|
这是我的代码:
import Data.List
import Control.Monad
data Reg = Epsilon |
Literal Char |
Or Reg Reg |
Concat Reg Reg |
Star Reg
deriving Eq
showReg :: Reg -> [Char]
showReg Epsilon = "@"
showReg (Literal c) = [c]
showReg (Or r1 r2) = "(" ++ showReg r1 ++ "|" ++ showReg r2 ++ ")"
showReg (Concat r1 r2) = "(" ++ showReg r1 ++ showReg r2 ++ ")"
showReg (Star r) = showReg r ++ "*"
instance Show Reg where
show = showReg
evalPostfix :: String -> Reg
evalPostfix = head . foldl comb []
where
comb :: [Reg] -> Char -> [Reg]
comb (x:y:ys) '|' = (Or y x) : ys
comb (x:y:ys) '&' = (Concat y x) : ys
comb (x:xs) '*' = (Star x) : xs
comb xs '@' = Epsilon : xs
comb xs s = (Literal s) : xs
-- Apply the shunting-yard algorithm to turn an infix expression
-- into a postfix expression.
shunt :: String -> String -> String -> String
shunt o p [] = (reverse o) ++ p
shunt o [] (x:xs)
| x == '(' = shunt o [x] xs
| x == '|' = shunt o [x] xs
| otherwise = shunt (x:o) [] xs
shunt o (p:ps) (x:xs)
| x == '(' = shunt o (x:p:ps) xs
| x == ')' = case (span (/= '(') (p:ps)) of
(as, b:bs) -> shunt (as ++ o) bs xs
| x == '|' = case (p) of
'(' -> shunt o (x:p:ps) xs
otherwise -> shunt (p:o) (x:ps) xs
| x == '*' = shunt (x:o) (p:ps) xs
| otherwise = shunt (x:o) (p:ps) xs
-- | Convert an infix expression to postfix
toPostfix :: String -> String
toPostfix = shunt [] []
-- | Evaluate an infix expression
eval :: String -> Reg
eval = evalPostfix . toPostfix
特别是,分流功能正在完成所有繁重的工作,是应该进行更改的地方。(这棵树可以很容易地在 evalPostfix 中构建。)
现在,我花了最后几个小时寻找解释如何做到这一点的教程,但没有任何运气。我想说我需要跟踪我有多少悬挂表达式,如果我会做任何会创建三个的事情,请插入一个“&”,但这似乎效率低下,我确信有更好的方法. 如果有人可以看到如何更改代码或可以指出我正确的方向,我将不胜感激。