Ocena odwrotnej notacji polskiej w R

Question

Jaki jest najskuteczniejszy algorytm do oceny zapisu RPN w R?

Oto pytanie: załóżmy, że mamy

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

Jak napisać funkcję ogólnego przeznaczenia, który ocenia każdą RPN wejścia?

Czy R ma strukturę danych stosu?

Dzięki za podpowiedzi

Answer 1

Do mojej wiedzy nie jest dedykowany struktura stosu, który można wcisnąć/pop itd., Ale można łatwo wykorzystać list do osiągnięcia tego samego efektu. Tutaj używamy tej samej listy trzymać wejścia RPN ciąg i działać jako stosu:

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

Test Miejmy:

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

Coś trudniejsze:

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

Podział logika:

• utworzyć listę z numerami i symboli reprezentujących podmioty
• spacer w dół listy lewej do prawej
  • jeśli trafienie numer, wystarczy przesunąć kursor do następnej wartości (towar na lewo od wskaźnika jest nasz stos, więc używamy część naszego wejścia lista jako stos!)
  • jeśli trafisz w funkcję, połącz dwa elementy po lewej stronie wskaźnika (np. pozycje skrajnie prawe w stosie) do jednej rozmowy na stosie, i zresetować wskaźnik

To wszystko. Korzystamy z tego, że R przechowuje połączenia jako listy zagnieżdżone i że +, - itp. Są po prostu funkcjami w R, więc to działa bardzo naturalnie.

Założenia:

• funkcje zostały przejęte binarny (tj żadnych unarne - lub + między innymi)
• użytkownik inputing tylko ważne funkcje
• liczby są liczbami całkowitymi (będzie rozciągać się numeryczne, jeśli dostosujesz wyrażenie regularne)
• Łańcuch RPN musi mieć sens (tj. c("3", "+", "3")) zakończy się niepowodzeniem.