Poate c\u0103 problemele de parsing vi se par un chin, \u00eentruc\u00e2t, cel mai probabil, v\u0103 g\u00e2ndi\u021bi la o rezolvare folosind un stack, o metod\u0103 care necesit\u0103 foarte mult timp la implementare \u0219i care este greu de \u00een\u021beles. <\/p>\n\n\n\n
\u00cen acest articol v\u0103 propun o metod\u0103 care este mai u\u0219or de \u00een\u021beles \u0219i care folose\u0219te recursivitatea indirect\u0103.<\/p>\n\n\n\n
<\/p>\n\n\n\n
Ne vom concentra asupra problemei #2638<\/a> de pe pbinfo<\/a>. Ni se cere s\u0103 evalu\u0103m o expresie ce con\u021bine numere naturale si operatorii +, – \u0219i *. S\u0103 arunc\u0103m o privire asupra unei astfel de expresii: 24-3*7+11*2-1<\/p>\n\n\n\n Putem observa c\u0103 expresia este format\u0103 din mai mul\u021bi termeni, lega\u021bi prin operatorii + sau -. Fie T1 = 24, T2 = 3*7, T3 = 11*2 \u0219i T4 = 1. Expresia se va transforma \u00een: T1-T2+T3-T4 . Deja totul devine mai simplu. Urm\u0103torul pas este s\u0103 observ\u0103m faptul c\u0103, la r\u00e2ndul lor, termenii sunt forma\u021bi dintr-un singur num\u0103r sau dintr-un produs de numere, legate prin operatorul *. Aceste numere le vom numi factori (de exemplu, T2 = 3*7, deci putem spune c\u0103, T2 = F1*F2, unde F1 are valoarea 3, iar F2 valoarea 7).<\/p>\n\n\n\n Cheia \u00een rezolvare st\u0103 \u00een scrierea unor func\u021bii care s\u0103 returneze aceste rezultate par\u021biale legate prin operatori cu aceea\u0219i prioritate (de exemplu, suma \u0219i diferen\u021ba au aceea\u0219i prioritate). Mai mult, pentru a putea ob\u021bine sume\/diferen\u021be\/produse, avem nevoie, evident, de valori, deci vom avea \u00eenc\u0103 o func\u021bie care s\u0103 ne returneze aceste numere (factori).<\/p>\n\n\n\n Func\u021bia care calculeaz\u0103 sumele sau diferen\u021bele arat\u0103 \u00een felul urm\u0103tor:<\/p>\n\n\n\n \u00cen mod similar va ar\u0103ta \u0219i func\u021bia care calculeaz\u0103 produsele dintre numere:<\/p>\n\n\n\n \u00cen final, vom scrie \u0219i func\u021bia care ne va returna valoarea factorilor:<\/p>\n\n\n\n Dac\u0103 problema ne spunea c\u0103 pot exista \u0219i paranteze rotunde, unde se g\u0103seau alte expresii de evaluat, putem modifica func\u021bia factor()<\/em> \u00een felul urm\u0103tor:<\/p>\n\n\n\n <\/p>\n\n\n\n Ultimul pas este apelul din main, adic\u0103:<\/p>\n\n\n\n <\/p>\n\n\n\n Este foarte importat s\u0103 definim \u00eenainte antetul fiec\u0103rei func\u021bii, deoarece, at\u00e2t func\u021bia eval()<\/em>, c\u00e2t \u0219i func\u021bia factor()<\/em>, apeleaz\u0103 func\u021bii care, p\u00e2n\u0103 la momentul respectiv, nu au fost definite. Le vom scrie antetul odat\u0103 cu variabilele globale, apoi le vom defini.<\/p>\n\n\n\n <\/p>\n\n\n\n Sper ca acest articol s\u0103 v\u0103 ajute \u00een rezolvarea problemelor de parsing. Func\u021biile pot suferi modific\u0103ri de la problem\u0103 la problem\u0103, \u00eens\u0103, este important s\u0103 \u00een\u021belege\u021bi principiul din spate, pentru a putea rezolva c\u00e2t mai multe probleme de acest tip.<\/p>\n\n\n\n <\/p>\n\n\n\n Autor: Pirnog Theodor Ioan<\/p>\n\n\n\n Colegiul National „B. P. Hasdeu”, Buz\u0103u<\/p>\n","protected":false},"excerpt":{"rendered":" Poate c\u0103 problemele de parsing vi se par un chin, \u00eentruc\u00e2t, cel mai probabil, v\u0103 g\u00e2ndi\u021bi la o rezolvare folosind … <\/p>\n","protected":false},"author":3,"featured_media":312,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[],"class_list":["post-304","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-probleme"],"_links":{"self":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/304","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/comments?post=304"}],"version-history":[{"count":8,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/304\/revisions"}],"predecessor-version":[{"id":313,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/304\/revisions\/313"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/media\/312"}],"wp:attachment":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/media?parent=304"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/categories?post=304"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/tags?post=304"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}long long eval(){\n\n long long ans = termen(); \/\/ lu\u0103m valoarea primului termen\n\n while(s[p] == '+' || s[p] == '-'){\n\n if(s[p] == '+'){\n\n p++; \/\/ trecem de '+'\n ans += termen();\n\n }else{\n\n p++; \/\/ trecem de '-'\n ans -= termen();\n\n }\n\n }\n\n return ans;\n}\n\n<\/pre>\n\n\n\nlong long termen(){\n\n long long ans = factor(); \/\/ lu\u0103m valoarea primului factor\n\n while(s[p] == '*'){\n\n p++; \/\/ trecem de '*'\n ans *= factor();\n\n }\n\n return ans;\n}\n\n<\/pre>\n\n\n\nlong long factor(){\n\n long long x = 0;\n\n while(s[p] >= '0' && s[p] <= '9')\n x = x * 10 + (s[p] - 48), p++;\n\n return x;\n}<\/pre>\n\n\n\nlong long factor(){\n\n long long x = 0;\n\n if(s[p] == '('){\n\n p++; \/\/ trecem de '('\n x = eval(); \/\/ evalu\u0103m subexpresia\n p++; \/\/ trecem de ')'\n\n return x;\n }\n\n while(s[p] >= '0' && s[p] <= '9')\n x = x * 10 + (s[p] - 48), p++;\n\n return x;\n}<\/pre>\n\n\n\ncout << eval();<\/pre>\n\n\n\n
string s;\nint p;\n\nlong long eval();\nlong long termen();\nlong long factor();<\/pre>\n\n\n\n