Valutazione della notazione polacca inversa in R

Question

Qual è l'algoritmo più efficiente per valutare una notazione RPN in R?

Ecco la domanda: supponiamo di avere

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

come scrivere una funzione di uso generale che valuta ogni RPN di ingresso?

R dispone di una struttura di dati stack?

Grazie per i vostri suggerimenti

Answer 1

A mia conoscenza non esiste una struttura di stack dedicato che si può spingere/pop ecc, ma si può facilmente utilizzare gli elenchi per ottenere lo stesso effetto. Qui usiamo la stessa lista per contenere la stringa RPN di input e di agire come la pila:

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

prova di Let:

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

qualcosa di più impegnativo:

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

La ripartizione dei la logica:

• creare un elenco con numeri e simboli che rappresentano gli operatori
• camminare lungo elenco da sinistra a destra
  • se colpito un numero, basta spostare il puntatore al valore successivo (la roba alla sinistra del puntatore è il nostro stack, in modo che si utilizza parte della nostra ingresso lista come stack!)
  • se si preme una funzione, combina i due elementi a sinistra del puntatore (es. elementi più a destra nello stack) in una chiamata sullo stack, e Reset puntatore

Questo è tutto. Ci avvaliamo del fatto che R memorizza le chiamate come elenchi nidificati e che +, -, ecc. Sono solo funzioni in R, quindi funziona in modo molto naturale.

Ipotesi:

• funzioni sono assunte binario (cioè nessun unari - o +, tra le altre cose)
• l'utente è solo inputing funzioni validi
• i numeri sono interi (questo si estenderanno valori numerici se si modifica l'espressione regolare)
• la stringa RPN deve avere senso (ovvero c("3", "+", "3")) non riuscirà.