如何知道何時在正則表達式分析樹中插入串聯節點？

Question

我正在從事一個有趣的項目，涉及從正則表達式生成一個分析樹。我主要工作，但我掛在如何集成串聯。

*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內建立。）

現在，我花了最近幾個小時尋找一個教程，解釋如何做到這一點，但沒有任何運氣。我想說，我需要跟蹤我有多少懸掛式表情，如果我會做任何會產生三個的表情，請插入'&'，但這看起來效率低下，我確信有更好的方法。如果任何人都可以看到如何改變代碼或者可以指引我正確的方向，我將非常感激。

Answer 1

分流碼算法主要用於處理將中綴運算符轉換爲後綴運算符。兩個複雜因素是正則表達式語法已經有一個後綴運算符*，並且中綴連接運算符是隱式的。這些組合使得解析令人討厭。

「abcd」用中綴&怎麼看？它是一個& b & c & d。應該是postfix ab & c & d &或abcd & & &？第一個是左聯合，第二個是右聯。我聲稱第二個解析正則表達式更合適。

現在，a，b，c或d中的每一個都可以是括號中的正則表達式，並且每個可以後跟一個'*'。

我會考慮提高你的代碼添加& ......

更新：你的代碼是錯誤的

*Main> toPostfix' "a|bcd" 
"abcd|" 

我不能輕易修復bug並擴展它來添加&，所以我現在放棄。