Enunțul problemei expresie, de clasa a 10-a, dată în 2011 la OJI, se găsește pe .campion, PbInfo și InfoArena.

Rezumat expresie

Se dă o așa-numită expresie aritmetică ponderată, formată din unul sau mai multe k-șiruri, paranteze rotunde și paranteze pătrate. Un k-șir este o enumerare de k numere despărțite prin virgulă. Expresia se evaluează în modul următor:

  • Un k-șir neîncadrat între paranteze (de tipul 0) se evaluează drept suma elementelor șirului.
  • Un k-șir încadrat între paranteze rotunde (de tipul 1) se evaluează drept secvența de sumă maximă a șirului.
  • Un k-șir încadrat între paranteze pătrate (de tipul 2) se evaluează drept mediana șirului (elementul aflat pe poziția [(k + 1) / 2]) în șirul sortat, k-șirurile fiind indexate de la 1.

Trebuie să determinăm câte numere întregi conține expresia dată și care este valoarea ei.

Soluție expresie

Prima cerință necesită doar un strtok pe șirul de caractere dat. Delimitatorii sunt toate caracterele ce pot apărea în expresie, cu excepția cifrelor. Însă, pentru că trebuie să și evaluăm expresia, în funcția pentru parsarea întregilor (getInt) am și incrementat numărul lor, răspunzând la ambele cerințe simultan.

Pentru evaluarea expresiei am folosit recursivitate indirectă. O abordare cu stivă era mai greu de implementat pentru că trebuie lucrat cu vectori. Am scris o funcție eval ce parcurge șirul cu un pointer global p (nu pointer ca tip de date), ce indică poziția curentă din șir. Când se ajunge la o paranteză rotundă, se apelează funcția getRot, care evaluează un k-șir de tipul 1. În cazul unei paranteze pătrate, se apelează funcția getPtr, care evaluează un k-șir de tipul 2.

Pentru k-șirurile de tipul 1, am determinat secvența de sumă maximă prin programare dinamică. Este vorba despre simpla relație de recurență dp[i] = max(v[i], dp[i - 1] + v[i]). Pentru k-șirurile de tipul 2, este de ajuns să sortăm șirul și să-i accesăm elementul din mijloc pentru a-i afla mediana.

Până aici soluția folosește niște algoritmi obișnuiți pentru o județeană de a 10-a. DAR, mai trebuie să fim atenți la un aspect. Vectorii unde sunt stocate șirurile procesate de fiecare funcție ocupă multă memorie, iar în combinație cu numărul maxim de apeluri simultane pe stivă (egal cu adâncimea maximă a expresiei), provoacă stack overflow pe multe teste. Vectorii pot fi declarați cumva global pentru a scăpa de overflow? În niciun caz. Vectorii trebuie să fie locali; altfel același vector ar fi folosit de sute de apeluri în același timp.

Soluția este să folosim vectori din STL. De exemplu, în timp ce se evaluează un k-șir de tipul 1, se ajunge în interiorul lui la unul de tipul 2, care trebuie evaluat înainte de a citi restul elementelor din primul. Deci, de ce să păstrăm de la începutul apelului spațiu și pentru ele printr-un vector static? Folosind un vector alocat dinamic, întotdeauna pe stivă va fi reținut numărul minim de valori necesare.

Sursă C++ expresie

Dacă ai vreo nedumerire cu privire la problema expresie, lasă un comentariu și te voi ajuta 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!