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());        
       }       
    }

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.