檢查匹配的括號

我想寫一個代碼，給定一個括號列表，我會檢查命令是否有效。檢查匹配的括號

爲了簡單起見，定義了以下數據類型。

datatype par = LPAR | RPAR 
type pList = par list

我直到現在是：

fun valid(nil:plist): bool = true 
| valid([Lpar]) = false 
| valid([Rpar]) = false 
| valid([Lrap,Rpar) = true 
| valid(L::L1) =

例如，「（（）（）」 - > [LPAR，LPAR，RPAR，LPAR，RPAR]將返回false 你可以看到括號是字符串格式的，我很困惑，因爲我必須檢查兩件事：左邊（等於左邊）和每個（匹配a）。如果是，那麼我需要做一些幫手功能

你能否給我提供關於我的幫手功能應該是的信息或者這是否實施？ ty

來源

2014-09-27 Sarah cartenz

第一種模式是OK。第二，第三和第四模式是無用的，雖然沒有正式的錯誤。您似乎試圖將整個括號列表對待。試着表達這個規則：一個右括號在一個左括號之後，所以遞歸地（在一個開 - 關對內，可能有嵌套的開 - 關對）。這是作業嗎？ – Hibou57 2014-09-27 23:21:36

我沒有嘗試這個在REPL但它應該是這個樣子

fun valid_paren xs : bool = 
fun aux (xs, ctr) = case xs of 
    [] => ctr = 0 
    | (x:xs') => case x of 
      '(' => aux (xs', ctr+1) 
      ')' => aux (xs', ctr-1) 
      _ => aux (xs', ctr) 
in 
    aux (xs, 0)

來源

2014-10-01 08:10:21 fr1c710n

我發現了一種方法來解決我的問題，通過計算括號。邏輯是這樣的：

我從0開始，如果我找到一個左邊的P我加1，其他的I我減1.一旦我輸入-1我立即返回假，因爲我不能有一個右邊的P先來。然後我遞歸。如果最終輸出爲0，則它是真實的，因爲這意味着每個左邊的p匹配右邊的p。

Q.E.D

來源

2014-09-27 23:48:56

檢查匹配的括號

回答

相關問題