import java.util.Stack;
import java.io.*;
import javax.swing.*;
public class RPN{
public static boolean precedence(char a,char b){
int pos[]=new int[2];
pos[0]=-1;
pos[1]=-1;
for(int i=0;i<s.length;i++){
if(s[i].indexOf(b)==1 && s[i].indexOf(a)!=0) return false;
}
for(int i=0;i<oper.length;i++){
if(oper[i].indexOf(a)>-1) pos[0]=i;
if(oper[i].indexOf(b)>-1) pos[1]=i;
}
if(pos[0]<pos[1]) return true;
else if(pos[0]>=pos[1] && pos[0]!=-1 && pos[1]!=-1) return false;
return true;
}
public static String prepare(String infix){
infix=infix.replaceAll("[ ]+","");
for(int i=0;i<oper.length;i++){
for(int k=0;k<oper[i].length();k++){
infix=infix.replaceAll("\\"+oper[i].charAt(k)," \\"+oper[i].charAt(k)+" ");
}
}
for(int i=0;i<s.length;i++){
for(int k=0;k<s[i].length();k++){
infix=infix.replaceAll("\\"+s[i].charAt(k)," \\"+s[i].charAt(k)+" ");
}
}
infix=infix.replaceAll("[ ]+"," ");
if(infix.charAt(0)==' ') infix=infix.replaceFirst(" ","");
return infix;
}
public static String toPrefix(String infix){
infix=prepare(infix);
Stack<Character> op_stack=new Stack();
String[] token=infix.split(" ");
StringBuffer out=new StringBuffer();
for(int i=0;i<token.length;i++){
boolean operator=false;
for(int k=0;k<oper.length;k++){
if(oper[k].indexOf(token[i].charAt(0))>-1) operator=true;
}
for(int k=0;k<s.length;k++){
if(s[k].indexOf(token[i].charAt(0))>-1) operator=true;
}
if(operator==false){
out.append(token[i]);
out.append(" ");
}
else{
boolean empty=op_stack.isEmpty();
char op=token[i].charAt(0);
char peek;
boolean operand=false;
while(!(empty=op_stack.isEmpty()) && (!precedence(peek=op_stack.peek(),op))){
out.append(op_stack.pop());
out.append(" ");
}
if(!(empty=op_stack.isEmpty())){
for(int k=0;k<s.length;k++){
if(s[k].indexOf(op_stack.peek())==0 && s[k].indexOf(op)==1) operand=true;
}
}
if(empty || operand==false)
op_stack.push(op);
else op_stack.pop();
}
}
while(!op_stack.isEmpty()){
out.append(op_stack.pop());
out.append(" ");
}
return out.toString();
}
public static void main(String[] args){
JFrame frame=new JFrame();
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
JOptionPane Pane=new JOptionPane();
frame.setContentPane(Pane);
String infix=Pane.showInputDialog("Enter String");
Pane.showMessageDialog(frame,toPrefix(infix),infix,JOptionPane.ERROR_MESSAGE);
frame.dispose();
}
private static final String [] oper={"+-","*/","^"};
private static final String [] s={"()","[]","{}"};
}