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 中的函数，所以这很自然。

假设：

• 假定函数是二进制的（即没有一元的-or+等​​）
• 用户只输入有效的功能
• 数字是整数（如果您调整正则表达式，这将扩展到数字）
• RPN 字符串需要有意义（即c("3", "+", "3")）将失败。