在字符串 R 代码中查找嵌套括号的最大深度

Question

我无法完成此 R 代码。我们得到一个带有括号的字符串，如下所示 “（（（X））（（（Y））））” 我们需要找到平衡括号的最大深度，如上例中的 4。由于'Y'被4个平衡括号包围。

如果括号不平衡则return -1 我的代码如下所示：

current_max = 0
max = 0
def = function (S){
  n=S
  for (i in nchar(n))
    if (is.element('(',n[i]))
    {
      current_max <- current_max + 1   
    }
  if (current_max > max)
      {
        max <- current_max
      }
  else if (is.element(')',n[i]))
  {
    if (current_max > 0)
    {
      current_max <- current_max - 1
    }
    else
    {
      return -1
    }
  }
  if (current_max != 0)
  {
    return -1
  }
  return (max)
}

但是当我调用函数 def("(A((B)))") 时，答案应该是 2。但是每次它都显示 0，即使括号不平衡。我不确定代码是否正确或错误在哪里。我正在努力学习 R，所以请耐心等待。谢谢

Answer 1

如果x <- "( ((X)) (((Y))) )"，则删除所有非括号并拆分为字符...

y <- unlist(strsplit(gsub("[^\(\)]", "", x), ""))

y
 [1] "(" "(" "(" ")" ")" "(" "(" "(" ")" ")" ")" ")"

然后最大嵌套就是+1(for()和-1(for))的最高累加和...

z <- max(cumsum(ifelse(y=="(", 1, -1)))

z
 [1] 4

如果括号不平衡则 sum(ifelse(y=="(", 1, -1))) 将不等于零。

Answer 2

这是三个解决方案。它们都是向量化的，即输入 x 可以是字符向量，它们都正确处理了没有括号的情况。

1) gsubfn 包中的 strapply/proto strapply 匹配函数运行中作为第二个参数给出的正则表达式 fun 在原型对象 p 中，它也应该传递给 strapply。 p 中的 pre 函数初始化输入 x 的每个分量的计算。 proto 对象可用于保留过去匹配项的内存（此处 lev 是嵌套级别），允许进行计数。我们向每个字符串附加一个任意字符，这里 "X" 以确保始终至少有一个匹配项。如果我们知道没有零长度字符串输入，则可以省略。 sapply 使用 Max 取最大 returned 深度或 returns -1 如果没有余额。

library(gsubfn) # also pulls in proto

# test input
x <- c("(A((B)))", "((A) ((())) (B))", "abc", "", "(A)((B)", "(A(B)))")


p <- proto(pre = function(.) .$lev <- 0,
           fun = function(., x) .$lev <- .$lev + (x == "(") - (x == ")") )
Max <- function(x) if (tail(x, 1) == 0 && min(x) == 0) max(x) else -1
sapply(strapply(paste(x, "X"), ".", p), Max)
## [1]  3  4  0  0 -1 -1

2) Reduce 这是一个基本的解决方案。它利用了 (1) 中的 Max。

fun <- function(lev, char) lev + (char == "(") - (char == ")")
sapply(x, function(x) Max(Reduce(fun, init = 0, unlist(strsplit(x, "")), acc = TRUE)))


    (A((B))) ((A) ((())) (B))              abc                  
           3                4                0                0 
     (A)((B)          (A(B))) 
          -1               -1

3) strapply/list 另一种可能性是提取括号和 return 为 ( 和 [= +1 或 -1 27=] 使用 strapply 和替换列表。然后运行 cumsum 和 Max（从上面）。

library(gsubfn)

fn$sapply(strapply(x, "[()]", list("(" = +1, ")" = -1), empty = 0), ~ Max(cumsum(x)))
## [1]  3  4  0  0 -1 -1

在字符串 R 代码中查找嵌套括号的最大深度

Find maximum depth of nested parenthesis in a string R code

nested

r

parentheses