Evaluate reverse Polish notation in R

Question

What is the most efficient algorithm for evaluating RPN notation in R?

Here's the question: suppose that

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

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

Does R have a stack data structure?

Thanks for your tips.

Answer 1

As far as I know, there is no special stack structure that you can press / pop, etc., but you can easily use lists to achieve the same effect. Here we use the same list to hold the input string of the RPN and act as a stack:

 rpn <- function(x) { 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 the 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 complicated:

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

Logic Failure:

• make a list with numbers and characters representing operators
• go down left
  • if you click a number, just move the pointer to the next value (the material to the left of the pointer is our stack, so we use part of our input list as a stack!)
  • if you press a function, combine the two elements to the left of the pointer (that is, the rightmost elements on the stack) into one call on the stack and the reset pointer

What is it. We take advantage of the fact that R stores calls as nested lists, and + , - , etc. - these are just functions in R, so it works very naturally.

Assumptions:

• Functions
• are considered binary (that is, there are no unary - or + , by the way)
• user enters only valid functions
• numbers are integers (this will apply to numerical values ​​if you adjust the regex)
• RPN string should make sense (i.e. c("3", "+", "3") ) will not be executed.