Rezolvare completă PbInfo #1067 Expresie7

Prin convenţie numim expresie aritmetică ponderată o expresie construită astfel:

  • expresia conţine numere întregi de cel mult 2 cifre despărţite prin virgulă;
  • numim k-şir o enumerare de k numere despărţite prin virgulă (k≥1);
  • o expresie poate conţine unul sau mai multe k-şiruri;
  • expresia foloseşte paranteze rotunde şi paranteze drepte.

Evaluarea expresiei se face după următoarele reguli:

  • dacă expresia conţine un singur k-şir atunci rezultatul expresiei este reprezentat de suma celor k numere. Exemplu: 2,4,1 = 2+4+1 = 7.
  • dacă în expresie întâlnim un k-şir delimitat de paranteze rotunde rezultatul evaluării acestui k-şir va fi reprezentat de suma maximă a unui secvenţe ce aparţine k-şirului, unde prin secvenţă se înţelege o succesiune de numere aflate pe poziţii consecutive în şir. Exemplu: (-2,4,-1,3,-2,-3,2) => secvenţa de sumă maximă este 4,-1,3 a cărui sumă este egală cu 6.
  • dacă în expresie întâlnim un k-şir delimitat de paranteze pătrate, elementele k-şirului fiind numerotate 1,2,..,k, rezultatul evaluării acestui k-şir va fi reprezentat de valoarea elementului aflat pe poziţia [(k+1)/2] dacă şirul ar fi ordonat crescător (mediana unui şir). Exemplu: [-2,9,10,3,5] => şirul ordonat [-2,3,5,9,10] => iar valoarea expresiei este egală cu 5.
  • evaluarea parantezelor se face dinspre interior spre exterior.

Cerinţă

Fiind dată o expresie aritmetică ponderată să se determine:

  • câte numere întregi conţine expresia aritmetică;
  • care este valoarea expresiei aritmetice.

Date de intrare

Fișierul de intrare expresie7.in conține pe prima linie un şir de caractere ce reprezintă o expresie aritmetică ponderată.

Date de ieșire

Fișierul de ieșire expresie7.out va conține pe prima linie numărul de numere întregi din expresie, iar pe următoarea linie va fi scris un număr ce reprezintă valoarea expresiei aritmetice.

Restricții și precizări

  • expresia se consideră corectă
  • 3 ≤ lungimea unei expresii ≤ 100000
  • şirul prin care se codifică expresia poate să conţină doar următoarele caractere: cifre, paranteze rotunde şi pătrate deschise şi închise, caracterul virgulă, caracterul minus
  • pentru rezolvarea primei cerinţe se obţine 20% din valoarea fiecărui test
  • 10% dintre teste nu vor conţine paranteze
  • 20% dintre teste nu vor conţine paranteze imbricate

Exemplul 1

expresie7.in

2,(2,-4,1,-1,5)

expresie7.out

6
7

Explicație

Expresia conţine 6 numere întregi
Valoarea expresiei este: 2+5 = 7

Exemplul 2

expresie7.in

(3,-1,4),[2,3,1,8]

expresie7.out

7
8

Explicație

Valoarea expresiei este: 6+2 = 8

Exemplul 3

expresie7.in

(2,-1,[1,2,3,4,5],-4,1)

expresie7.out

9
4

Explicație

Valoarea expresiei este: (2,-1,3,-4,1) = 4

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Expresie7:

/*
    Eugen Nodea
    Implementare stive
    Mediana - quickselect()
    Complexitate O(n)
*/
# include <fstream>
# include <cstring>
# include <algorithm>
# define nmax 100002
# define swap(a,b) temp=(a);(a)=(b);(b)=temp;
using namespace std;

ifstream f("expresie7.in");
ofstream g("expresie7.out");

char ex[nmax];
int L,i,k,x,j,kd,kr,y,rst[nmax/2],dst[nmax/2];
int st[nmax],sm,Max,nr=0,S,sol;

//determinare mediana - alg. asemanator quicksort
int quickselect(int *a, int st, int dr, int k)
{
  int i,ir,j,l,mid;
  int p,temp;

  l=st; ir=dr;
  for(;;)
  {
    if (ir <= l+1)
    {
          if (ir == l+1 && a[ir] < a[l]) { swap(a[l],a[ir]); }
          return a[k];
    }
    else {
          mid=(l+ir) >> 1;
          swap(a[mid],a[l+1]);
          if (a[l] > a[ir])   { swap(a[l],a[ir]);   }
          if (a[l+1] > a[ir]) { swap(a[l+1],a[ir]); }
          if (a[l] > a[l+1])  { swap(a[l],a[l+1]);  }

          i=l+1; j=ir;
          p=a[l+1];
          for (;;)
          {
            do i++; while (a[i] < p);
            do j--; while (a[j] > p);
            if (j < i) break;
            swap(a[i],a[j]);
          }
          a[l+1]=a[j]; a[j]=p;
          if (j >= k) ir=j-1;
          if (j <= k) l=i;
        }
  }
}

int main()
{
    f.getline(ex,nmax);
    L=strlen(ex);
    i=k=kd=kr=0;
    while (i < L)
    {
        if (ex[i] == '(')
        {
            ++i; rst[++kr]=k+1;
        }
        if (ex[i] == '[')
        {
            ++i; dst[++kd]=k+1;
        }
        if ('0' <= ex[i] && ex[i] <= '9' || ex[i] == '-')
        {
                        if (ex[i] == '-') sm=-1, ++i;
                                     else sm=1;
            x=0;
            while ('0' <= ex[i] && ex[i] <= '9' && i < L)
            {
                x=x*10+ex[i]-'0';
                ++i;
            }
            st[++k]=sm*x;
            if (ex[i] == ',') ++i,++nr;
        }
        if (ex[i] == ')')
        {       //determinam subsecventa de suma maxima
            x=rst[kr];
            S=st[x]; Max=S;
            for (j=x+1; j<=k; ++j)
                            {
                                if (S+st[j] < st[j]) S = st[j];
                                                else S += st[j];
                                if (S > Max) Max=S;
                            }
            k=x; --kr; st[k]=Max;
            ++i;
        }
        if (ex[i] == ']')
        {   //determinam mediana
                        x=dst[kd];
                        y=quickselect(st,x,k,(k+x)/2);
                        k=x; --kd; st[k]=y;
                        ++i;
                }
        if (ex[i] == ',') ++i,++nr;
    }

    for (i=1, sol=0; i<=k; ++i)
    {
        sol += st[i];
    }
    g<< nr+1 <<'\n'<< sol <<'\n';
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1067 Expresie7

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1067 Expresie7 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!