字符串中的有效括號（Haskell實現）

-1

問題是要檢查字符串中的括號是否正確關閉。對於Haskell的實現，到目前爲止我有以下。它看起來很尷尬。我正在尋找更多的「Haskell風格」或更優雅的實現。字符串中的有效括號（Haskell實現）

import Data.List 

isValidParentheses :: String -> Bool 
isValidParentheses = isValidHelper . (filter isParenthese) 

getIndex :: (Eq a) => a -> [a] -> Int 
getIndex c xs = getOut (elemIndex c xs) 
    where getOut (Just x) = x 
     getOut Nothing = -1 

isLeftParenthese :: Char -> Bool 
isLeftParenthese c = (getIndex c "{[(") /= -1 

isRightParenthese :: Char -> Bool 
isRightParenthese c = (getIndex c "}])") /= -1 

isParenthese :: Char -> Bool 
isParenthese c = isLeftParenthese c || isRightParenthese c 


isValidHelper :: String -> Bool 
isValidHelper xs = helper xs [] 
    where helper (x:xs) []  | isRightParenthese x = False 
          | otherwise = helper xs [x] 
     helper [] st = null st 
     helper (x:xs) (s:ss) | isLeftParenthese x = helper xs (x:s:ss) 
           | ((getIndex x "}])") /= (getIndex s "{[(")) = False 
           | otherwise = helper xs ss

感謝

來源

2015-01-04 Yan Zhu

'getIndex c xs/= -1'可以被'elem c xs'替代。在此之後，應該刪除'getIndex'：如果需要，可以直接比較'elemIndex'的'Maybe Int'結果。將'Nothing'轉換爲'-1'非常不合Haskellish：最好它是無用的（在這種情況下），最壞的情況是它促使程序員忘記「未找到」的情況。最後，您的代碼不會處理其他字符，例如'a（b [c] d）e'無效 - 這是有意的，對嗎？ – chi

[檢查一個字符串是否包含平衡括號]的可能重複（http://stackoverflow.com/questions/7209260/checking-if-a-string-consists-of-balanced-parenthesis） –

遍歷字符串
店在年底
在堆疊開口括號
流行匹配括號出棧

檢查，如果堆棧是空的

isValid = loop [] 
    where 
    match '(' ')' = True 
    match '{' '}' = True 
    match '[' ']' = True 
    match _ _ = False 

    loop st [] = null st 
    loop st (x:xs) 
     | x `elem` "([{" = loop (x:st) xs 
     | x `elem` ")]}" = case st of 
     open : st' | match open x -> loop st' xs 
     _ -> False -- unmatched close 
     | otherwise = loop st xs

來源

2015-01-04 23:27:19

字符串中的有效括號（Haskell實現）

回答

相關問題