Predavanje 10 - Stogovi

1. Uvod

Danasnju diskusiju cemo motivirati polazeci od problema racunanja aritmetickih izraza u kojima se pojavljuju aritmeticke operacije zbrajanja i oduzimanja cijelih brojeva poput:
5*(((9+8)*(4*6))+7)

Racunanje ovakvih izraza svakako ukljucuje racunanje i spremanje medjurezultata: prvo izracunamo 9+8 pa spremimo 17 onda racunamo 4*6 itd. Ovakav pristup nama je intuitivno jasan ali nije jasno kako ga implementirati u C-u. Osnovni problem kako odrediti redoslijed racunanja unutar pojedinih zagrada u izrazu npr. Trebamo li prvo racunati (9+8) ili (4*6) itd. Zapravo treba nam bolji nacin zapisivanja aritmetickih izraza.
Aritmeticki izrazi napisani na standardni nacin kao gore su u infiks obliku. Drugi nacin zapisivanja ovih izraza je postfiks oblik (koji se jos zove i poljska notacija). U toj notaciji isti izraz izgleda ovako

5 9 8+4 6**7+*

Algoritam za prelazak iz postfiks u infiks notaciju je sljedeci:

sukcesivno mijenjamo postfiks: infiks: ab+ (a+b) ab* (a*b)
dok ne iscrpimo sve takve trojke. Primjer:
59 8+4 6**7+* 5(9+8)4 6**7+* 5(9+8)(4*6)*7+* 5((9+8)*(4*6))7+* 5(((9+8)*(4*6))+7)* 5*(((9+8)*(4*6))+7)
Gornji algoritam pokazuje da postoji jednoznacno odredjeni infiks oblik za dani postfiks oblik i pokazuje da u postfiks notaciji ne trebamo brinuti za zagrade tj. za svaki operand operatori su potpuno odredjeni. Algoritam pokazuje takodjer kako se iz infiks notacije dobije postfiks notacija jedinstveno (samo idemo u obratnom smjeru). (Vidi zadatak 2 za implementaciju u C-u.)

Sada smo spremni opisati algoritam za racunanje aritmetickih izraza dan u postfiks notaciji.

Citamo izraz s lijeva na desno i kada naidjemo na broj spremamo ga na stog, kada naidjemo na operaciju izvadimo zadnja dva spremljena broja na stog i na njih primjenimo operaciju na koju smo upravo naisli, obrisemo ih sa stoga te vratimo rezultat nazad na stog. Ako je izraz napisan korektno na kraju na hrpi ostane samo jedan broj koji predstavlja rezultat.

Primjer: Izracunajte vrijednost aritmetickog izraza danog u postfiks obliku 5 9 8+4 6**7+*

iduci znak operacija stog
5spremanje na stog 5
9spremanje na stog 9
5
8spremanje na stog 8
9
5
+
  • uzimanje zadnja dva broja sa stoga: 9 i 8 (izraz nije korektno zapisan ako nema barem dva elementa na stogu u ovom trenutku)
  • racunanje 9+8=17
  • brisanje 9 i 8 sa stoga
  • spremanje rezultata 17 na stog
17
5
4spremanje na stog 4
17
5
6spremanje na stog 6
4
17
5
*
  • uzimanje zadnja dva broja sa stoga: 6 i 4 (izraz nije korektno zapisan ako nema barem dva elementa na stogu u ovom trenutku)
  • racunanje 6*4=24
  • brisanje 6 i 4 sa stoga
  • spremanje rezultata 24 na stog
24
17
5
*
  • uzimanje zadnja dva broja sa stoga: 24 i 17 (izraz nije korektno zapisan ako nema barem dva elementa na stogu u ovom trenutku)
  • racunanje 24*17=408
  • brisanje 24 i 17 sa stoga
  • spremanje rezultata 408 na stog
408
5
7spremanje na stog 7
408
5
+
  • uzimanje zadnja dva broja sa stoga: 7 i 408 (izraz nije korektno zapisan ako nema barem dva elementa na stogu u ovom trenutku)
  • racunanje 7+408=415
  • brisanje 7 i 408 sa stoga
  • spremanje rezultata 415 na stog
415
5
*
  • uzimanje zadnja dva broja sa stoga: 415 i 5 (izraz nije korektno zapisan ako nema barem dva elementa na stogu u ovom trenutku)
  • racunanje 415*5=2075
  • brisanje 7 i 408 sa stoga
  • spremanje rezultata 415 na stog
2075
kraj unosa
  • provjerimo imamo li samo jedan broj na stogu
  • ako da, on je rezultat u ovom slucaju 2075
  • ispraznimo stog

2. Stog

Algoritam za racunanje podataka temeljio se na slozenom tipu podatka koji nazivamo stog. Gornji primjer sugerira funkcije koje ce raditi na stogu.



Stog sastavljen od cjelobrojnih podataka je slozeni tip podatka cije su osnove operacije:

/*inicijaliziramo stog od najvise max elemenata*/ void init(int max); /*dodajemo element na vrh stoga*/ void push(int novi); /* brisemo zadnje unijeti element liste element sa liste ako takav postoji */ int pop(); /*vraca nulu ako stog nije prazan, a inace neki cijeli broj razlicit od nule*/ int is_empty();
Ovu deklaraciju cemo staviti u zaglavlje stog.h

Primjedba: lako je generalizirati gornju definiciju stoga na druge tipove podataka jednostavne ili slozene. Mi nismo nastojali dati najopcenitiju mogucu definiciju.

