Program Konversi Infix ke Postfix

/*
Name:Rudy Tri(5109100031), Anak Agung Ngurah Bagus Trihatmaja (5109100040)
Description: Program ini bertujuan untuk mengubah bentuk infix menjadi postfix dengan menggunakan konsep stack dalam linked list. Program ini meminta inputan berupa string maksimal 100 karakter dan mengeluarkan output berupa char. */


/*PREPOSESOR*/
#include
#include
#include
#define MAX 100


/*struct untuk linked list stack*/
typedef struct node
{
node *next;
node *prev;
char opnd;
};

typedef struct node *stack;

/*struct untuk head dan tail linked list*/
typedef struct list
{
stack head,tail;
};

/*untuk membuat node baru diperlukan alokasi memory
fungsi ini bertujuan untuk mengalokasikan memory bagi node*/
stack getnode()
{
stack p;
p =(stack)malloc(sizeof(node));
return (p);
}

/*setelah selesai memakai memory, diperlukan memory release agar kinerja
komputer setelah running program ini tetap baik. Namun tidak terlalu berpengaruh pada
komputer jaman sekarang*/
void freenode(list *lst)
{
stack temp;
for(temp=lst->head;temp!=NULL;temp=temp->next)
free(temp);
}

/*fungsi pop dalam konsep stack. Mengeluarkan elemen terakhir dalam linked list*/
char pop(list *lst)
{
stack temp;
temp=lst->tail;

if(lst==NULL){
printf("stack is empty");
exit(1);
}

while(temp->next!=NULL)//while ini bertujuan untuk mencari elemen terakhir dalam linked list
{
temp=temp->next;
}

if(temp->next==NULL)//apabila node terakhir tersebut telah ditemukan maka return isinya*/
{
return temp->opnd;
}
}

/*fungsi untuk menghapus node terakhir dalam linked list. Pada fungsi pop sebelumnya, elemen terakhir
hanya dikembalikan isinya namun tidak dihapus. Sebenarnya fungsi tersebut bisa saja disederhanakan sehingga
tidak perlu menggunakan fungsi remove last.
*/
void removeLast(list *lst)
{
stack temp;
if(lst== NULL){
printf("stack is empty");
}
else{
temp=lst->tail;
if(lst->head!=lst->tail){
lst->tail = (lst->tail)->prev;
(lst->tail)->next=NULL;
}
else{
lst->head=lst->tail=NULL;
}
free(temp);
}
}

/*fungsi untuk menginputkan elemen ke dalam linked list*/
void push(list *lst, char op)
{
stack temp;

temp = getnode();//alokasi memory
temp->opnd = op;
temp->next = NULL;//dalam C akan lebih baik jika kita menginisialisasikan sebelumnya
temp->prev = NULL;

if(lst->head == NULL){//jika linked list kosong atau untuk input yang pertama kali
lst->head = temp;
}
else{
/*menghubungkan node yang baru dengan node paling terakhir dalam linked list*/
temp->prev = lst->tail;
lst->tail->next = temp;
}
lst->tail=temp; //mengubah posisi tail dalam linked list
}

/*fungsi ini memberi nilai pada tiap operator untuk menentukan prioritas operator*/
int priority(char e)
{
int pri = 0;
if(e == '^')
pri = 5;
else if(e == '*' || e == '/' || e =='%')
pri = 3;
else if(e == '+' || e == '-')
pri = 1;
return pri;
}


int main()
{
/*INISIALISASI*/
char infix[MAX];//array untuk menampung input
char postfix[MAX];//array untuk menampung output
char t;//variabel temporary

list lst;
lst.head=NULL;//inisialisasi head dan tail
lst.tail=NULL;

int i;//digunakan dalam looping sebagai counter
int count=0;//digunakan untuk menentukan indeks dalam array postfix
int stackvalue=-1,nextvalue=-1; //digunakan sebagai pembanding prioritas operator
int flag=0;//digunakan sebagai counter linked list stack

/*INPUT*/
printf("Infix input is[max 100 character] : ");
scanf("%s",infix);

for(i=0;infix[i]!='\0';i++)//looping untuk mengecek input perkarakter
{


if(infix[i]=='/' || infix[i]=='*' || infix[i]=='+' || infix[i]=='-' || infix[i]=='^' || infix[i]=='(' || infix[i]==')')
/* untuk menentukan apakah karakter dalam input merupakan operand atau tidak */
/* tanda '(' dan ')'masuk ke dalam stack namun tidak memiliki nilai prioritas */
{

if(lst.head==NULL)//saat pertama kali menginputkan
{
if(infix[i]!='(')
{
stackvalue=priority(infix[i]);
}
}



else if(lst.head!=NULL)//ketika stack tidak kosong
{

if(infix[i] != '(' || (lst.tail)->opnd != '(')
{
/*cek prioritas*/
t=(lst.tail)->opnd;
stackvalue=priority(t);
nextvalue=priority(infix[i]);

}

if(nextvalue < stackvalue || infix[i] == ')')
{
/*bandingkan nilai prioritas dan cek apakah ada prioritas pengerjaan(ex : (a+b)*c))*/
while(flag!=0 && (lst.tail)->opnd != '(')
/*looping pop selama stack tidak kosong dan sampai menemukan '('*/
{
postfix[count]=pop(&lst);
removeLast(&lst);
count++;
flag--;
}

if(flag!=0 && (lst.tail)->opnd=='('){
/*jika stack tidak kosong dan terdapat '(' maka langsung di pop namun tidak masuk
ke dalam array output*/
removeLast(&lst);
flag--;
}
}
}

if(infix[i]!=')'){
/*operator ')' tidak masuk ke dalam stack. operator ')' hanya sebagai penanda*/
push(&lst,infix[i]);
flag++;
}

}

else//selain operator masukkan ke array postfix
{
postfix[count]=infix[i];
count++;
}

}


while(flag!=0)//jika stack tidak kosong maka pop sampai stack kosong
{
postfix[count]=pop(&lst);
removeLast(&lst);
count++;
flag--;
}

/*TAMPILKAN OUTPUT*/
printf("Postfix iutput is : ");
for(int j=0;j {
printf("%c",postfix[j]);
}


getch();
}