Expresia de evaluare și Walking copac folosind polimorfism? (ala Steve Yegge)

În această dimineață, citeam Steve Yegge: Când Polimorfismul eșuează , când am venit o întrebare pe care un coleg de-a lui a folosit pentru a solicita potențiali angajați atunci când au venit pentru interviu la Amazon.

Ca un exemplu de polimorfism în   acțiune, să ne uităm la clasic   "eval" întrebare de interviu, care (ca   pe cât știu) a fost adus la Amazon   de Ron Braunstein. Întrebarea este   destul de bogată, așa cum reușește   probă o mare varietate de importante   abilități: design OOP, recursivitate, binar   copaci, polimorfism și timpul de execuție   tipare, abilități generale de codificare și (dacă   pe care doriți să o faceți extra greu)   parsarea teoriei.

     

La un moment dat, candidatul sperăm   îți dă seama că poți reprezenta un   expresia aritmetică ca binară   copac, presupunând că utilizați doar   operatori binari precum "+", "-",   "*", "/". Nodurile frunzelor sunt toate   numere și nodurile interne sunt   toți operatorii. Evaluarea   expresie înseamnă mersul pe copac. Dacă   candidatul nu realizează acest lucru,   le puteți conduce ușor la ele sau dacă   necesar, spune-le doar.

     

Chiar dacă le spui, e încă un an   o problemă interesantă.

     

Prima jumătate a întrebării, care   unii oameni (ale căror nume o voi face   protejați-vă de respirația mea pe moarte, dar de ei   inițialele sunt Willie Lewis) simt este a   Cerință de angajare dacă doriți să apelați   Sunteți un dezvoltator și de lucru la   Amazon, este cam greu.   întrebarea este: cum te duci de la un   expresia aritmetică (de ex   string), cum ar fi "2 + (2)" la un   expresie arbore. S-ar putea să avem un ADJ   provocare la această întrebare la unii   punct.

     

A doua jumătate este: să spunem asta   un proiect cu 2 persoane și partenerul dvs.,   pe care îl vom numi "Willie"   responsabil pentru transformarea   string expresie într-un copac. Primesti   partea ușoară: trebuie să decideți ce   clase Willie este de a construi   copac cu. O puteți face în orice   limbă, dar asigurați-vă că alegeți unul,   sau Willie vă va înmâna asamblarea   limba. Dacă se simte ornery, asta   va fi pentru un procesor care nu este   fabricat mai mult în producție.

     

Ai fi uimit de numărul de candidați   o faceți pe acesta.

     

Nu voi da răspunsul, dar a   Standard Bad Solution implică utilizarea   a unui comutator sau a unei stări de caz (sau doar   bun vechi de moda cascaded-ifs). A   O soluție mai ușoară implică   folosind o masă de indicatori de funcție,   și Probabil cea mai bună soluție   implică utilizarea polimorfismului. eu   vă încurajați să lucrați prin ea   cândva. Distracție!

Deci, să încercăm să abordăm problema în trei moduri. Cum te duci dintr-o expresie aritmetică (de exemplu într-un șir) cum ar fi "2 + (2)" la un arbore de expresie folosind cascaded-if, o tabelă de indicatori de funcție și/sau polimorfism?

Simțiți-vă liber să abordați una, două sau toate cele trei.

[actualizare: titlu modificat pentru a se potrivi mai bine cu cele mai multe răspunsuri au fost.]

0
fr hi bn
Pe baza răspunsului lui Mark Harrisson, am scris o implementare php
adăugat autor serdarsenay, sursa

12 răspunsuri

Polymorphic Tree Walking, Python version

#!/usr/bin/python

class Node:
    """base class, you should not process one of these"""
    def process(self):
        raise('you should not be processing a node')

class BinaryNode(Node):
    """base class for binary nodes"""
    def __init__(self, _left, _right):
        self.left = _left
        self.right = _right
    def process(self):
        raise('you should not be processing a binarynode')

class Plus(BinaryNode):
    def process(self):
        return self.left.process() + self.right.process()

class Minus(BinaryNode):
    def process(self):
        return self.left.process() - self.right.process()

class Mul(BinaryNode):
    def process(self):
        return self.left.process() * self.right.process()

class Div(BinaryNode):
    def process(self):
        return self.left.process()/self.right.process()

class Num(Node):
    def __init__(self, _value):
        self.value = _value
    def process(self):
        return self.value

def demo(n):
    print n.process()

demo(Num(2))                                       # 2
demo(Plus(Num(2),Num(5)))                          # 2 + 3
demo(Plus(Mul(Num(2),Num(3)),Div(Num(10),Num(5)))) # (2 * 3) + (10/2)

Testele fac doar construirea copacilor binari folosind constructori.

Structura programului:

clasă de bază abstractă: Nod

  • toate nodurile moștenesc din această clasă