Mi smo sada deklarirali stog, ali nismo specificirali kako ga treba implementirati.

3. Implementacija cjelobrojnog stoga

Mi cemo implementirati funkcije deklarirane u stog.h u datoteci stog.c koristeci vezane liste. Napomenimo da postoji implementacija u terminima polja.



#include<stdlib.h> #include "stog.h" typedef struct stog* veza; struct stog{ int a; veza iduci; }; static veza pocetak; /* oznacava pocetak liste koja reprezentira stog*/ void init(int max){ /* ova implementacija ne koristi varijablu max */ pocetak=NULL; } int is_empty(){ return pocetak==NULL; } void push(int novi){ veza x=(veza)malloc(sizeof *x); x->a=novi; x->iduci=pocetak; pocetak=x; } int pop(){ int i; veza t; if(pocetak) i=pocetak->a; t=pocetak->iduci; free(pocetak); pocetak=t; return i; }

4. Izracunavanje aritmetickih izraza danih u postfiks obliku

Program koji ucitava postfiks izraz sa komandne linije i izracunava njegovu vrijednost ukoliko je sam izraz korektno zadan. Potrebne su tri izvorne datoteke stog.h, stog.c, i postfiks.c ciju implementaciju dajemo nize.

prevodjenje programa: $gcc -o postfiks postfiks.c stog.c izvrsavanje programa: $postfiks "5 9 8+4 6**7+*" 2075 Uocimo navodne zankove oko argumenta. Oni postoje je mi koristimo praznine da specificiramo pojedine operande kada izraz nije jednoznacan. Radi jednostavnosti svi operandi su nenegativni cijeli brojevi.



#include<stdio.h> #include<string.h> #include "stog.h" /*funkcija greska ispisuje poruku na standardni output zavrsava izvrsavanje programa*/ void greska(char* poruka){ printf("%s\n", poruka); exit(1); } int main(int argc, char** argv){ char* izraz; int i, N, op1, op2; if(argc ==1) greska("Izraz koji se racuna je argument na komandnoj liniji!\n"); izraz=argv[1]; N=strlen(izraz); /*inicijaliziramo stog od najvise N elemenenata*/ init(N); /* implementiramo gornji algoritam za racunanje vrijednosti aritmetickog izraza u postfiks obliku */ /*analiziramo karaktere u izraz*/ for (i=0; i< N; i++){ switch (izraz[i]){ case '+': /* uzmemo dva operanda sa stoga koja su zadnja spremljena na stog */ if(is_empty()) greska("Ucitani izraz nije valjani postfiks oblik."); else op1=pop(); if(is_empty()) greska("Ucitani izraz nije valjani postfiks oblik."); else op2=pop(); push(op1+op2); continue; case '*': /* uzemo dva operanda sa stoga koja su zadnja spremljena na stog */ if(is_empty()) greska("Ucitani izraz nije valjani postfiks oblik."); else op1=pop(); if(is_empty()) greska("Ucitani izraz nije valjani postfiks oblik."); else op2=pop(); push(op1*op2); continue; case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': /*ucitali smo broj i zato ucitavamo brojeve dokle mozemo*/ op1=0; while(('0'<=izraz[i])&& (izraz[i]<='9')){ op1=10*op1+(izraz[i]-'0'); i++; } push(op1); i--; /*smanjimo i jer moramo analizirati posljednji izraz[i] zbog kojeg smo izasli iz while petlje */ continue; case ' ': /*mozemo ocekivati da su brojevi odvojeni prazninama*/ continue; default: /*ucitali smo karakter koji ne moze biti dio postfiks izraza*/ greska("Ucitani izraz nije valjani postfiks oblik."); continue; } } /*ako smo ovdje onda uzimamo element sa stoga*/ op1=pop(); /*ako je ostatak stoga prazan ispisujemo element*/ if(is_empty()) printf("%d\n", op1); else greska("Ucitani izraz nije valjani postfiks oblik."); return 0; }

5. Zadaci za DZ

1. Implemetirajte cjelobrojni stog koristeci polja.

2. Napisite program koji pretvara postfiks oblik u infiks oblik.

3. Implementirajte stog karaktera i koristeci taj stog napisite program koji pretvara infiks oblik u postfiks oblik. Uputa: Dijkstrin algoritam: cita se string znak po znak.

  1. Ucitajte iduci znak ako postoji.
  2. Ako se ucita broj ispisite ga.
  3. Ako se ucita lijeva zagrada stavite ju na stog.
  4. Ako se ucita operator tada
  5. Ako se ucita desna zagrada tada ispisite sve operator sa vrha stoga sve dok ne dodjete do lijeve zagrade. Lijevu zagradu uzeti sa stoga ali ne i ispisati.
  6. Ako postoji jos ulaznih znakova ponovite 1. Inace ispisite preostali sadrzaj stoga

4. Preradite postfiks.c tako da operandi mogu biti i negativni brojevi.

5. Preradite postfiks.c tako da dodate oduzimanje - i cjelobrojno dijeljenje koje oznacavamo sa /. Operandi su i dalje nenegativni.

6.* Napisite program tumac (eng. interpreter) za programski jezik kojem se program sastoji od niza pridruzivanja i jednog aritmetickih izraza. Ovaj jezik dopusta samo varijable koje su mala slova, svaka linija koda zavrsava ; i nalazi se u posebnom redu. Npr. program

x=1; y=x+1; x*(2y+1);
ispisuje 5 na standardni output.