Suma per sobre o per sota en una pila X92251

Statement

html

Implementeu una funció RECURSIVA que, donada una pila d’enters sint, i donada una pila d’strings sstring de la mateixa mida que conté només mots above o below, retorna una nova pila d’enters de la mateixa mida que les dues anteriors tal que, per a cada posició p:

Si sstring té above a posició p, llavors la pila retornada té a posició p la suma dels elements per sobre o igual a posició p en sint.
Si sstring té below a posició p, llavors la pila retornada té a posició p la suma dels elements per sota o igual a posició p en sint.

// Pre: sint i sstring tenen la mateixa mida, i sstring només conté
//      mots de {"above", "below"} un nombre arbitrari de cops i
//      en un ordre arbitrari.
// Post: Retorna una pila d'enters de la mateixa mida que sint i sstring.
//       Per a cada posició p, si sstring té "above" a posició p, llavors
//       la pila retornada té a posició p el resultat de sumar tots els
//       elements de sint a posició per sobre o igual a p,
//       i si per contra sstring té "below" a posició p, llavors
//       la pila retornada té a posició p el resultat de sumar tots els
//       elements de sint a posició per sota o igual a p.
stack<int> sumAboveOrBelow(stack<int> sint, stack<string> sstring);

Aquí tenim un exemple d’entrada i sortida de la funció, a on es mostren els elements de les piles des del fons de la pila a l’esquerra fins al top de la pila a la dreta:

8 5 1 7 1
below above above above below
=>
8 14 9 8 22

Observació Només cal enviar el procediment demanat; el programa principal serà ignorat.

Observació

La vostra funció i subfuncions que creeu han de treballar només amb piles. Heu de trobar una solució RECURSIVA i eficient del problema. Podeu crear funcions auxiliars per tal de millorar l’eficiència.

Una implementació no eficient que superi honestament els jocs de proves públics us permetrà obtenir una nota raonable, però per a superar tots els jocs de proves i obtenir la màxima nota haureu de pensar en una manera de fer-ho eficient.

Sample session

7 6 6 3
above above below above
=>
22 15 19 3

3 1
above above
=>
4 1

7 7 7 9
below below above above
=>
7 14 16 9

3 3 8 10 3 10 4 2 10 2
below above above below below above below below above above
=>
3 52 49 24 27 28 41 43 12 2

8 5 1 7 1
below above above above below
=>
8 14 9 8 22

3 7 6 5 7 7 4 5 3 5 5 4 8 7
below above above above above above above above above above below below below below
=>
3 73 66 60 55 48 41 37 32 29 57 61 69 76

5 2 10 1 9 3 7 10 1
above below below below above below below above below
=>
48 7 17 18 30 30 37 11 48

8 8 8 3 2 7 6 5 1 2 8 2 10 8 8 7 7 10 9
above below below below below above above above above above above above above below above above above below above
=>
119 16 24 27 29 90 83 77 72 71 69 61 59 78 41 33 26 110 9

10 10 9 6 10 4 6 2 6 9 9 1 1
above below below below below below below above above below above above below
=>
83 20 29 35 45 49 55 28 26 72 11 2 83

5 8 4 8 10
below below above above below
=>
5 13 22 18 35

Information

Author: PRO1
Language: Catalan
Official solutions: Unknown.
User solutions: C++