clasă de bază abstractă: BinaryNode

  • toți operatorii binariți moștenesc din această clasă
  • Metoda
  • procesului face munca de evaluare a expresiei și returnarea rezultatului

clase operator binar: Plus, Minus, Mul, Div

  • două noduri copil, câte unul pentru subexpresiile din partea stângă și din partea dreaptă

clasa numerică: Num

  • deține o valoare numerică a nodului frunz, de ex. 17 sau 42
0
adăugat
Întrebarea a fost pentru un calcul aritmetic SUCH AS 2 + (2), nu calculul lui 2 + (2). Prin urmare, nu este prea inginer, dar răspunde la întrebare așa cum a fost intenționat.
adăugat autor Thomas Owens, sursa
"Aveți parte ușoară: trebuie să decideți ce clase Willie trebuie să construiască copacul".
adăugat autor vanja., sursa
Acest răspuns nu este la întrebarea "Cum te duci dintr-o expresie aritmetică (de exemplu într-un STRING), cum ar fi" 2 + (2) "... Unde se face demo-ul? Num (3)), Div (Num (10), Num (5)))) "Veniți de la acel alt program pe care nu-l vedem?
adăugat autor Guge, sursa
Acest răspuns este orbitor supra-inginizat. Întrebarea a fost pentru 2 + (2), nu un calcul aritmetic arbitrar. De asemenea, aceasta doar execută arborele, nu-l construiește.
adăugat autor ReaperUnreal, sursa

@Justin:

Uită-te la nota mea despre reprezentarea nodurilor. Dacă utilizați acea schemă, atunci

2 + (2)

pot fi reprezentate ca

           .
         /\
         2  ( )
             |
             2
0
adăugat

Reprezentarea nodurilor

Dacă vrem să includem paranteze, avem nevoie de 5 tipuri de noduri:

  • the binary nodes: Add Minus Mul Div
    these have two children, a left and right side

         +
       /\
    node   node
    
  • a node to hold a value: Val
    no children nodes, just a numeric value

  • a node to keep track of the parens: Paren
    a single child node for the subexpression

        ( )
         |
        node
    

Pentru o soluție polimorfă, trebuie să avem o astfel de relație de clasă:

  • Nod
  • BinaryNode: moștenire de la nod
  • Plus: moștenire de la nodul binar
  • Minus: moștenire de la nodul binar
  • Mul: moștenire de la nodul binar
  • Div: moștenire de la nodul binar
  • Valoare: moștenire de la nod
  • Paren: moștenirea de la nod

Există o funcție virtuală pentru toate nodurile numite eval (). Dacă apelați această funcție, aceasta va returna valoarea acestei subexpresii.

0
adăugat
În unele cazuri există. S-ar putea să aveți un instrument pentru a rescrie/recrea expresia originală și nu pentru a optimiza disponibilizările din expresia originală. Desigur, pentru cazul evaluării expresiei și obținerii răspunsului, sunteți corect.
adăugat autor Mark Harrison, sursa
Nu există niciun motiv pentru a include paranteze în arborele sintaxei abstracte.
adăugat autor Jonas Kongslund, sursa

Sau poate aceasta este adevărata întrebare:   cum poți reprezenta (2) ca BST?   Aceasta este partea care mă împiedică   up.

Recursivitatea.

0
adăugat

ar trebui să utilizeze un limbaj funcțional imo. Copacii sunt mai greu de reprezentat și de manipulat în limbile OO.

