#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#define N 64
#define LP 10
#define RP 20
#define OPERATOR 30
#define OPERAND 40
#define LPP 0
#define AP 1
#define SP AP
#define MP 2
#define DP MP
#define REMP 2
#define NONE 9
static char infix[N+1],stack[N],postfix[N+1];
static int top;
void infixtopostfix(void);
int gettype(char);
void push(char);
char pop(void);
int getprec(char);
void main()
{
char ch;
do
{
clrscr();
top=-1;
printf("\n\n\n\n\t\t\tMASUKKAN BENTUK INFIX ==> ");
fflush(stdin);
gets(infix);
infixtopostfix();
printf("\t\t\tBENTUK POSTFIX ==> %s\n",postfix);
printf("\n\t\t\tAPAKAH INGIN MENGULANG?[Y/T]? ");
ch=getche();
printf("\n");
}while(ch=='Y' || ch=='y');
}
void infixtopostfix(void)
{
int i,p,l,type,prec;
char next;
i=p=0;
l=strlen(infix);
while(i<l)
{
type=gettype(infix[i]);
switch(type)
{
case LP:
push(infix[i]);
break;
case RP:
while((next=pop())!='(')
postfix[p++]=next;
break;
case OPERAND:
postfix[p++]=infix[i];
break;
case OPERATOR:
prec=getprec(infix[i]);
while(top>-1 && prec <= getprec(stack[top]))
postfix[p++]=pop();
push(infix[i]);
break;
}
i++;
}
while(top>-1)
postfix[p++]=pop();
postfix[p]='';
}
int gettype(char sym)
{
switch(sym)
{
case '(':
return(LP);
case ')':
return(RP);
case '+':
case '-':
case '*':
case '/':
case '%':
return(OPERATOR);
default :
return(OPERAND);
}
}
void push(char sym)
{
if(top>N)
{
printf("\nStack sudah penuh\n");
exit(0);
}
else
stack[++top]=sym;
}
char pop(void)
{
if(top<=-1)
{
printf("\nStack masih kosong\n");
exit(0);
}
else
return(stack[top--]);
}
int getprec(char sym)
{
switch(sym)
{
case '(':
return(LPP);
case '+':
return(AP);
case '-':
return(SP);
case '*':
return(MP);
case '/':
return(DP);
case '%':
return(REMP);
default :
return(NONE);
}
}
- Infix to postfix
Logika Program
Untuk bisa membuat program ini yaitu merubah notasi infix ke postfix, terlebih dahulu kami belajar teori tentang stack. Maka dari itu, sebelum kami menjelaskan logika dari program merubah notasi infix ke postfix, terlebih dahulu kami akan menjelaskan tentang apa itu stack?.
Stack adalah suatu urutan elemen yang elemennya dapat diambil dan ditambah hanya pada posisi akhir (top) saja. Contoh dalam kehidupan sehari-hari adalah tumpukan piring di sebuah restoran yang tumpukannya dapat ditambah pada bagian paling atas dan jika mengambilnya pun dari bagian paling atas pula. Kami menganalogikannya dengan buku yang di tumpuk. Ketika kita ingin mengambil atau menaruh buku selalu dari posisi atas dari tumpukan buku tersebut.
Ada 2 operasi paling dasar dari stack yang dapat dilakukan, yaitu :
1. Operasi push yaitu operasi menambahkan elemen pada urutan terakhir (paling atas).
2. Operasi pop yaitu operasi mengambil sebuah elemen data pada urutan terakhir dan menghapus elemen tersebut dari stack.
Selain operasi dasar stack (push dan stack), ada lagi operasi lain yang dapat terjadi dalam stack yaitu :
1. Proses deklarasi yaitu proses pendeklarasian stack.
2. Proses isempty yaitu proses pemeriksaan apakah stack dalam keadaan kosong.
3. Proses isfull yaitu proses pemeriksaan apakah stack telah penuh.
4. Proses inisialisasi yaitu proses pembuatan stack kosong, biasanya dengan pemberian nilai untuk top.
Representasi stack dalam pemrograman, dapat dilakukan dengan 2 cara yaitu :
1. Representasi stack dengan array
2. Representasi stack dengan single linked list
Sebagai contoh representasi kedua cara tersebut dengan operasi yang dilakukan adalah push(1), push(2), pop, push(5), push(8), pos. Untuk lebih detail, perhatikan gambar di bawah ini:
| Representasi stack dengan menggunakan array dengan maksimal data 5 adalah |
| Operasi-operasi stack secara lengkap adalah sebagai berikut : 1. Pendeklarasian stack Proses pendeklarasian stack adalah proses pembuatan struktur stack dalam memori. Karena stack dapat direpresentasikan dalam 2 cara, maka pendeklarasian stack pun ada 2 yaitu : a. Pendeklarasian stack yang menggunakan array. Suatu stack memiliki beberapa bagian yaitu * top yang menunjuk posisi data terakhir (top) * elemen yang berisi data yang ada dalam stack. Bagian ini lah yang berbentuk array. * maks_elemen yaitu variable yang menunjuk maksimal banyaknya elemen dalam stack. Dalam bahasa C, pendeklarasiannya adalah : #define maks 100 //pendeklarasian struktur stack struct tstack{ int top; int maks_elemen; int elemen[maks]; }; //pendeklarasian stack tstack stack; b. Pendeklarasian stack yang menggunakan single linked list Adapun stack yang menggunakan single linked list, hanya memerlukan suatu pointer yang menunjuk ke data terakhir (perhatikan proses di halaman sebelumnya). Setiap elemen linked list mempunyai 2 field yaitu elemen datanya dan pointer bawah yang menunjuk posisi terakhir sebelum proses push. Pendeklarasian dalam bahasa C adalah : typedef struct TStack *PStack; typedef struct TStack { int elemen; PStack bawah; }; // contoh pendeklarasian variable stack PStack stack;//variable stack akan selalu menunjuk top. |
2. Inisialisasi Inisialisasi stack adalah proses pembuatan suatu stack kosong. Adapun langkah-langkah proses tersebut berdasarkan jenis penyimpanannya adalah :
a. Inisialisasi stack yang menggunakan array.
Proses inisialisasi untuk stack yang menggunakan array adalah dengan mengisi nilai field top dengan 0 (nol) jika elemen pertama diawali dengan nomor 1. Kalau elemen pertama array dimulai dengan 0 (contoh bahasa C), maka top diisi dengan nilai -1.
Implementasinya dalam bahasa C adalah :
void inisialisasi(tstack *stack)
{
stack->top=-1;//karena dalam C array dimulai dgn 0
stack->maks_elemen=maks;
}
Cara pemanggilannya adalah
inisialisasi(&stack);
b. Inisialisasi stack yang menggunakan single linked list
Proses inisialisasi untuk stack yang menggunakan single linked list adalah dengan mengisi nilai pointer stack dengan NULL.
Implementasi dalam bahasa C adalah :
void inisialisasi(PStack *stack)
{
*stack=NULL;
}
Cara pemanggilannya adalah :
inisialisasi(&stack);
3. Operasi IsEmpty Operasi ini digunakan untuk memeriksa apakah stack dalam keadaan kosong. Operasi ini penting dilakukan dalam proses pop. Ketika suatu stack dalam keadaan kosong, maka proses pop tidak bisa dilakukan. Adapun langkah-langkah operasi ini adalah :
a. Operasi IsEmpty pada stack yang menggunakan array.
Operasi ini dilakukan hanya dengan memeriksa field top. Jika top bernilai 0 (untuk elemen yang dimulai dengan index 1) atau top bernilai -1 (untuk elemen yang dimulai dengan index 0), maka berarti stack dalam keadaan empty (kosong) yang akan me-return-kan true (1) dan jika tidak berarti stack mempunyai isi dan me-return-kan nilai false (0)
Implementasi dalam bahasa C adalah :
int isempty(tstack stack)
{
if (stack.top==-1)
return 1;
else
return 0;
}
Cara penggunaannya adalah :
//Penggunaan isempty dalam statement if
if( isempty(stack) ) ...
b. Operasi IsEmpty pada stack yang menggunakan single linked list.
Operasi IsEmpty pada stack yang menggunakan single linked list adalah dengan memeriksa apakah pointer stack bernilai NULL. Jika stack bernilai NULL maka menandakan stack sedang keadaan empty (kosong) dan akan me-return-kan nilai 1 dan jika tidak NULL maka menandakan stack mempunyai isi (tidak kosong) sehingga operasi tersebut akan me-return-kan nilai false (0).
Implementasinya dalam bahasa C adalah :
int isempty(PStack stack)
{
if (stack==NULL)
return 1;
else
return 0;
}
Cara penggunaannya adalah
//Penggunaan isempty dalam statement if
if( isempty(stack) ) ...
4. Operasi IsFull Operasi ini berguna untuk memeriksa keadaan stack apakah sudah penuh atau belum. Operasi ini akan menghasilkan nilai true (1) jika stack telah penuh dan akan menghasilkan nilai false (0) jika stack masih bisa ditambah. Langkah-langkah untuk operasi ini adalah :
a. Operasi IsFull pada stack yang menggunakan array.
Operasi ini akan memberikan nilai true (1) jika field top sama dengan field maks_elemen (untuk array yang elemennya dimulai dari posisi 1) atau top sama dengan maks_elemen-1 (untuk array yang elemennya dimulai dari posisi 0).
Implementasinya dalam bahasa C adalah :
int isfull(tstack stack)
{
if (stack.top==(stack.maks_elemen-1))
return 1;
else
return 0;
}
Cara pemanggilannya adalah :
//penggunaan isfull dalam statement if
if( !isfull(stack) ) … // jika stack tidak penuh
b. Operasi IsFull pada stack yang menggunakan single linked list.
Karena dalam linked list bersifat dinamis, maka pengecekan isFull adalah dengan memeriksa apakah memori masih dapat digunakan untuk alokasi sebuah elemen stack. Jika alokasi dapat dilakukan, maka berarti memori masih belum penuh dan proses push dapat dilakukan. Tetapi jika alokasi memori gagal dilakukan, maka berarti memori penuh dan tidak bisa menambah lagi elemen stack.
Implementasi dalam bahasa C adalah :
int isfull()
{
PStack test;
test=(PStack)malloc(sizeof(TStack));
if(test==NULL)//jika alokasi gagal
return 1;
else
{
free(test);
return 0;
}
}
Cara pemanggilannya adalah :
//penggunaan isfull dalam statement if
if( !isfull(stack) ) … // jika stack tidak penuh
5. Operasi Push Operasi push adalah operasi dasar dari stack. Operasi ini berguna untuk menambah suatu elemen data baru pada stack dan disimpan pada posisi top yang akan mengakibatkan posisi top akan berubah. Langkah operasi ini adalah :
a. Operasi push pada stack yang menggunakan array.
Langkah operasi push dalam array adalah dengan :
* Periksa apakah stack penuh (isfull). Jika bernilai false/0 (tidak penuh) maka proses push dilaksanakan dan jika pemeriksaan ini bernilai true/1 (stack penuh), maka proses push digagalkan.
* Proses push-nya sendiri adalah dengan menambah field top dengan 1, kemudian elemen pada posisi top diisi dengan elemen data baru. Implementasinya dalam bahasa C adalah :
void push(tstack *stack, int baru)
{
if(!isfull(*stack))
{
stack->top++;
stack->elemen[stack->top]=baru;
}
else
{
printf("Stack Full. Push Gagal.\n");
}
}
Cara penggunaannya adalah :
push(&stack,5);// push 5 ke dalam stack
b. Operasi push pada stack yang menggunakan single linked list Operasi push pada stack yang menggunakan single linked list adalah sama dengan proses tambahawal pada operasi linked list. Langkah-langkahnya adalah :
* Periksa apakah memori penuh (isfull). Jika bernilai false/0 (tidak penuh) maka proses push dilaksanakan dan jika pemeriksaan ini bernilai true/1 (stack penuh), maka proses push digagalkan.
* Proses push-nya sendiri adalah dengan cara mengalokasikan suatu elemen linked list (disebut variable baru), kemudian periksa jika stack dalam keadaan kosong maka pointer yang menunjuk ke awal stack diisi dengan pointer baru, dan jika dengan menambah field top dengan 1, kemudian elemen pada posisi top diisi dengan elemen data baru. Tetapi jika pointer penunjuk stack sudah menunjuk ke suatu data, maka sambungkan field pointer bawah (penunjuk ke data sebelumnya) dari pointer baru ke pointer penunjuk posisi akhir stack (top) dan kemudian pindahkah pointer penunjuk posisi akhir stack ke pointer baru. Untuk lebih jelas perhatikan kembali gambar 5 di halaman 3 mengenai representasi stack dengan linked linst.
Implementasi operasi ini dengan menggunakan bahasa C adalah :
void push(PStack *stack, int data)
{
PStack baru;
if(!isfull())
{
baru=(PStack)malloc(sizeof(TStack));
baru->bawah=NULL;
baru->elemen=data;
if(isempty(*stack))
*stack=baru;
else
{
baru->bawah=*stack;
*stack=baru;
}
}
else
{
printf("Memory Full. Push Gagal.\n");
}
}
Cara penggunaannya adalah :
push(&stack,5);// push 5 ke dalam stack
6. Operasi Pop Operasi pop adalah salah satu operasi paling dasar dari stack. Operasi ini berguna untuk mengambil elemen terakhir (top) dan kemudian menghapus elemen tersebut sehingga posisi top akan berpindah. Operasi ini biasanya dibuat dalam bentuk function yang me-return-kan nilai sesuai data yang ada di top.
a. Operasi pop pada stack yang menggunakan array.
Langkah operasi pop pada stack yang menggunakan array adalah terlebih dahulu memeriksa apakah stack sedang keadaan kosong, jika tidak kosong maka data diambil pada posisi yang ditunjuk oleh posisi top, kemudian simpan dalam variable baru dengan nama data, kemudian posisi top – 1, kemudian nilai pada variable data di-return-kan ke function.
Implementasi operasi ini dalam bahasa C adalah :
int pop(tstack *stack)
{
int data;
if(!isempty(*stack))
{
data=stack->elemen[stack->top];
stack->top--;
return data;
}
else
return 0;
}
Cara pemanggilannya adalah :
int data;
data=pop(&stack);
b. Operasi pop pada stack yang menggunakan single linked list Langkah operasi pop pada stack yang menggunakan single linked list adalah sama dengan proses hapusawal pada operasi single linked list. Prosesnya adalah :
* Periksa apakah.stack kosong (isempty), jika kosong maka proses pop tidak bisa dilakukan. Jika stack tidak kosong maka proses pop dijalankan.
* Proses pop-nya sendiri adalah mengambil elemen yang ditunjuk oleh pointer stack kemudian simpan dalam variable data. Kemudian buat variable pointer bantu yang diisi dengan pointer penunjuk stack yang nantinya akan dihapus dari memori. Kemudian pointer penunjuk stack dipindahkan ke posisi yang ditunjuk oleh field pointer bawah dari variable bantu.
Implementasi dalam bahasa C adalah :
int pop(PStack *stack)
{
int data;
PStack bantu;
if(!isempty(*stack))
{
data=(*stack)->elemen;
bantu=*stack;
*stack=bantu->bawah;
free(bantu);
return data;
}
else
return 0;
}
Cara pemanggilannya adalah :
int data;
data=pop(&stack);
Itulah, beberapa penjelasan dan teorinya berikut dengan implementasinya menggunakan bahasa C. Karena kami memilih menggunakan bahasa C untuk membuat program ini. Jika dilihat dan dibandingkan antara listing yang kami buat dengan implementasi dari teori diatas memang berbeda. Karena kami tambahkan dan kami edit untuk syntaknya tidak hanya itu kami juga berusaha mencoba untuk lebih mengexplor ilmu dari apa yang telah kami pelajari di Alogaritma dan pemograman 3.
Selanjutnya, kami akan menjelaskan tentang logika program yang telah kami buat. Hal yang terpenting ialah kita harus fokus kepada output yang diminta, output yang di minta adalah nilai dari infix yang dirubah menjadi postfix.
0 comments:
Post a Comment