import java.util.Scanner;
class Node {
public Object data;
public Node next;
public Node () {
data =' '; next = null; }
public Node (Object val) {
data = val; next = null; }
}
public class empat {
private Node top;
public empat() {
top = null; }
public boolean empty(){
return top == null; }
public boolean full(){
return false;
}
public void push(Object e){
Node tmp = new Node(e);
tmp.next = top;
top = tmp;
}
public Object pop(){
Object e = top.data;
top = top.next;
return e;
}
public Object peek(){
Object e = top.data;
return e;
}
public void postfix(String x){
String output="";
empat S=new empat();
for(int i=0;i<x.length();i++){
char c=x.charAt(i);
if(c==('+')||c==('*')||c==('-')||c==('/')){
while(!S.empty() && priority(S.peek())>= priority(c))
output+=S.pop();
S.push(c);
}
else if(c=='('){
S.push(c);
}
else if(c==')'){
while(!S.peek().equals('('))
output+=S.pop();
S.pop();
}
else
output+=c;
}
while(!S.empty())
output+=S.pop();
System.out.println("Notasi Infix : "+x);
System.out.println("Notasi Postfix : "+output);
}
public void prefix(String x){
String output="";
empat S=new empat();
int i;
for(i=0;i<x.length();i++){
char c=x.charAt(i);
if(c==('+')||c==('*')||c==('-')||c==('/')){
while(!S.empty() && prioritas(S.peek()) <= prioritas(c))
output+=S.pop();
S.push(c);
}
}
while(!S.empty())
output+=S.pop();
for(i=0;i<x.length();i++){
char c=x.charAt(i);
if(c==('+')||c!=('*')||c!=('-')||c!=('/')){
while(!S.empty() && prioritas(S.peek()) >= prioritas(c))
output+=S.pop();
S.push(c);
}
else
output+=c;
if((c=='(')||(c==')')){
S.pop();
}
if(c==('+')||c==('*')||c==('-')||c==('/')){
S.pop();
}
}
while(!S.empty())
output+=S.pop();
System.out.println("Notasi Prefix : "+output);
}
public int priority(Object x){
if(x.equals('+')||x.equals('-'))
return 1;
else if(x.equals('*')||x.equals('/'))
return 2;
else
return 0;
}
public int prioritas(Object x){
if(x.equals('+')||x.equals('-'))
return 2;
else if(x.equals('*')||x.equals('/'))
return 1;
else
return 0;
}
public static void main(String args[]){
Scanner in = new Scanner(System.in);
empat s=new empat();
System.out.println();
System.out.println("------------------------------------------");
System.out.print("Inputkan Notasi Infix: "); String input = in.next();
System.out.println("------------------------------------------");
s.postfix(input);
s.prefix(input);
System.out.println("------------------------------------------");
}
}
