Citat: |
Implementirajte a.t.p. STACK pomoću pointera i napišite potprogram koji logički izraz iz infix oblika prebacuje u prefix oblik. Problem trebate riješiti pomoću stoga. Ulazni podaci: string koji predstavlja logički izraz u infix obliku Izlazni podaci: prikaz istog izraza u prefix obliku Na primjer, za ulazne podatke: A|B&(C^E|D) treba ispisati: |A&B|^CED Napomena: &=AND, |=OR, ^=XOR, -=NOT; obratite pažnju na prioritete |
michelangelo (napisa): |
da ne otvaram novu temu:
imam problem kod implementacije BTREE pomoću polja, točnije kod funkcije node CREATE(labeltype l, BTREE TL, BTREE TR, BTREE *T) ne dolazim na ideju za to. pa ako neko može dat hint barem, bila bi zahvalna |
michelangelo (napisa): |
tnx. mislim da sam skopčala. još jedno pitanje zadatak mi je stvorit novo stablo koje se sastoji samo od korijenskog čvora, koji mora dobiti oznaku c. dal je ovaj kod dobar za to?
void make_new(BTREE *B, labeltype c) { BTREE Br,Bl; MAKE_NULL(&Br); MAKE_NULL(&Bl); node i=CREATE(c,Br,Bl,&B); } |
CROmpir (napisa): |
Imam jedno pitanje,
Kako u atp. BTREE, definirati LAMBDA?? i kako implementirati PARENT funkciju... hvala |
pravipurger (napisa): |
1. Kada implementiram LIST preko pointera u zadaći da li trebam napisati funkciju PREVIOUS() za koju skripta kaže da je neefikasna, ali dz kaže "potrebno napraviti sve funkcije koje su navedene kod definicije tog atp-a"?
2. Da li kad mi ćelija sadrži koeficijent, eksponent i pointer trebam pisati dvije funckije RETRIEVE1 i RETRIEVE2, jednu koja vraća koef, drugu koja vraća exp ili jednu koja će vraćati nešto drugo? |
CROmpir (napisa): |
Moze li mi netko pomoci oko implementacije funkcije PARENT u BTREE a.t.p-u pomocu pointera... Ne kuzim kako da to napravim...
U skripti sugerira da dodamo jos jedno celiju pointera na parent? I smijemo li to koristiti s obzirom da vise CREATE nije onakakva funkcija kakva bi trebala biti imala bi jos jedan parametar ako se ne varam... Ima li mozda nekakvu ideju ili moze bilo kakva pomoc... |
Kod: |
node CREATE(labeltype l, BTREE TL, BTREE TR, BTREE *Tptr){
*Tptr=(celltype *)malloc(sizeof(celltype)); (*Tptr)->label=l; (*Tptr)->leftchild=TL; (*Tptr)->rightchild=TR; return (*Tptr); } node INSERT_LEFT_CHILD ( labeltype l, node i, BTREE *T){ node novi; novi=CREATE(l,LAMBDA,LAMBDA,T); i->leftchild=novi; return (i->leftchild); } node INSERT_RIGHT_CHILD ( labeltype l, node i, BTREE *T){ node novi; novi=CREATE(l,LAMBDA,LAMBDA,T); i->rightchild=novi; return (i->rightchild); } |
CROmpir (napisa): | ||
Moze li mi netko pomoci oko nacina unosa BINARNOG STABLA...
Bio bih mu jako zahvalan posto me to jako muci... I imam pitanje u vezi implementacije, jel ovo u redu??
|
CROmpir (napisa): |
Aha, puno hvala, da sad sam skuzio...
Mozes li mi jos reci ili pomoci kako da omogucim korisniku unos podataka u stablo? Fakat nemam ideje, prvi put se susrecem s tim... |
Kod: |
Za ulazne podatke: 7 2 2 7 2 1 4 1 6 3 2 7 5 1 4 1 3 2 1 4 treba ispisati: 1 2 4 5 7 |
akolak (napisa): |
Ako prefix izraz napišemo unazad i računamo kao postfix oćemo dobit isto rješenje?
Dakle ako + * 13 2 -8 7 napisemo kao 8 7 - 13 2 * + pa izracnamo kao postfix? Naravno pitanje se odnosi na općeniti prefix izraz. EDIT: Bolje pitanje je jel smijemo to koristit? (Mislim da se dokaže indukcijom po broju operatora) |
matmih (napisa): | ||
2. U ATP postoji samo jedna funkcija RETRIEVE i samo tu morate implementirati, ona vraća element koji se nalazi na poziciji p u listi. Dakle vraća element, kojeg god tipa on bio u vašem zadatku. |
Kod: |
element1=RETRIEVE(p,L1); element2=RETRIEVE(q,L2); if(element1.exp==element2.exp) element3.koef=element1.koef |
Joker (napisa): |
kak se zaokruzi tip double, da mi ne ispisuje 3.00000 nego samo tri? zaboravih =D |
Sekanta (napisa): | ||
ja sam isto na taj nacin radila, hmmm |
Malina_1 (napisa): |
Program mi radi dobro ako u ulaznom podatku ne spomenem : ^, što je taj ^, mislim inače je to matematički simbol za &. Ali ovdje valjda nije. I kako idu prioriteti među logičkim simbolima? Unaprijed hvala nekome tko će odgovoriti na ovo pitanje. |
yellow submarine (napisa): | ||
Ako u zadatku piše:
Je li to znači da ispis mora nužno biti tim redoslijedom ili je točno i ako se ispiše npr. 12754 ? Hvala. |
Kod: |
void DEQUEUE (QUEUE *Q ptr) { celltype *temp; if (EMPTY(*Q ptr)) error("queue is empty"); else { temp = Q ptr->front; Q ptr->front = Q ptr->front->next; free(temp); } } |
Kod: |
void DEQUEUE (QUEUE *Q ptr) { celltype *temp; if (EMPTY(*Q ptr)) error("queue is empty"); else { Q ptr->front = Q ptr->front->next; free(Q ptr->front); } } |
Buki (napisa): | ||||
pitanje u vezi funkcije DEQUEUE kod implementacije reda pomocu pointera:
cemu sluzi ovaj temp? jel ne bi moglo samo biti:
|
Kod: |
typedef struct _celija { elementtype element; struct _celija *next; } celija; position MAKE_NULL_L(LIST *L) { *L = (celija*) malloc(sizeof(celija)); (*L)->next = NULL; return *L; } |
Fikus (napisa): | ||
Moze pomoc oko liste, ja imam implementaciju iz skripte pa me zanima di je tocno grecka
Dakle kod prvog mi ocita gresku kod elementtypea (expected specifier list before elementtype) i kod make null a i ostalih funkcija mi kaze da u mojoj strukturi nema člana koji se zove next i jos mi ocitava gresku za malloc, kaze :incompatibile implicit declaration of built-in function malloc Eto to bi bilo sve sto me zanima, dakle glavno pitanje je kako to sve popravit da bi radilo, hvala |
Kod: |
#include<stdio.h>
#include<stdlib.h> #include<ctype.h> #include<string.h> #define MAXL 100 typedef int elementtype; typedef struct{ elementtype elements[MAXL]; int pocetak, kraj; } DQUEUE; int addone(int i){ return((i+1)% MAXL); } void MAKE_NULL(DQUEUE *Q){ Q->pocetak=0; Q->kraj=MAXL-1; } int EMPTY(DQUEUE Q){ if (Q.pocetak == addone(Q.kraj)) return 1; else return 0; } elementtype FRONT(DQUEUE Q){ if (EMPTY(Q)) printf("Red je prazan!"); else return Q.elements[Q.pocetak]; } void UBACI_KRAJ(elementtype x, DQUEUE *Q){ if(addone(addone(Q->kraj))==(Q->pocetak)) printf("Red je pun!"); else{ Q->kraj=addone(Q->kraj); Q->elements[Q->kraj]=x; } } void IZBACI_POCETAK(DQUEUE *Q){ if(EMPTY(*Q)) printf("Red je prazan!"); else Q->pocetak=addone(Q->pocetak); } void IZBACI_KRAJ(DQUEUE *Q){ if(EMPTY(*Q)) printf("Red je prazan!\n"); else if(Q->kraj>0) --Q->kraj; else Q->kraj=MAXL-1; } void UBACI_POCETAK(elementtype x, DQUEUE *Q) { if(addone(addone(Q->kraj))==(Q->pocetak)) printf("Red je pun!\n"); else { Q->kraj=addone(addone(Q->kraj)); int i=Q->kraj; while(i!=Q->pocetak) { Q->elements[i]=Q->elements[i-1]; if(i>0) --i; else i=MAXL-1; } Q->elements[Q->pocetak]=x; } } int main() { DQUEUE Q; elementtype x; char funkcija[MAXL], pomocni[MAXL], broj[MAXL]; int i, j, br=0, n; MAKE_NULL(&Q); while(1) { i=0; j=0; gets(funkcija); n=strlen(funkcija); while(i<n) { if(funkcija[i]==' ') { if(br==0) pomocni[i]=funkcija[i]; br++; } else if(isdigit(funkcija[i])) { broj[j]=funkcija[i]; j++; } else pomocni[i]=funkcija[i]; i++; } x=atoi(broj); if(pomocni=="UBACI POCETAK") UBACI_POCETAK(x, &Q); else if(pomocni=="IZBACI POCETAK") IZBACI_POCETAK(&Q); else if(pomocni=="UBACI KRAJ") UBACI_KRAJ(x, &Q); else if(pomocni=="IZBACI KRAJ") IZBACI_KRAJ(&Q); else break; if(!EMPTY(Q)) { i=Q.pocetak; while(i!=Q.kraj) { printf("%d ", Q.elements[i]); addone(i); } printf("\n"); } } system("pause"); return 0; } |
Kod: |
while ( i < MAXLENGHT ) { if ( (*B).labels[i] != LAMBDA ) { // ni L ni D dijete ne stanu u polje, pa idem na sljedeci node if ( 2*i+1 > MAXLENGHT && 2*i+2 > MAXLENGHT ) { i++; break; } printf("Unesi lijevo dijete cvora %d na mjesto %d:\n", i,2*i+1); scanf ("%c", &c); (*B).labels[2*i+1]=c; if ( (*B).labels[2*i+1] == '#' ) return; printf("Unesi desno dijete cvora %d na mjesto %d:\n", i,2*i+2); scanf ("%c ", &c); (*B).labels[2*i+2]=c; if ( (*B).labels[2*i+2] == '#' ) return; } ++i; } |
mini (napisa): |
@gea
probaj napisat scanf (" %c") . dakle, razmak između navodnika i % |
Kod: |
#include<stdio.h> #define MAXL 100 typedef char labeltype; typedef int node; const node LAMBDA=-1; typedef struct { labeltype LABELS[MAXL]; } BTREE; void MAKE_NULL(BTREE *B) { int i; for(i=0;i<MAXL;i++) B->LABELS[i]='-'; } int EMPTY(BTREE B) { int i=1,j=0; while(i && j<MAXL) { if (B.LABELS[j]!='-') i=0; j++; } return i; } node CREATE (labeltype l, BTREE TL, BTREE TR, BTREE *B) { int i=0,k1=1,m=1,k2=2,j; B->LABELS[0]=l; while(k1<MAXL && k2<MAXL) { j=m; while(j>0) { B->LABELS[k1]=TL.LABELS[i]; B->LABELS[k2]=TR.LABELS[i]; i++; k1++; k2++; j--; } k1=k1+m; m=m*2; k2=k2+m; } return 0; } void LEFT_SUBTREE(BTREE B, BTREE *TL) { int i=0,k=1,l=1,j; while(k<MAXL) { j=l; while(j>0) { TL->LABELS[i]=B.LABELS[k]; i++; k++; j--; } k=k+l; l=l*2; } } void RIGHT_SUBTREE(BTREE B, BTREE *TR) { int i=0,k=2,l=1,j; while(k<MAXL) { j=l; while(j>0) { TR->LABELS[i]=B.LABELS[k]; i++; k++; j--; } l=l*2; k=k+l; } } node INSERT_LEFT_CHILD(labeltype l, node n, BTREE *B) { B->LABELS[n*2+1]=l; return n*2+1; } node INSERT_RIGHT_CHILD(labeltype l, node n, BTREE *B) { B->LABELS[n*2+2]=l; return n*2+2; } void DELETE(node n, BTREE *B) { B->LABELS[n]='-'; } node ROOT(BTREE B) { return 0; } node LEFT_CHILD(node n, BTREE B) { if ((2*n+1)>=MAXL || B.LABELS[2*n+1]=='-') return LAMBDA; return 2*n+1; } node RIGHT_CHILD(node n, BTREE B) { if ((2*n+2)>=MAXL || B.LABELS[2*n+2]=='-') return LAMBDA; return 2*n+2; } node PARENT(node n, BTREE B) { if (n==0) return LAMBDA; return (n-1)/2; } labeltype LABEL(node n, BTREE B) { return B.LABELS[n]; } void CHANGE_LABEL(labeltype l, node n, BTREE *B) { B->LABELS[n]=l; } int UNOS(int i, node j, char prefix[MAXL], BTREE *B) { node n1,n2; n1=INSERT_LEFT_CHILD(prefix[i], j, B); if (prefix[i]=='+' || prefix[i]=='-' || prefix[i]=='*' || prefix[i]=='/') i=UNOS(i+1,n1, prefix, B); i++; n2=INSERT_RIGHT_CHILD(prefix[i], j, B); if (prefix[i]=='+' || prefix[i]=='-' || prefix[i]=='*' || prefix[i]=='/') i=UNOS(i+1,n2, prefix, B); return i; } void OBILAZAK(node i,BTREE B) { node n1,n2; printf("%c ", LABEL(i,B)); n1=LEFT_CHILD(i,B); if (n1==LAMBDA) printf("NULL "); else printf("%c ",LABEL(n1,B)); n2=RIGHT_CHILD(i,B); if (n2==LAMBDA) printf("NULL"); else printf("%c",LABEL(n2,B)); printf("\n"); if (n1!=LAMBDA) OBILAZAK(n1,B); if (n2!=LAMBDA) OBILAZAK(n2,B); } void PREORDER(node n,BTREE B) { if (n==LAMBDA) return; printf("%c", LABEL(n,B)); PREORDER(LEFT_CHILD(n,B),B); PREORDER(RIGHT_CHILD(n,B),B); } int main() { BTREE P, prazno; char prefix[MAXL]; scanf("%s", prefix); MAKE_NULL(&P); MAKE_NULL(&prazno); CREATE(prefix[0], prazno, prazno, &P); UNOS(1,0, prefix, &P); OBILAZAK(0,P); PREORDER(0,P); return 0; } |
Kod: |
char REKONSTRUIRAJ( char *IN, char *POST)
{ char *Left_IN, *Right_IN, *Left_POST, *Right_POST, right, left; int n, i, j, t; char roditelj; n=strlen(POST); roditelj=POST[n-1]; for(i=0;i<n; i++) { if(IN[i]==roditelj) { Left_IN=(char*)malloc((i)*sizeof(char)); for(j=0; j<i; j++) { Left_IN[j]=IN[j]; } Right_IN=(char*)malloc((n-i-1)*sizeof(char)); for(j=0; j+i+1<n; j++) { Right_IN[j]=IN[j+i+1]; } break; } } Left_POST=(char*)malloc(i*sizeof(char)); for(j=0; j<i; j++) { Left_POST[j]=POST[j]; } Right_POST=(char*)malloc((n-i-1)*sizeof(char)); for(j=0; j+i<n-1; j++) { Right_POST[j]=POST[j+i]; } if (strlen (Left_IN) == 0) left = '-'; // to je NULL else left = REKONSTRUIRAJ (Left_IN, Left_POST); if (strlen (Right_IN) == 0) right = '-'; // to je NULL else right = REKONSTRUIRAJ (Right_IN, Right_POST); printf ("Cvor: %c %c %c\n", roditelj, left, right); free (Left_IN); free (Left_POST); free (Right_POST); return roditelj; } int main(void) { int n; char *IN, *POST; printf("unesi broj cvorova:\n"); scanf("%d", &n); IN=(char*)malloc((n)*sizeof(char)); POST=(char*)malloc((n)*sizeof(char)); printf("Unesi INORDER:\n"); scanf("%s", IN); printf("Unesi POSTORDER:\n"); scanf("%s", POST); REKONSTRUIRAJ (IN, POST); return 0; } |
output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.