Schläger: implementieren Funktion (eval t)

Question

Ich versuche, eine Funktion (eval t) zu implementieren, führt die folgenden:

Beispiele:

(eval '(2 * (1 + 2))) -> 6 

(eval '((3 - (4/2)) * 2) -> 2 

Was ich habe, so weit ist:

(define (inner lst) 
    ((cond 
    ((equal? (second lst) '+) +) 
    ((equal? (second lst) '-) -) 
    ((equal? (second lst) '*) *) 
    ((equal? (second lst) '/) /)) 
    (first lst) (third lst))) 


(define (eval t) 
    (cond 
    ((and (number? (first t)) (number? (third t))) (inner t)) 
    ((list? (third t)) (eval `(,(first t) ,(second t) ,(inner (third t))))) 
    ((list? (first t)) (eval `(,(inner (first t)) ,(second t) ,(third t)))))) 

Es funktioniert für:

(eval '(1 + (1 + 2))) -> 4 

(eval '((1 + 1) + (2 + 2))) -> 6 

aber es funktioniert nicht für Fälle wie:

(eval '((1 + 1) + (1 + (1 + 1)))) 

Jede Hilfe wird sehr geschätzt werden!

Answer 1

Der Trick hier ist zu verstehen, dass Ausdrücke genau zwei Formen annehmen können: eine rohe Nummer Datum oder eine Liste, die eine Operation enthält. Als pseudo-Grammatik, bedeutet, dass jeder Ausdruck der folgenden Struktur entsprechen müssen:

 
expression = number 
      | (expressionoperatorexpression) 

operator = + 
      | - 
      | * 
      |/

Dies bedeutet, dass die eval Funktion der Lage sein muss entweder Art Ausdruck zu handhaben, so dass alle diese funktionieren sollte:

(eval 7)    ; => 7 
(eval '(1 + 6))  ; => 7 
(eval '((2 * 3) + 1) ; => 7 

Es gibt zwei Dinge, von diesem zu nehmen:

1. Die eval Funktion han Lage sein sollte, dle rohe Zahlen, nicht nur Listen mit Operatoren.
2. Es gibt nur genau zwei Fälle, die in der eval Funktion behandelt werden müssen.

Das bedeutet, dass eval wahrscheinlich so etwas wie die folgende Form annehmen sollte:

; eval : expression? -> number? 
(define (eval expr) 
    (cond 
    [(number? x) ???] 
    [else  ???])) 

Ihr viele verschiedene Fälle für die Implementierung von eval sind zu komplex und sind nicht erforderlich. Sie sollten die Struktur einer Liste nicht überprüfen müssen, da sie immer genau auf die gleiche Weise ausgewertet werden muss: eval die linke Seite, dann eval die rechte Seite, dann beide Seiten zusammen mit der Operation in der Mitte kombinieren. Dies funktioniert, weil, wenn eval mit Zahlen umgehen kann, dann etwas wie (eval 3) korrekt funktioniert.

Das hört sich nach einem Hausaufgabenproblem an, deshalb werde ich nicht die genaue Umsetzung verraten, aber hoffentlich sollte das ausreichen, um Sie in die richtige Richtung zu weisen.