Converting Reverse Polish to Infix Notation in Java

Question

I am trying to solve a programming challange that involves converting reverse polish notation to infix notation. For example: 1 3 + 2 4 5 - + / would be: ((1+3)/(2+(4-5))) My solution so far does work, but it's not fast enough. So I am looking for any optimization advice.

public class betteralgo {
 public static void main(String[] args) throws IOException {
 BufferedReader bi = new BufferedReader(new 
 InputStreamReader(System.in));
 String line = bi.readLine();
 String[] input = line.split(" ");
 StringBuilder builder = new StringBuilder();
 Stack<String> stack = new Stack<String>();
 for(String e:input) {
 switch(e){
 case("+"):
 case("-"):
 case("*"):
 case("/"):
 String i = stack.pop();
 String k = stack.pop();
 stack.push("(" + k + e + i + ")");
 break;
 default:
 stack.push(e);
 }
 }
 System.out.println(stack.pop()); 
 } 
 }

• Martin R: "it's not fast enough" – for which input? How long does it take? Is there a concrete time limit that you need to achieve?

Answer 1

use a recursive function
I guess avoiding the stack-juggling (because of the recursivity of fromRPN) and the unnecessary creation of String objects (with StringJoiner) should make it fast enough.

fromRPN( new ArrayList<String>( Arrays.asList( "1 3 + 2 4 5 - +".split( " " ) ) ) ); // ((1+3)/(2+(4-5)))

public String fromRPN( ArrayList<String> rpn ) {
 for( int n = 0; rpn.size() > 1; n++ )
 switch( rpn.get( n ) ) {
 case "+":
 case "-":
 case "*":
 case "/":
 String s = new StringJoiner( "", "(", ")" ).add( rpn.remove( n - 2 ) ).add( rpn.remove( n - 1 ) ).add( rpn.remove( n - 2 ) ).toString();
 rpn.add( n - 2, s );
 if( rpn.size() > 1 )
 return( fromRPN( rpn ) );
 return( rpn.get( 0 ) );
 case "sqrt": // insert Your unary operator(s) here...
 StringJoiner join = rpn.get( n ).startsWith( "(" ) ? new StringJoiner( "" ) : new StringJoiner( "", "(", ")" );
 join.add( rpn.remove( n ) );
 if( rpn.get( n - 1 ).startsWith( "(" ) )
 join.add( rpn.remove( n - 1 ) );
 else
 join.add( "(" ).add( rpn.remove( n - 1 ) ).add( ")" );
 s = join.toString();
 rpn.add( n - 1, s );
 if( rpn.size() > 1 )
 return( fromRPN( rpn ) );
 return( rpn.get( 0 ) );
 }
 return( fromRPN( rpn ) );
}

You can test both types of expressions (RPN and algebraic) with 7th stone

Answer 2

If you want to do it faster I know that I once solved this with a hashMap which is much faster. The problem is that, depending on what you are going to use it for, it's harder to implement. I don't have time to show exactly how I did it now, I might come back to you, but it should give you a pointer on where to look.

• dfhwze: up-vote pending ..