logika program posfix infix borland C++
Logika program CODE KONVERSI DARI INFIKS KE POSTFIX
#include
#include
#include
#include
#include
const int size =50;
char infix[size],postfix[size],stack[size];
int top=-1;
int precedence(char ch); // function to get the precedence of the operator
char pop(); //function to pop an element from the stack
char topelement(); // returns the top element of the stack
void push(char ch); // pushes an element into the stack
int main()
{
char ele,elem,st[2];
int prep,pre,popped,j=0,chk=0;
strcpy(postfix," ");
gets(infix);
for(int i=0;infix[i]!=0;i++)
{
if(infix[i]!='('&&infix[i]!=')'&&infix[i]!='^'&&infix[i]!='*'&&infix[i]!='/'&&infix[i]!='+'&&infix[i]!='-')
postfix[j++]=infix[i];
else if(infix[i]=='(')
{
elem=infix[i];
push(elem);
}
else if(infix[i]==')')
{
while(popped=pop() != '(')
postfix[j++]=popped;
}
else
{
elem=infix[i];
pre=precedence(elem);//stores the precedence of operator coming frm infix
ele=topelement();
prep=precedence(ele);//stores the precedence of operator at the top of the stack
if(pre > prep)
push(elem);
else
{
while(prep >= pre)
{
if(ele=='#')
break;
popped=pop();
ele=topelement();
postfix[j++]=popped;
prep=precedence(ele);
}
push(elem);
}
}
}
while((popped=pop())!='#')
postfix[j++]=popped;
postfix[j]='\0';
cout<<"\n post fix :"<<
system("pause");
return 0;
}
int precedence(char ch)
{
switch(ch)
{
case '^' : return 5;
case '/' : return 4;
case '*' : return 4;
case '+' : return 3;
case '-' : return 3;
default : return 0;
}
}
char pop() //function to pop the element from the stack
{
char ret;
if(top!=-1)
{ ret =stack[top];
top--;
return ret;
}
else
return '#';
}
char topelement() // function to return top element from the stack without popping
{
char ch;
if(top!=-1)
ch=stack[top];
else
ch='#';
return ch;
}
void push(char ch) // function to push an element in the stack
{
if(top!=size-1)
{
top++;
stack[top]= ch;
}
}
LOGIKA PROGRAM
Untuk dapat memahami bagaimana suatu program ditulis, maka struktur dari program harus dimengerti terlebih dahulu. Tiap bahasa komputer mempunyai struktur program yang berbeda. Dalam pembuatan program konversi dari notasi infix ke posfix dengan menggunakan bahasa pemrograman C++ maka pertama- tama kita harus mengetahui setiap tanda dan nama- nama bagian untuk bahasa pemrograman C, seperti deklarasi, inti program dan #include yang merupakan salah satu jenis paragraph praposesor (preprocessor directive). Yang mana paragraph ini dipakai untuk membaca file yang diantaranya berisi deklarasi fungsi dan definisi konstanta. Beberapa file judul disediakan dalam C, file-file ini mempunyai ciri yaitu namanya diakhiri dengan ekstensi .h karena ini merupakan suatu header. Header file merupakan file yang berisi dengan prototype ( judul, nama, sintak ) dari sekumpulan fungsi-fungsi pustaka tertentu. Jadi file ini hanya berisi dengan prototipe dari fungsi-fungsi pustaka, sedangkan fungsi-fungsi pustakanya
sendiri disimpan dalam file pustaka (library file dengan nama extension file –nya adalah .LIB). Misalnya prototipe dari fungsi-fungsi pustaka printf() dan scanf() terdapat di file stdio.h, sehingga jika fungsi-fungsi ini digunakan di program, maka nama file judulnya harus dilibatkan dengan menggunakan preposcessor #include. File judul stdio.h berisi prototype fungsi-fungsi pustaka untuk operasi input dan output standar. Ada dua cara melibatkan file judul disuatu program C, yaitu : #include atau #include “stdio.h”.
Pada program ini kita buat #include yang berguna untuk disertakan pada program yang melibatkan obyek cout. Tanpa kehadiran baris tersebut akan terjadi kesalahan sewaktu program dikompilasi. Sebab file iostream.h berisi deklarasi yang diperlukan oleh cout dan berbagai obyek yang berhubungan dengan operasi masukan-keluaran pada stream. Ini bukanlah suatu pernyataan. Itulah sebabnya tidak ada tanda titik koma yang diperlukan. Baris tersebut mengisntruksikan kepada kompiler untuk menyisipkan file lain (pada contoh iostream.h) saat program dikompilasi. Kemudian #include yang berfungsi agar compiler membaca file bernama stdio.h saat kompilasi sedang dilakukan. Fungsi-fungsi pustaka yang digunakan untuk memasukkan data melalui keyboard, prototypenya ada di stdio.h seperti gets(), scanf(), getchar(). Dan prototype dari fungsi- fungsi untuk menampilkan hasil terdapat pada file judul stdio.h bersifat standar yaitu putchar(), puts(), printf(), dan fprintf(). #include juga merupakan suatu directive menyatakan beberapa fungsi perpustakaan yang berguna untuk melakukan "konsol input dan output" dari sebuah program. Fungsi-fungsi pustaka yang digunakan untuk memasukkan data melalui keyboard, prototypenya ada di conio.h yaitu getche() dan getch(). Dan untuk menampilkan hasil terdapat pada file judul conio.h bersifat tidak standar, dalam arti tidak semua kompiler C menyediakan yaitu clrscr() dan gotoxy(). Lalu gunakan #include
Kemudian tentukan jumlah maksimal nilai konstanta yang bernilai 50 dengan menggunakan variabel size dan tipe data integer karena tipe ini bisa berupa pecahan yang dibulatkan dan nilai negatif positif. Deklarasikan variable infix, posfix dan stack dengan tipe char yang dimaksudkan untuk menampung nilai sebuah huruf (karakter). Karakter yang disimpan dimemori dengan deklarasi tipe char menempati posisi 1 byte (8 bit) yang diwakili kode ASCII. Variabel ini mempunyai nilai maksimum size yang nilainya sudah ditentukan pada deklarasi sebelumnya. Dan int top=-1; maksudnya untuk menentukan terdapat ruang pada stack untuk object yang dimasukkan yang bernilai -1. Gunakan int precedence untuk memperoleh atau memprioritaskan operator yang lebih tinggi dengan tipe data integer yang berupa karakter. Kemudian char pop yang digunakan untuk menghapus elemen pada stack yang terdapat pada karakter. Lalu setelah menghapus elemen maka akan diperoleh kembali nilai top elemen yang selanjutnya dan berguna untuk mengembalikan elemen teratas dari stack. Perintahkan void push(char ch) yang berfungsi untuk memasukan elemen ke dalam stack yang berfungsi sebagai suatu operand. Karena pada push menggunakan void maka menurut bentuk umu yang digunakan setelah itu harus menggunakan main dengan int main().
Dalam sebuah stack untuk mengubah notasi posfix ke infix maka notasi tersebut mempunyai beberapa aturan antara lain, jika terdapat penginputan kurung buka “(“ maka tanda tersebut akan masuk atau PUSH kedalam stack dan apabila terdapat penginputan tanda kurung tutup “)” maka elemen-elemen yang berada pada stack akan dikeluarkan atau di POP dari stack dan menjadi output kecuali tanda “(“ tadi. Dan kemudian pada perubahan postfix ini setiap operand yang diinput akan langsung menjadi output. dan jika terdapat penginputan operator, maka operator tersebut akan menjadi top dari stack dengan level lebih tinggi atau sama dan top dari stack tersebut akan tercetak sebagai output dan apabila lebih rendah, maka operartor yang diamati akan masuk ke dalam stack. Untuk memulai menuliskan isi utama dari program buat tanda kurung kurawal buka ‘{‘ lalu ketik perintah selanjutnya dengan membuat variabel ele, elem, st untuk penyimpanan atau kependekan yang terdiri dari 2 indeks. Lakukan juga untuk variable precedence elemen, topelemen, precedence topelemen, lalu untuk variable j bernilai nol dan chk bernilai nol juga. Kemudian strcpy dengan maksud menyalin nilai string suatu elemen dengan mencetak kalimat posfix lalu sisipan kosong yang akan diisi oleh inputan data yang akan dibuat. Setelah itu kita akan mendapatkan hasil infix dengan gets() yang berfungsi membaca string dari keyboard sampai ketemu new-line dan disimpan pada buffer, kemudian new-line di replace dengan null character, dan mengembalikan nilai NULL jika ada error dan mengembalikan argument-nya (buffer) jika sukses. For(int i=0;infix[i]!=0;i++) gunakan perulangan for untuk nilai variable i sama dengan nol maka nilai infix pada indeks variable i tidak sama dengan nol karena i++ yang berarti nilai bertambah 1.
Lalu buat perintah lagi dengan { yang berisi if(infix[i]!='('&&infix[i]!=')'&&infix[i]!='^'&&infix[i]!='*'&&infix[i]!='/'&&infix[i]!='+'&&infix[i]!='-') yang berarti jika infix i tidak sama dengan nilai variabel i maka akan tercetak dengan urutan ‘(‘ dan infix i tidak sama dengan nilai i maka dicetak ‘)’, selanjutnya tanda ^ atau pangkat, * atau perkalian, / atau pembagian, + atau tambah, - atau kurang. Maka nilai posfix akan bertamabah atau bergeser nilainya sama dengan nilai infix I yang sudah diatur. Dan jika suatu data yang diinput tidak ada maka akan berpindah pada pilihan if selanjutnya yaitu jika infiks berbentuk tanda ‘(‘ maka dalam program stack maka buat perintah dalam elemen yang bernilai infix i jika bertemu tanda buka kurung maka akan di push atau dimasukkan ke dalam stack atau tumpukan lalu tutup program yang berarti sudah tidak berlaku lagi perintah program tersebut dengan kurung tutup ‘)’. Dan jika nilai infix bertemu tanda ‘)’ maka buat program bahwa gunakan while perintah suatu kondisi jika bertemu tanda ‘)’ maka stack akan dihapus sampai bertemu dengan tanda ‘(‘ pertama dan hasil penghapusan itu akan menjadi nilai posfix yang bertambah. Selain itu gunakan kondisi jika nilai elemen infix i maka akan ditentukan bahwa pre bernilai hasil operator dari suatu elemen yang nilainya dating dari infix, kemudian ele yang berarti nilai dari top elemen, dan prep yang bernilai hasil operator dari top atau urutan nilai tertinggi dalam stack. Dari perintah itu maka dapat ditentukan jika pre lebih besar dari prep maksudnya nilai infix sesudahnya lebih besar dari sebelumnya maka nilai operator elemen tersebut akan di push atau dimasukkan ke dalam stack. Dan jika kondisi operator infix sebelumnnya lebih besar atau sama dengan nilai infix sesudahnya maka elemen operator tersebut akan dihapus dari stack yang kemudian disimpan ke dalam nilai posfix yang menjadi hasil dari topelemen sudah dipop. Setelah selesai program itu lalu push elemen kembali jika infix selanjutnya masih ada. Lalu tutup program sesuai penggunaan tanda kurung kurawal buka tadi.
Jika kondisi popped tidak bukan sama dengan operator maka akan di hapus dan tercetak tanda # yang berarti bukan operator atau sebuar string operand yang langsung menjadi pposfix atau sebuah output program. Dan hasil posfix j tersebut akan menyisipkan string null atau kosong. Kemudian gunakan strean cout untuk menggabungkan output (penyisipan) dari tiga variable, juga dari kanan ke kiri. Cout juga digunakan untuk menyisipkan ekspresi, konstanta, atau penentu variable ke dalam stream, selama type diberikan oleh class. Gunakan operator penyisipan (<<) diantara item yang kemudian akan dicetak \n untuk mengakhiri sebuah string pada baris baru kalimat post fix: lalu diisi dengan variable posfix yang telah menjadi output yang telah disisipkan dan kemudian <
Pada hasil elemen dengan variable precendence bertipe karakter. Dengan menggunakan statemen switch akan menyeleksi kondisi yang diberikan dan kemudian membandingkan hasilnya dengan konstanta-konstanta yang berada di case. Pembandingan akan dimulai dari konstanta1 sampai dengan konstanta terakhir. Jika hasil dari kondisi sama dengan nilai konstanta tertentu, misalnya konstanta2, maka statemen-statemen yang ada di case konstanta2 akan diproses sampai ditemui statemen break yang akan membawa proses keluar dari penyeleksian switch. Pada case- case ini akan diurutkan suatu nilai operator dari yang tertinggi hingga yang rendah tingkatannya. Untuk case ^ atau pangkat berada pada posisi lebih tinggi yaitu dengan menuju ke nomor 5. Untuk case '/' atau pembagian maka pada posisi ke-4; untuk case '*' perkalian pada posisi ke-4; untuk case '+' penambahan pada posisi ke-3; untuk case '-' pengurangan pada posisi ke-3; dan untuk tanda yang tidak ada di dalam case atau default akan diletakkan pada posisi 0.
Program untuk karakter variable pop yang digunakan untuk menghapus sebuah elemen yang berada di dalam stack. Kemudian karakter ret yaitu untuk menyimpan hasil, jika top atau nilai teratas yang masuk ke dalam stack tidak sama dengan -1 maka hasil ret bernilai top nilai tertinggi dalam stack dan ret berkurang satu, dan akan tercetak hasil dari ret tersebut. Jika tidak ada dalam pilihan itu maka hasil akan berupa # atau kosong.
Perintah program yang terdapat dalam variable topelemen berarti yang merupakan fungsi dari sebuah elemen yang menjadi top dalam stack tanpa melakukan penghapusan. Dalam isi programnya bahwa pada karakter ch jika terdapat nilai top yang bernilai tidak sama dengan -1 maka ch akan bernilai sama dengan hasil sebuah nilai stack yang tertinggi. Jika tidak maka ch sama dengan #, lalu terlihatlah hasil ch tersebut.
Pada fungsi push yamg berarti memasukkan sebuah elemen ke dalam stack akan terlihat hasilnya jika nilai top tersebut tidak sama dengan bernilai size dikurangi 1. Maka dalam nilai tersebut terdapat bahwa top akan bertambah hingga nilai stack top tersebut menuju pada nilai ch terakhir di dalam sebuah infix
Jumat, 23 April 2010 pukul 18.46.00 GMT+7
kalo bisa di percepat ya,,, makasih
Jumat, 23 April 2010 pukul 18.46.00 GMT+7
ma'af nich aku ada tugas algoritma,,
menghitung jumlah pasangan kurung menggunakan bahasa C++ pada notasi infix, stack