98
ALGORITMY V JAZYKU C A C++
#include <conio.h> struct uzel { char Oper; double Cislo; struct uzel *levy,*pravy; }; struct uzel *P[50]; /* zásobník */ struct uzel *Q; int sp; /* ukazovátko v zásobníku */ void Tisk(struct uzel * Q) { /* výpis bin. stromu preorder – prefixová notace */ /* if (Q->Oper == ' ') printf("%f ",Q->Cislo); else printf("%c ",Q->Oper); */ printf("("); if (Q->levy!=NULL) Tisk(Q->levy); /* inorder – infixová notace, k ní je nutný výstup závorek */ if (Q->Oper == ' ') printf("%f ",Q->Cislo); else printf("%c ",Q->Oper); if (Q->pravy!=NULL) Tisk(Q->pravy); printf(")"); /* postorder – postfixová notace */ /* if (Q->Oper == ' ') printf("%f ",Q->Cislo); else printf("%c ",Q->Oper); */ } int main() { char radek[200]; char s[10]; char c; int i,j,k; sp = 0; /* inicializace zásobníku */ for (i=0;i<200;i++) radek[i]=' '; for (j=0;j<10;j++) s[j]=0; printf("Zadejte vyraz v postfixove notaci:\n"); j=strlen(gets(radek)); radek[j]='='; /* zarážka */ i=0; zac: while(radek[i]==' ') i++; c=radek[i];
7. Reprezentace aritmetického výrazu binárním stromem
Ukázka elektronické knihy, UID: KOS180596
if(c=='=') { sp--; Q=P[sp]; /* kořen stromu */ Tisk(Q); getch(); return; } if(c!='.' && !isdigit(c)) { /* operátor */ Q=(struct uzel*)malloc(sizeof(struct uzel)); if (Q!=NULL) { if ((c=='+') ||(c=='-') ||(c=='*') ||(c=='/')) { Q->Oper=c; Q->Cislo=0; if (sp<2) { printf("Zasobnik je prazdny"); return; } sp--; Q->pravy=P[sp]; sp--; Q->levy=P[sp]; P[sp]=Q; sp++; } else { printf("Neznamy prikaz"); return; } } else { printf("neni pamet!"); return; } } else { /* operand */ k=0; while(radek[i]==' ') i++; while(isdigit(radek[i])) { s[k]=radek[i]; if (k < 9) k++; else { printf ("Dlouhy operand!\n"); return; } i++; } if (radek[i]=='.')
99
7. Reprezentace aritmetického výrazu binárním stromem
ALGORITMY V JAZYKU C A C++
7.3 Převod postfixové notace na binární strom
Ukázka elektronické knihy, UID: KOS180596
100
ALGORITMY V JAZYKU C A C++
{
s[k]='.'; i++; if (k < 9) k++; else { printf ("Dlouhy operand!\n"); return; } while(isdigit(radek[i])) { s[k]=radek[i]; if (k < 9) k++; else { printf ("Dlouhy operand!\n"); return; } i++; }
} Q=(struct uzel*)malloc(sizeof(struct uzel)); if (Q!=NULL) { Q->Cislo=atof(s); Q->Oper=' '; Q->levy=NULL; Q->pravy=NULL; if (sp<49) { P[sp]=Q; sp++; } else { printf("Plny zasobnik"); return; } } else { printf("Neni pamet"); return; } i--;
}
} i++; goto zac; return 0;
7. Reprezentace aritmetického výrazu binárním stromem
Ukázka elektronické knihy, UID: KOS180596