Postfix to Infix - Parenthesis

Question

Я пытаюсь реализовать постфикс для infix и infix для postfix (используя стеки), и все идет хорошо, за исключением того, что когда я конвертирую из постфикса, я не могу придумать, как дело с круглыми скобками. В нем говорится, что я должен использовать минимальное число скобок. Например:

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

Любая помощь будет очень признательна.

Answer 1

Ну, если можно предположить, что все имена переменных одиночные символы (как это кажется, что вы делаете), то вы могли бы сделать что-то вроде:

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

Проблема с этим, он будет обернуть левая часть умножения с круглыми скобками, независимо от того, нужна ли ей эта операция.

Чтобы сделать больше, вам нужно создать класс (Операция или некоторые такие), содержащие левую строку, правую строку и оператор. Затем, когда я сейчас проверяю, есть ли b или a больше 1, вы можете проверить, какой именно оператор он имел.

Хорошо, вот более полный ответ, я думаю:

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