Handling Parenthesis While Converting Infix Expressions to Postfix Expressions

Handling parenthesis while converting infix expressions to postfix expressions

You need to push the left parenthesis onto the stack, and process the stack like so when you encounter a right parenthesis:

// opening (
if (in_fix.peek().type == 4) {   
    post_fix.push(in_fix.pop());
}
//closing )
if(in_fix.peek().type == 5){
    while(!(post_fix.isEmpty() || post_fix.peek().type == 4)){
         postfixstr.append(post_fix.pop());
    }
    if (post_fix.isEmpty())
        ; // ERROR - unmatched )
    else
        post_fix.pop(); // pop the (
    in_fix.pop(); // pop the )
} 

Correct spacing between expressions after converting from infix to postfix expression

while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek()))
                postfix += " " + (stack.pop());

Add an extra space before you add the operator everywhere you add an operator

Converting infix to postfix, do I need precendence table if I have brackets

If the infix expression is fully parenthesized, then no, you don't need a precedence table.

Problems with stack in an infix to postfix converter

Aha! You need "stack peek" when comparing rank of topmost.. because "top" must be popping the element off.

Try stack.peek() or equivalent. What actually class & library are you using, for the stack? s[top] is not valid syntax.

Back at answer #1, I started to write a peekRank() function for you, thinking there was an issue with checking when the stack was empty.. but stopped when I saw you had an empty-check.

It appears you weren't peek()ing the top correctly, though.

---

[Earlier #2 -- Not the issue]

Have you considered the ) handling? Your ( code appears to have a guard for stack-empty on it.

[Earlier # 1-- Not exactly the issue]

Put an 'ENTIRE EXPRESSION' pseudo-token on the stack for the entire duration of processing, so you have a non-empty stack, or answer a rank despite there being no surrounding expression/ enclosing token.

Postfix to Infix - Parenthesis

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

---

Related Topics