Algoritma Stack untuk evaluasi postfix dan conversi basis
4.Buatlah keterangan dengan menggunakan gambar serta algoritma, untuk menggambarkan algoritma Stack untuk evaluasi postfix dan conversi basis dari basis 10 ke basis 2.
Jawab :
Algoritma postfix
Buatlah sebuah stack operan kosong
Ambil setiap token pada ekspresi posfiks, lalu periksa setiap token
1.Jika token adalah operan, maka push token ke dalam stack operan
2.Jika token adalah operator, maka pop stack operan lalu simpan sebagai operan kedua, dan pop lagi stack operan lalu simpan sebagai operan pertama.
3.Lakukan perhitungan terhadap kedua operan sesuai dengan operator token
Push hasil perhitungan ke dalam stack operan
Ulangi langkah 1 dan 2 hingga token habis
Pop stack operan dan kembalikan sebagai hasil evaluasi
Algoritma Konversi basis
Source Code
#include
#include
#include"math.h"
void main()
{
clrscr();
int a,b,n;
gotoxy(6,1);
printf("CONVERTING PROGRAM\n");
printf("(Decimal Value -> Binary Value)\n");
printf("===============================\n");
printf("Decimal Value (0-255) = ");
scanf("%d",&n);
a=n;
if(a<0)
{
printf("Access denied!\n");
}
else if(a>255)
{
printf("Access denied!\n");
}
else
{
printf("Binary Value = ");
while(a>1)
{
b=fmod(a,2);
a=a/2;
printf("%d",b);
printf("%d\n",a);
}
printf("===============================\n");
getch();
}
Algoritma
1. Masukkan bilangan desimal (n)
2. Proses looping
2a.. Untuk i=0 sampai i<8 n =" n/2" i="7">=0
3b. Cetak bin
3c. Kembali ke proses 3a
4. Program selesai
5. Carilah contoh program QUEUE di Internet dan jelaskan algoritma dari program yang anda peroleh tersebut
Jawab :
Contoh 1 :
#include
#include
#include
#include
#define MAX 100
char *p[MAX], *pop(void);
int spos = 0;
int rpos = 0;
void add(void), push(char *q), print(void), remove(void);
void add(void)
{
char s[256], *p;
do {
printf("spos %d: ", spos+1);
gets(s);
if(*s==0) {
break;
}
p = (char *) malloc(strlen(s)+1);
if(!p) {
printf("Out of memory.\n");
return;
}
strcpy(p, s);
if(*s) {
push(p);
}
} while(*s);
}
void print(void)
{
int t;
for(t=rpos; t < spos; ++t)
printf("%d. %s\n", t+1, p[t]);
}
void remove(void)
{
char *p;
if((p=pop())==NULL) {
return;
}
printf("%s\n", p);
}
void push(char *q)
{
if(spos==MAX) {
printf("List Full\n");
return;
}
p[spos] = q;
spos++;
}
char *pop(void)
{
if(rpos==spos) {
printf("No more.\n");
return NULL;
}
rpos++;
return p[rpos-1];
}
int main(void)
{
char s[80];
register int t;
for(t=0; t < MAX; ++t) {
p[t] = NULL;
}
while(1) {
printf("Add(A), Print(P), Remove(R), Quit(Q): ");
gets(s);
*s = toupper(*s);
switch(*s) {
case 'A':
add();
break;
case 'P':
print();
break;
case 'R':
remove();
break;
case 'Q':
exit(0);
}
}
return 0;
}
ALGORITMA
Queue adalah list linear yang:
1.Dikenali elemen pertama (HEAD) dan elemen terakhirnya (TAIL)
2.Penambahan elemen di lakukan di elemen terakhir (TAIL)
3.Penghapusan elemen di lakukan di elemen pertama (HEAD)
Algoritma untuk penambahan elemen jika masih ada tempat adalah dengan “memajukan” TAIL. Kasus khusus untuk Queue kosong karena HEAD harus diset nilainya menjadi 1.
Algoritma untuk penghapusan elemen jika Queue tidak kosong: ambil nilai elemen HEAD, kemudian HEAD “maju”. Kasus khusus untuk Queue dengan keadaan awal berelemen 1, yaitu menyesuaikan HEAD dan TAIL dengan DEFINISI. Algoritma ini TIDAK mencerminkan pergeseran orang yang sedang mengantri di dunia nyata, tapi efisien. Namun suatu saat terjadi keadaan Queue penuh tetapi “semu sebagai berikut :
Jika keadaan ini terjadi, haruslah dilakukan aksi menggeser elemen untuk menciptakan ruangan kosong. Pergeseran hanya dilakukan jika dan hanya jika TAIL sudah mencapai IndexMax.
Contoh 2 :
******** C Program For Impelmetation Of Queue ***********/
#define MAXSIZE 10
struct st
{
int front,rear;
int queue[MAXSIZE];
};
struct st s;
int empty(void);
int full(void);
void add(void);
void delete(void);
void display(void);
void main()
{
char ans;
int ch;
s.front = 0;
s.rear = 0;
do
{
clrscr();
printf("********Queue Program**********\n");
printf("1. ADD\n");
printf("2. DELETE\n");
printf("3. DISPLAY\n");
printf("4. QUIT\n");
printf("Enter Your Choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
add();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(1);
break;
default:
printf("INVALID CHOICE!!!!!!!!!!!!!!!!\n");
break;
}
printf("\nWant To Go To The Main Menu[y/n]");
flushall();
ans = getch();
}
while(ans == 'y' ans == 'Y');
printf("\nPress Any Key To Continue\n");
getch();
}
int full(void)
{
if (s.rear == MAXSIZE)
return(1);
else
return(0);
}
int empty(void)
{
if (s.front == s.rear + 1)
return(1);
else
return(0);
}
void add(void)
{
char ch;
int x;
do
{
if(full() == 1)
{
printf("\n\nQueue Full\n");
break;
}
else
{
s.rear = s.rear + 1;
printf("\nEnter An Element to Be Added ");
scanf("%d",&x);
s.queue[s.rear] = x;
if(s.rear == 1) s.front ++;
}
printf("\nDo You Want to Add More Elements[y/n]:");
flushall();
ch = getch();
}
while(ch=='y' ch == 'Y');
}
void delete(void)
{
char ch;
do
{
if(empty() == 1)
{
printf("\n\nQueue Empty\n");
break;
}
else
{
printf("% d Has Been Deleted!",s.queue[s.front]);
s.front = s.front +1;
}
printf("\nWant to Delete More [y\n]");
flushall();
ch = getch();
}
while(ch=='y' ch == 'Y');
}
void display(void)
{
int i;
clrscr();
if(empty () == 1)
printf("\nQueue Empty!!");
else
{
printf("\nDisplaying Queue\n");
for(i = s.front;i printf("%d\n",s.queue[i]);
}
}
/************ OUTPUT ***************
**********Queue Program**********
1. ADD
2. DELETE
3. DISPLAY
4. QUIT
Enter Your Choice : 1
Enter An Element to Be Added 1
Do You Want to Add More Elements[y/n]:y
Enter An Element to Be Added 2
Do You Want to Add More Elements[y/n]:y
Enter An Element to Be Added 3
Do You Want to Add More Elements[y/n]:y
Enter An Element to Be Added 4
Do You Want to Add More Elements[y/n]:y
Enter An Element to Be Added 5
Do You Want to Add More Elements[y/n]:n
Want To Go To The Main Menu[y\n] y
**********Queue Program**********
1. ADD
2. DELETE
3. DISPLAY
4. QUIT
Enter Your Choice : 3
Displaying Queue
1
2
3
4
5
Want To Go To The Main Menu[y\n] y
**********Queue Program**********
1. ADD
2. DELETE
3. DISPLAY
4. QUIT
Enter Your Choice : 2
1 Has Been Deleted!!
Do You Want To Delete More?[y/n] n
Want to Go To Main Menue[y/n] y
**********Queue Program**********
1. ADD
2. DELETE
3. DISPLAY
4. QUIT
Enter Your Choice : 3
Displaying Queue
2
3
4
5
Want To Go To The Main Menu[y\n] y
**********Queue Program**********
1. ADD
2. DELETE
3. DISPLAY
4. QUIT
Enter Your Choice : 4 */