Vjezbe 3: Stack

U ovim vjezbama radimo s infix, postfix i prefix notacijom.


Fileovi:
-------------------------------------
	evaluacija.c - evaluacija postfix izraza pomocu stacka
	in2post.c - Dijkstrin algoritam za prebacivanje infix -> postfix

Opisi ovih algoritama nalaze se u fileu "opisi_algoritama.c"

Nap: Buduci da konkretno izvodjenje programa sadrzi puno tehnickih detalja nevezanih uz same algoritme i strukturu stack (npr, baratanje s operatorima, operandima, itd.), najbolje je najprije prouciti odgovarajuce algoritme u pseudokodu i rijesiti pokoji zadatak pomocu stacka, a tek nakon toga krenuti s konkretnom implementacijom.

Zadaci:
-------------------------------------
1) Dijkstrinim algoritmom pretvorite sljedece infix izraze u postfix, a zatim ih evaluirajte pomocu stacka:
	a) (2+3) * (4+5)^2
	b) 2^4*3 - 2*2*2 + 3*4

2) Razmislite o tome kako biste algoritme modificirali kada bismo umjesto postfix notacije koristili prefix.


Popis tipova i funkcija u ATP Stack:
-------------------------------------
elementtype
Stack
void StMakeNull(Stack *S);
elementtype StTop(Stack S);
void StPush(elementtype x, Stack *S);
void StPop(Stack* S);
int StEmpty(Stack S);


Opis programa:
-------------------------------------
Za pokretanje programa "postfix.c" i "in2post.c" potrebno je implementirati ATP stack.
Kako na stacku zelimo cuvati i operande i operatore, u ovom slucaju koristimo sljedeci elementtype:

typedef struct{
	int operand;
	char operator;
	int prioritet;
} operator_ili_operand;

typedef operator_ili_operand elementtype;

Ako se radi o operandu, u char operator spremamo 'n', a u int operand stvarnu vrijednost operanda.
Ako se radi o operatoru, u char operator spremamo odgovarajuci znak ('+', '-', itd.)

Imamo nekoliko pomocnih funkcija; najvaznije su:

1) int ucitaj_liniju(elementtype *L);

Ova funkcija omogucuje da s tipkovnice unesemo niz operatora/operanada odvojenih razmacima, npr:
2 * 3 - 4 * 5
Funkcija ove operande/operatore sprema u niz L te vraca duljinu nastalog niza.

2) void soio(elementtype x);

stavi-operator-ili-operand: omogucuje ispis elementa x, neovisno o tome je li operator ili operand

3) elementtype evaluiraj(elementtype x, char c, elementtype y);

Ako je c operator, a x i y operandi, ova funkcija racuna odgovarajucu operaciju x c y.
Primjer: za x == 3, y == 4, c == '+', funkcija vraca 3 + 4, tj. 7

Nap: program trenutno podrzava samo operacije s int-ovima, stoga operaciju '/' shvacamo kao cjelobrojno dijeljenje)