Algoritm pentru descrierea DOT a arborelui sintactic al unei expresii
Ne bazăm pe formatul prefixat canonic (impus de predicatul write_canonical
din Prolog); de exemplu, expresia 2+3*4+5 are formatul +(+(2,*(3,4)),5) (separând cu ',' subarborele stâng de cel drept şi parantezând subarborii).
Numerotăm operatorii şi operanzii, imitând metoda clasică de reprezentare pe un tablou a unui arbore binar (fiii nodului N sunt 2N şi 2N+1, N≥1). Pentru nodul curent N creem înregistrarea DOT N[label="op"] unde op este operatorul/operandul respectiv. Când citim '(' - dublăm N-ul curent (urmează fiul stâng), iar când citim ',' - incrementăm N-ul curent (urmează fiul drept); în ambele cazuri, creem înregistrarea DOT a muchiei: N/2 -- N. Când întâlnim ')' - înjumătăţim N-ul curent (regăsind N-ul părintelui, de la care va urma eventual o nouă ramură).
Arbori aritmetici şi expresii uzuale
Rezultatul - afişarea în anumite formate, a unei expresii - este banal (cum şi anticipasem) şi se putea obţine şi direct (fără clasele ArTree şi Climb de aici - instrumentând în schimb un algoritm "shunting yard"); dar nu rezultatul ca atare ne-a interesat, ci procedeul de analiză bazat pe proprietăţile operatorilor ("precedence climbing" - metodă ingenioasă, compactă şi eficientă de analiză sintactică) - împreună desigur, cu modelarea în C++ plecând de la modelul de arbori aritmetici ArTree.
Limbajul expresiilor aritmetice
De prin clasa a V-a, se tot deprind mecanisme de analiză sintactică şi morfologică a unui text (la "Limba română" şi la orele de "limbi străine"); iar aceste mecanisme servesc şi cazului mai simplu, al expresiilor algebrice (tot "texte", având asociate anumite "înţelesuri").
Propoziţiile corecte sunt constituite din anumite "părţi de vorbire", cu respectarea anumitor "reguli gramaticale" - a vedea programa şcolară pentru Limba şi literatura romănă, clasele V - VIII.
Un limbaj oarecare presupune deasemenea, anumite "părţi de vorbire" specifice şi un set de "reguli gramaticale" pe baza căruia se pot produce "propoziţiile" (sau "programele") corecte.
Trasarea şi restrângerea căutării, în metoda backtracking
Pentru analiza unui program bazat pe backtracking putem folosi (fie şi numai în scop instructiv) următorul procedeu (în loc de instrumente de tip "debugger"): rezumăm programul respectiv la un caz tipic (să producă o singură soluţie, nu pe toate) şi intercalăm în anumite puncte două "linii de control" (afişând nodul şi adâncimea). Rezultă un fişier text conţinând întreaga istorie a căutării soluţiei - poate foarte voluminos, dar putem angaja utilitare ca less şi grep pentru a depista ramificări inutile (de evitat în cursul căutării soluţiei).
Pânzele drumurilor hamiltoniene pe graful calului 5x5
Prelucrăm (prin comenzi perl) un fişier "informativ" şi reducem (printr-un program Python) cele 1728 de drumuri hamiltoniene ale calului de şah pe tabla 5x5, la un tablou javaScript conţinând cele 864 de drumuri "directe"; apoi, realizăm o funcţie javaScript care produce un element <canvas> pe care se vizualizează drumul indicat (pe tabla a cărei dimensiune este indicată).
vezi Cărţile mele (de programare)