Postfix to Infix - Parenthesis

Question

I'm trying to implement postfix to infix and infix to postfix (using stacks) and everything is going well except that when I'm converting from postfix I can't come up with the idea how to deal with parenthesis. It says I have to use minimum number of parenthesis. For example:

<POSTFIX> ab+c*da-fb-*+
<INFIX> (a+b)*c+(d-a)*(f-b)

<POSTFIX>ab~c+*de-~/
<INFIX>a*(~b+c)/~(d-e)

private static class Postfix {
    private void convert(String postfix) {
        Stack<String> s = new Stack<>();

        for (int i = 0; i < postfix.length(); i++) {
        char o = postfix.charAt(i);
        if (isOperator(o)) {
            if (o == '~') {
            String a = s.pop();
            s.push(o + a);
            }
            else {
            String b = s.pop();
            String a = s.pop();
            s.push(a + o + b);
            }
        } else s.push("" + o);
        }
        System.out.println("<INF>" + s.pop().toString());
    }
}

Any help will be much appreciated.

Answer 1

Well, if you can assume that all the variable names are single chars (as it seems you do), then you could do something like:

private static class Postfix {
    private void convert(String postfix) {
        Stack<String> s = new Stack<>();

        for (int i = 0; i < postfix.length(); i++) {
            char o = postfix.charAt(i);
            if (isOperator(o)) {
                if (o == '~') {
                    String a = s.pop();
                    if ( a.size() > 1 ) { a = "(" + a + ")"; }
                    s.push("" + o + a);
                }
                else {
                    String b = s.pop();
                    String a = s.pop();
                    if ( o == '*' || o == '/' ) {
                        if ( b.size() > 1 ) { b = "(" + b + ")"; }
                        if ( a.size() > 1 ) { a = "(" + a + ")"; }
                    }
                    s.push("" + a + o + b);
                }
            } else {
                s.push("" + o);
            }
        }
        System.out.println("<INF>" + s.pop().toString());
    }
}

The problem with this, is it'll wrap the left-hand side of a multiply with parentheses, regardless of whether that operation "needs" it.

To do more, you'd need to create a class (Operation or some such) containing a left-side String, right-side String, and operator. Then, where I currently just check to see if the b or a is larger than 1, you could check what kind of operator it had instead.

Ok, here's the more complete answer, I think:

private static class Postfix {
    class Operation {  // internal class
       Operation lhs;
       Operation rhs;
       char operator;
       char varname;
       boolean shouldParens = false;

       Operation( Operation l, char operator, Operation r ) {
          this.lhs = l;
          this.rhs = r;
          this.operator = operator;
       }

       Operation( char name ) {
          this.varname = name;
       }

       public void addParensIfShould( char newop ) {
          if ( !varname ) {
              if ( newop == '~' ) {
                 this.shouldParens = true;
              }
              else if ( newop == '*' || newop == '/' ) {
                 if ( this.operator == '+' || this.operator == '-' ) {
                    this.shouldParens = true;
                 }
              }
          }
       }

       public String toString() {
          if ( varname ) return "" + varname;
          StringBuilder b = new StringBuilder();
          if ( shouldParens ) b.append("(");
          if ( lhs ) { b.append( lhs.toString() ); }
          b.append( operator );
          if ( rhs ) { b.append( rhs.toString() ); }
          if ( shouldParens ) b.append(")");
          return b.toString()
       }
    };

    private void convert(String postfix) {
        Stack<Operation> s = new Stack<>();

        for (int i = 0; i < postfix.length(); i++) {
            char o = postfix.charAt(i);
            if (isOperator(o)) {
                if (o == '~') {
                    Operation a = s.pop();
                    a.addParensIfShould( o );
                    Operation newOp = new Operation( null, o, a );
                    System.out.println( "Adding uni op " + newOp )
                    s.push(newOp);
                }
                else {
                    Operation b = s.pop();
                    Operation a = s.pop();
                    a.addParensIfShould( o );
                    b.addParensIfShould( o );
                    Operation newOp = new Operation( a, o, b );
                    System.out.println( "Adding bi op " + newOp )
                    s.push(newOp);
                }
            } else {
                Operation newOp = new Operation( o ); // it's just a varname
                System.out.println( "Adding varname op " + newOp )
                s.push(newOp);    
            }
        }
        System.out.println "<INF>" + s.toString()
    }
}