Evaluation of Reverse Polish Notation in R

Question

What is the most efficient algorithm to evaluate a RPN notation in R?

Here is the question: suppose we have

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

How to write a general purpose function that evaluates any input RPN ?

Does R have stack data structure ?

Thanks for your hints

Answer 1

To my knowledge there isn't a dedicated stack structure that you can push/pop etc., but you can easily use lists to achieve the same effect. Here we use the same list to hold the input RPN string and to act as the stack:

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]]      
}

Let's test:

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

Something more challenging:

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

A breakdown of the logic:

• make a list with numbers and symbols representing the operators
• walk down list left to right
  • if hit a number, just move pointer to next value (the stuff to the left of the pointer is our stack, so we are using part of our input list as the stack!)
  • if hit a function, combine the two items to the left of the pointer (i.e. rightmost items in stack) into one call on the stack, and reset pointer

That's it. We take advantage that R stores calls as nested lists and that +, -, etc. are just functions in R so this works very naturally.

Assumptions:

• functions are assumed binary (i.e. no unary - or +, among other things)
• the user is only inputing valid functions
• the numbers are integers (this will extend to numerics if you tweak the regular expression)
• the RPN string needs to make sense (i.e. c("3", "+", "3")) will fail.