在 R 中绘制表达式树

Question

我知道我可以使用 substitute 函数在 R 中创建表达式树。假设我生成了以下表达式树：

expT <- substitute(a+(2*b+c))

是否可以在 R 中可视化表达式树，生成如下内容：

我知道 ( 也是 R 中的一个函数，但我想在图中省略它。

Answer 1

这绝对有可能，但我不知道这样做的现有功能。也就是说，这是一个很好的练习。查看 Walking the AST with recursive functions（并阅读整章）以获取有关如何对表达式树进行操作的基本说明。

由此看来，剩下的就“相对”简单了：

对于每个节点，确定要打印的符号。
维护当前节点的（相对）坐标。递归表达式时，此坐标会根据您的操作进行更新；例如，您知道函数调用的参数需要在其调用下方居中，因此您可以相应地更新 y 坐标，然后根据参数的数量计算 x。运算符只是其中的一个特例。

最后，您可以使用这些符号以及它们计算出的坐标来绘制它们之间的相对关系。

Answer 2

这里有一些可能有用的代码和结果，但至少不能达到 "walk" "parse tree":

> parse( text="a+(2*b+c)")
expression(a+(2*b+c))
> parse( text="a+(2*b+c)")[[1]]
a + (2 * b + c)
> parse( text="a+(2*b+c)")[[1]][[1]]
`+`
> parse( text="a+(2*b+c)")[[1]][[2]]
a
> parse( text="a+(2*b+c)")[[1]][[3]]
(2 * b + c)
> parse( text="a+(2*b+c)")[[1]][[4]]
Error in parse(text = "a+(2*b+c)")[[1]][[4]] : subscript out of bounds
> parse( text="a+(2*b+c)")[[1]][[3]][[1]]
`(`
> parse( text="a+(2*b+c)")[[1]][[3]][[2]]
2 * b + c
> parse( text="a+(2*b+c)")[[1]][[3]][[2]][[1]]
`+`
> parse( text="a+(2*b+c)")[[1]][[3]][[2]][[2]]
2 * b
> parse( text="a+(2*b+c)")[[1]][[3]][[2]][[3]]
c
> parse( text="a+(2*b+c)")[[1]][[3]][[2]][[2]][[1]]
`*`
> parse( text="a+(2*b+c)")[[1]][[3]][[2]][[2]][[2]]
[1] 2
> parse( text="a+(2*b+c)")[[1]][[3]][[2]][[2]][[3]]
b

我以为我在 R-help 或 r-devel 中看到过 Thomas Lumley 或 Luke Tierney 的帖子是这样做的，但到目前为止还没有找到它。我确实找到了 @G.Grothendieck 的帖子，它以编程方式分离了您可能构建的解析树：

 e <- parse(text = "a+(2*b+c)") 
my.print <- function(e) { 
  L <- as.list(e) 
  if (length(L) == 0) return(invisible()) 
  if (length(L) == 1) 
     print(L[[1]]) 
     else sapply(L, my.print) 
return(invisible()) } 
my.print(e[[1]])
#----- output-----
`+`
a
`(`
`+`
`*`
[1] 2
b
c

Answer 3

以下是大部分内容。它模仿 pryr:::tree 递归地检查调用树，然后分配 data.tree 节点。我更喜欢 igraph 但它不能容忍重复的节点名称（例如 + 出现两次）。我也无法 dendrogram 标记根以外的任何分支。

#install.packages("data.tree")
library(data.tree)

make_tree <- function(x) {
  if (is.atomic(x) && length(x) == 1) {
    as.character(deparse(x)[1])
  } else if (is.name(x)) {
    x <- as.character(x)
    if (x %in% c("(", ")")) {
      NULL
    } else {
      x
    }
  } else if (is.call(x)) {
    call_items <- as.list(x)
    node <- call_items[[1]]
    call_items <- call_items[-1]
    while (as.character(node) == "(" && length(call_items) > 0) {
      node <- call_items[[1]]
      call_items <- call_items[-1]
    }
    if (length(call_items) == 0) 
      return(make_tree(node))
    call_node <- Node$new(as.character(node))
    for (i in 1:length(call_items)) {
      res <- make_tree(call_items[[i]])
      if (is.environment(res))
        call_node$AddChildNode(res)
      else
        call_node$AddChild(res)
    }
    call_node
  } else
    typeof(x)
}

tree <- make_tree(quote(a+(2*b+c)))
print(tree)
plot(as.dendrogram(tree, edgetext = T), center = T, type = "triangle", yaxt = "n")

给出合理的文本输出：

      levelName
1 +            
2  ¦--a        
3  °--+        
4      ¦--*    
5      ¦   ¦--2
6      ¦   °--b
7      °--c

和一张图片。乘法符号没有出现在中间树节点中（我不明白为什么），但除此之外，我认为这可以完成工作。

Answer 4

这是一种利用函数 utils::getParseData 并借鉴为 parser package 编写的函数并使用 igraph 进行视觉处理的方法。链接函数几乎可以满足您的要求，但是 getParseData 函数返回的数据在叶子上有空白节点和数字 values/symbols/operators 等。如果您尝试解析函数或三元表达式或更复杂的东西，这很有意义。

此函数只是根据解析数据创建边列表。

## https://github.com/halpo/parser/blob/master/R/plot.parser.R
## Modified slightly to return graph instead of print/add attr
parser2graph <- function(y, ...){
    y$new.id <- seq_along(y$id)
    h <- graph.tree(0) + vertices(id = y$id, label= y$text)
    for(i in 1:nrow(y)){
        if(y[i, 'parent'])
            h <- h + edge(c(y[y$id == y[i, 'parent'], 'new.id'], y[i, 'new.id']))
    }
    h <- set_edge_attr(h, 'color', value='black')
    return(h)
}

下一个函数通过删除所有“(){}”和剩余的间隙来折叠解析树。这个想法是首先将所有标签在树中向上移动一个级别，然后剪掉叶子。最后，嵌套表达式 ('(){}') 中的所有间隙都被 creating/destroying 边移除。我将 brackets/braces 的嵌套层级移除的边缘涂成蓝色。

## Function to collapse the parse tree (removing () and {})
parseTree <- function(string, ignore=c('(',')','{','}'), ...) {
    dat <- utils::getParseData(parse(text=string))
    g <- parser2graph(dat[!(dat$text %in% ignore), ])
    leaves <- V(g)[!degree(g, mode='out')]                             # tree leaves
    preds <- sapply(leaves, neighbors, g=g, mode="in")                 # their predecessors
    vertex_attr(g, 'label', preds) <- vertex_attr(g, 'label', leaves)  # bump labels up a level
    g <- g - leaves                                                    # remove the leaves
    gaps <- V(g)[!nchar(vertex_attr(g, 'label'))]                      # gaps where ()/{} were
    nebs <- c(sapply(gaps, neighbors, graph=g, mode='all'))            # neighbors of gaps
    g <- add_edges(g, nebs, color='blue')                              # edges around the gaps
    g <- g - V(g)[!nchar(vertex_attr(g, 'label'))]                     # remove leaves/gaps
    plot(g, layout=layout.reingold.tilford, ...)
    title(string, cex.main=2.5)
}

一个例子，嵌套表达式略多。动画展示了原始树是如何倒塌的。

## Example string
library(igraph)
string <- "(a/{5})+(2*b+c)"

parseTree(string,  # plus some graphing stuff
          vertex.color="#FCFDBFFF", vertex.frame.color=NA,
          vertex.label.font=2, vertex.label.cex=2.5,
          vertex.label.color="darkred", vertex.size=25,
          asp=.7, edge.width=3, margin=-.05)

在 R 中绘制表达式树

Plotting expression trees in R

plot

r

expression-trees