Converting Reverse Polish to Infix Notation in Java

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

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

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

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.

• up-vote pending .. – dfhwze Aug 13 '19 at 18:09