PROGRAM INFIX KE PREFIX

import java.util.Scanner;
class Node{
    char kata1;
    char kata2;
    int der2;
    Node depan1, belakang1;
    Node depan2, belakang2;
    Node(char kata){
        kata1=kata;
        kata2=kata;
        if(kata2=='+' || kata2=='-'){
            der2=1;
        }
        else if(kata2=='*' || kata2=='/'){
            der2=2;
        }
        else if(kata2=='^'){
            der2=3;
        }
        else
            der2=0;
    }
}

class Prefix{
    static Node top1, tail1; //stack pre
    static Node top2, tail2; //stack opr
    static int size1=0, size2=0;

    void pushPre(char data){ //menampung operand dulu
        if(size1==0){
            top1=tail1=new Node(data);
        }
        else{
            Node tmp=top1;
            tmp.depan1=new Node(data);
            tmp=tmp.depan1;
            tmp.belakang1=top1;
            top1=tmp;
        }
        size1++;
    }

    void pushOpr(char data){ //menampung operator
        if(size2==0){
            top2=tail2=new Node(data);
        }
        else{
            Node tmp=top2;
            tmp.depan2=new Node(data);
            tmp=tmp.depan2;
            tmp.belakang2=top2;
            top2=tmp;
        }
        size2++;
    }

    int derajat(char x){
        if(x=='+' || x=='-'){
            return 1;
        }
        else if(x=='*' || x=='/'){
            return 2;
        }
        else if(x=='^'){
            return 3;
        }
        else return 0;
    }

    void tampil(){
        Node tmp=top2;
        System.out.print(" isi stack opr : ");
        while(tmp!=null){
            System.out.print(tmp.kata2);
            tmp=tmp.belakang2;
        }
    }

    void popPre(){
        System.out.print(top1.kata1);
        if(size1>1){
            top1=top1.belakang1;
            top1.depan1=null;
        }
        else
            top1=null;
        size1--;
    }

    void popOpr(){
        if(size2>1){
            top2=top2.belakang2;
            top2.depan2=null;
        }
        else
            top2=null;
        size2--;
    }

    public static void main(String[] args){
        Scanner s=new Scanner(System.in);
        Prefix p=new Prefix();
        String infix;
        char[] inf;
        int der;
        char bantu;
        System.out.print(" MASUKKAN INFIX = ");
        infix=s.nextLine();
        inf=infix.toCharArray();
        for(int a=inf.length-1; a>=0; a--){
            if(inf[a]!='+' && inf[a]!='-' && inf[a]!='*' && inf[a]!='/' && inf[a]!='^' && inf[a]!='(' && inf[a]!=')' && inf[a]!=' '){
                p.pushPre(inf[a]);
            }
            else if(inf[a]==')'){
                p.pushOpr(inf[a]);
            }

            else if(inf[a]=='('){
                while(top2.kata2!=')'){
                    bantu=top2.kata2;
                    p.pushPre(bantu);
                    p.popOpr();
                }
                p.popOpr();
            }
            else{
                der=p.derajat(inf[a]);
                if(size2==0 || top2.der2==0){
                    p.pushOpr(inf[a]);
                }
                else if(size2>0 && top2.der2>0){
                    while(size2!=0 && top2.der2>der){
                        bantu=top2.kata2;
                        p.pushPre(bantu);
                        p.popOpr();
                    }
                    p.pushOpr(inf[a]);
                }
                else if(top2.der2==der){
                    p.pushOpr(inf[a]);
                    }
            }
        }
        while(size2>0){
            bantu=top2.kata2;
            p.pushPre(bantu);
            p.popOpr();
        }
        System.out.print(" Prefix = ");
        while(size1>0){
            p.popPre();
        }
    }
}