5
\$\begingroup\$

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());        
       }       
    }
\$\endgroup\$
  • 5
    \$\begingroup\$ "it's not fast enough" – for which input? How long does it take? Is there a concrete time limit that you need to achieve? \$\endgroup\$ – Martin R Sep 7 '18 at 12:52
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ up-vote pending .. \$\endgroup\$ – dfhwze Aug 13 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.