0
adăugat
Într-adevăr ? Aceasta este implementarea nativă c ++: clasa AST {vector copil; împingere involuntară (AST *);/* add child, trebuie apelat de la yacc/bison parser /AST eval ();/ calculează recursiv nodurile copil /dump șir (int = 0);/ aruncați în copac cu file * /};
adăugat autor Dmitry Ponyatov, sursa
Dar tu chiar în corpul eval (): când încerci să ddo naiv eval ca cuib [0]/* lchild */= cuib [0] -> eval() este eval. Nu știu cum să o urmăresc în cazul variabilelor împărțite între câteva expresii, dar numerele de foi pot fi doar șterse.
adăugat autor Dmitry Ponyatov, sursa
Am uitat? ca etichetă pentru nodul însuși în AST
adăugat autor Dmitry Ponyatov, sursa

String Tokenizer + LL (1) Parserul vă va da un arbore de expresie ... modul de polimorfism ar putea implica o clasă aritmetică abstractă cu o funcție "evaluate (a, b)", care este suprascrisă pentru fiecare operator implicat (Addition, Subtracție etc) pentru a returna valoarea corespunzătoare, iar arborele conține operatori cu număr întreg și operatori aritmetici, care pot fi evaluați printr-o traversare post (?) - pentru arborele.

0
adăugat

Acest lucru intră în teoria parsingului/compilatorului, care este un fel de gaură de iepure ... Cartea Dragon este textul standard pentru construirea compilatorului, și ia acest lucru la extreme. În acest caz special, doriți să construiți o gramatică fără context pentru aritmetică, apoi utilizați această gramatică pentru a analiza un arbore de sintaxă abstractă . Puteți apoi să repetați copacul, reducându-l de jos în sus (în acest moment aplicați polimorfismul/funcția indicatori/comutator pentru a reduce arborele).

Am găsit aceste note pentru a fi incredibil de util în compilator și teoria parsării.

0
adăugat
Iată un CFG minim pentru întrebarea inițială: S -> N N -> 2 N -> N O N -> (N) O -> - N
adăugat autor ReaperUnreal, sursa

Re: Justin

Cred că arborele ar arăta așa:

  +
/\
2  ( )
    |
    2

Practic, ai avea un nod "eval", care evaluează doar arborele de sub el. Acest lucru ar fi apoi optimizat pentru a fi doar:

  +
/\
2   2

În acest caz, nu sunt necesare paranteze și nu adăugați nimic. Ei nu adaugă nimic logic, așa că ar pleca.

0
adăugat

Nu voi da răspunsul, dar a   Standard Bad Solution implică utilizarea   a unui comutator sau a unei stări de caz (sau doar   bun vechi de moda cascaded-ifs). A   O soluție mai ușoară implică   folosind o masă de indicatori de funcție,   și Probabil cea mai bună soluție   implică utilizarea polimorfismului.

Ultimii douăzeci de ani de evoluție în interpreți pot fi văzuți ca și cum mergem în altă direcție - polimorfismul (de exemplu, interpreții metacirculari Smalltalk naivi) pentru a funcționa pointeri (implementări naive lisp, coduri filetate, C ++) pentru a comuta (interpreți de cod octet naiv) la JIT-uri și așa mai departe - care necesită fie clase foarte mari, fie (în limbi polimorfe singulare) dublu expediere, ceea ce reduce polimorfismul la un tip de caz și te întorci la prima etapă. Ce definiție a "celui mai bun" se utilizează aici?

Pentru lucruri simple, o soluție polimorfă este OK - Iată unul pe care l-am făcut mai devreme , dar fie stivuirea, fie octetul/comutarea sau exploatarea compilatorului de runtime este de obicei mai bună dacă sunteți, de exemplu, reprezentând o funcție cu câteva mii de puncte de date.

0
adăugat

Problema, cred, este că trebuie să analizăm perenthezele și totuși nu sunt un operator binar? Ar trebui să luăm (2) ca un singur simbol, care se evaluează la 2?

Parantezele nu trebuie să apară în arborele expresiei, dar ele afectează forma sa. De exemplu, arborele pentru (1 + 2) +3 este diferit de 1+ (2 + 3):

    +
  /\
  +   3
/\
1   2

impotriva

    +
  /\
  1   +
    /\
    2   3

Parantezele reprezintă un "indiciu" al parserului (de exemplu, pe superjoe30, pentru a "coborî în mod recursiv")

0
adăugat

Cred că întrebarea este despre cum să scrie un parser, nu evaluatorul. Sau, mai degrabă, cum să creați arborele de expresie dintr-un șir.

Declarațiile de caz care returnează o clasă de bază nu contează exact.

Structura de bază a unei soluții "polimorfe" (care este un alt mod de a spune, nu-mi pasă ce construiești cu asta, vreau doar să o extind cu rescrierea celui mai mic număr de cod posibil) este deserializarea unei ierarhii de obiecte dintr- cu un set (dinamic) de tipuri cunoscute.

Principalul element al implementării soluției polimorfe este acela de a crea o modalitate de a crea un obiect de expresie dintr-un matcher de tip, probabil recursiv. De exemplu, harta unei BNF sau a unei sintaxe similare unei fabrici de obiecte.

0
adăugat

Așa cum au menționat deja oamenii, atunci când utilizați arbori de expresie nu sunt necesare paranteze. Ordinea operațiilor devine trivială și evidentă atunci când vă uitați la un arbore de expresie. Parantezele sunt sugestii pentru parser.

În timp ce răspunsul acceptat este soluția la o jumătate din problemă, cealaltă jumătate - de fapt parsarea expresiei - este încă nerezolvată. De obicei, aceste tipuri de probleme pot fi rezolvate cu ajutorul unui href="http://en.wikipedia.org/wiki/Recursive_descent_parser" recursiv coborâre parser . Scrierea o astfel de parser este adesea un exercițiu distractiv, dar cele mai multe instrumente moderne pentru parsare limba va abstract departe pentru tine .

Parserul este, de asemenea, semnificativ mai greu dacă permiteți numerele cu puncte variabile în șirul dvs. A trebuit să creez un DFA pentru a accepta numerele cu virgulă mobilă în C - a fost o sarcină foarte amănunțită și detaliată. Amintiți-vă că punctele flotante valide includ: 10, 10., 10.123, 9.876e-5, 1.0f, .025, etc. Presupun că în interviu a fost făcută o anumită dispensație (în favoarea simplității și a scurtării).

0
adăugat