检查匹配的括号

我想写一个代码，给定一个括号列表，我会检查命令是否有效。检查匹配的括号

为了简单起见，定义了以下数据类型。

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

检查匹配的括号

回答

相关问题