Setul 13

Problema 1 Scrieți o implementare pentru tipul de date abstract stivă folosind liste simplu înlănțuite. Asigurați-vă că programul invert.c funcționează tot așa cum funcționa cu implementarea bazată pe tablou. Nu aveți voie să modificați codul din stiva.h și din invert.c

/*********** * stiva.h * ***********/#ifndef STIVA_H#define STIVA_H /* Initializeaza stiva. Aloca resursele necesare pentru gestionarea stivei. */void init(void); /* Adauga un element in stiva. */void pune(double d); /* Extrage un element din stiva si returneaza valoarea lui. */double scoate(void); /* Returneaza elementul din varful stivei, fara a-l extrage din stiva. */double ia_varf(void); /* Returneaza 1 daca stiva e goala si 0 altfel. */int gol(void); /* Returneaza 1 daca stiva e plina si 0 altfel. */int plin(void); /* Extrage toate elementele din stiva si elibereaza orice resurse au fost folosite pentru memorarea elementelor. */void goleste(void); #endif

/************ * invert.c * ************/ #include <stdio.h>#include "stiva.h" int main(void){ int i; double element; init(); for (i = 0; i < 10; i++) { element = i; printf("punem %lf ... ", element); pune(element); printf("[PUS]\n"); } while (!gol()) { printf("urmeaza sa scoatem %lf ... ", ia_varf()); scoate(); printf("[SCOS]\n"); } goleste(); /* stiva deja e goala in acest punct, dar e important sa dam ocazia sa se elibereze resursele folosite de stiva. */ return 0;}

Start

#include <stdio.h>

#include <stdlib.h>

#include "stiva.h"

#define MAX 100

static double stiva[MAX];

static int varf;

void init(void)

{

int i;

for (i = 0; i < MAX; i++) {

stiva[i] = 0;

}

varf = -1;

}

int plin(void)

{

return (varf == MAX - 1);

}

int gol(void)

{

return (varf == -1);

}

void pune(double nr)

{

if (plin()) {

printf("Eroare: stiva este plina\n");

} else {

stiva[++varf] = nr;

}

}

double scoate(void)

{

if (gol()) {

printf("Eroare: stiva este goala\n");

return -1;

}

return stiva[varf--];

}

double ia_varf(void)

{

if (gol()) {

printf("Eroare: stiva este goala\n");

return -1;

}

return stiva[varf];

}

void goleste(void)

{

while (!gol()) {

scoate();

}

}

int main()

{

printf("Hello world!\n");

return 0;

}

Problema 2 (Evaluarea unei expresii în notație poloneză) Notația poloneză (sau postfix) este un mod de scriere a expresiilor în care ordinea operatorilor și a operanzilor este schimbată față de cea dintr-o expresie uzuală. În notația uzuală (numită și infix) o expresie are forma: operand operator operand. În notația postfix (poloneză) expresia este scrisă sub forma: operand operand operator.

De exemplu:

a + b devine în notație poloneză a b +

(a - b) * c devine a b - c *

a - b * (c + d) devine a b c d + * -

Scrieți un program care evaluează expresii postfix cu operanzi numere reale, expresii citite dintr-un fișier de intrare, câte una pe fiecare rând. Folosiți la implementare tipul de date abstract stiva definit mai sus. Pentru a testa programul puteți folosi fișierul

pentru care rezultatul trebuie să fie

Rezolvare notatie prefix+tastatura:

#include <stdlib.h>

#include <stdio.h>

#include <ctype.h>

int getcsp(void) { scanf(" "); return getchar(); }

int expr(void)

{

int c, n;

switch (c = getcsp()) {

case '+': return expr() + expr();

case '-': n = expr(); return n - expr();

case '*': return expr() * expr();

case '/': n = expr(); return n / expr();

default: if(isdigit(c)) { ungetc(c, stdin); scanf("%d", &n); return n; }

else { fputs("trebuie numar sau operator", stderr); return -1; }

}

}

int main(void)

{

printf("%d\n", expr());

return 0;

}