兄弟姐妹和他们的孩子在字符串中的顺序

Question

我用括号格式表示一个树,其中每个级别与其上层分开{.树是二进制的(它可以有一个或两个孩子).我想按字母顺序订购相同级别的兄弟姐妹,同时保留他们的孩子和子孩子.这意味着,只需按字母顺序对每个同级别的2个孩子进行排序.我有一个包含输入树的字符串str1,我想在字符串str2中获得有序.

这是一个例子:

str1<-"{A{C{D{E}}}{B{F{G{H{I}}}}}}"

在订单处理的第一阶段,我希望str2如下:

{A{B{F{G{H{I}}}}}{C{D{E}}}}

只需在C及其所有孩子和B及其所有子孩子之间切换然后继续...(因为C和B都是他们父亲的第二级A.只有一个'{'在B和C之间分开A)我该怎么办？

Answer 1

我认为约翰的评论可能在正确的轨道上 - 做你想做的最好的方法,就是把你的字符串转换成适当的面向对象的树结构.随后,您可以将数据操作为树而不是字符串,一旦完成了操作,您可以根据需要将树结构恢复为字符串格式. data.tree我们是一个理想的包装,因为它已经内置了强大的树操作工具(包括一个排序功能),所以没有重新发明轮子.

幸运的是,这种转换在递归时相对容易.以下是将字符串转换为以下内容的代码data.tree:

library(data.tree)

peek.next.node <- function(x){  #Helper function reads the next node (as a string) out of the char vector x
  return(paste(x[2:(which(x=="{"|x=="}")[2]-1)],collapse=""))
}

remove.next.node <- function(x){ #Helper function removes node at the start of the char vector x
  return(x[(which(x=="{"|x=="}")[2]):length(x)])
}

recurse.from.char.vector <- function (x,n){ #inspect input char vector, adding nodes to n if x starts with '{' and returning if x starts with '}'.  Will loop until return
  i<-1
  while(x[1]=="{"){
    new.node.name <- paste(c(peek.next.node(x),"_",i),collapse="")
    child.n <- n$AddChild(new.node.name,label=peek.next.node(x))
    i <- i+1
    x <- remove.next.node(x)
    x <- recurse.from.char.vector(x,child.n)
  }
  return (x[2:length(x)])
}

string.to.tree <- function(x){ #returns head node for a finished tree by calling a recursive parse function
  x.vec <- strsplit(x,"")[[1]]
  head <- Node$new(peek.next.node(x.vec),label = peek.next.node(x.vec))
  recurse.from.char.vector(remove.next.node(x.vec),head) 
  return(head)
}

请注意,即使您的节点标签不止一个字符,此代码也会起作用,并且它也适用于非二叉树.

回到树中的字符串会更容易,因为data.tree对象更自然地适用于递归:

recurse.to.char.vector <- function(n){
  return.vec <-unlist(c("{",n$label))
  if(length(n$children)>0)return.vec <- unlist(c(return.vec,sapply(n$children,recurse.to.char.vector)))
  return.vec <- unlist(c(return.vec,"}"))
  return(return.vec)
}

tree.to.string <- function(n){
  char.vector <- recurse.to.char.vector(n)
  return (paste(char.vector,collapse=""))
}

以下是您的示例:转换,排序和转换回来:

> str1<-"{A{C{D{E}}}{B{F{G{H{I}}}}}}"
> test.tree <- string.to.tree(str1)
> str1
[1] "{A{C{D{E}}}{B{F{G{H{I}}}}}}"
> test.tree$Sort("label")
> tree.to.string(test.tree)
[1] "{A{B{F{G{H{I}}}}}{C{D{E}}}}"

需要注意的是,你想要做的Sort,并tee.to.string在单独的行-在一些极端情况(如单节点"树")Sort()将返回一个NULL值

在评论中,您询问了"看到"没有子ID号的树.这可以通过levelName在树的属性上设置格式化功能来实现.基本上,无论何时print树,树都会遍历每个节点并打印levelName属性 - 您可以像任何其他打印属性一样对其进行格式化.

示例格式函数:

strip.num.from.levelName <- function(x){ #If string ends with _something, strip out everything after the last underscore
  x.vec <- strsplit(x,"")[[1]]
  which.sep <- which(x.vec == "_")
  if(length(which.sep)<=0)
    return(x)
  else 
    return(paste(x.vec[1:(tail(which.sep,1)-1)],collapse=""))
}

完成此功能后,将其应用于树SetFormat(test.tree,"levelName",strip.num.from.levelName).这将删除树的所有简单打印输出中的数字