r - R中反波兰符号的求值

Question

在R中评估RPN符号最有效的算法是什么？

这里的问题是:假设我们有

c("4", "13", "5", "/", "+") -> (4 + (13 / 5)) -> 6

如何编写可评估任何输入RPN的通用函数？

R是否具有堆栈数据结构？

谢谢你的提示

Answer 1

据我所知，没有可以推/弹出等的专用堆栈结构，但是您可以轻松地使用列表来达到相同的效果。在这里，我们使用相同的列表来保存输入的RPN字符串并充当堆栈:

rpn <- function(v) {
  l <- lapply(v, function(x) if(grepl("^\\d+$", x)) as.numeric(x) else as.name(x))
  i <- 1
  while(length(l) >= i) {
    if(!is.numeric(l[[i]])) {
      l[[i - 2]] <- as.call(l[c(i, i - 2, i - 1)])
      l[i:(i - 1)] <- NULL
      i <- i - 1
    } else i <- i + 1
  }
  l[[1]]      
}

让我们测试一下:

v <- c("4", "13", "5", "/", "+")
rpn(v)              # un-evaluated reparsed expression
# 4 + 13/5
eval(rpn(v))        # which you can evaluate
# [1] 6.6

更具挑战性的东西:

v <- c("4", "13", "+", "5", "/", "8", "-", "10", "3", "+", "*")
rpn(v)
# ((4 + 13)/5 - 8) * (10 + 3)
eval(rpn(v))
# [1] -59.8

逻辑分割:

列出包含代表运算符

的数字和符号的列表

从左到右浏览列表

如果命中一个数字，只需将指针移至下一个值(指针左侧的内容是我们的堆栈，因此我们将输入列表的一部分用作堆栈!)

如果命中一个函数，则将指针左侧的两个项(即堆栈中最右边的项)组合到堆栈中的一个调用中，并重置指针

就是这样。我们利用R将调用存储为嵌套列表的优势，并且 +， -等仅是R中的函数，因此这很自然地起作用。

假设:

函数被假定为二进制函数(即，不包含一元-或+等)

用户仅输入有效功能

数字是整数(如果您调整正则表达式，它将扩展为数字)

RPN字符串需要理解的

(即c("3", "+", "3"))将失败。