java - 后缀到中缀 - 括号

Question

我正在尝试实现后缀到中缀和中缀到后缀(使用堆栈)，一切都很顺利，除了当我从后缀转换时我无法想出如何处理括号的想法。它说我必须使用最少数量的括号。例如:

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

这样做的问题是，它会将乘法的左侧用括号括起来，无论该操作是否“需要”它。

要执行更多操作，您需要创建一个包含左侧字符串、右侧字符串和运算符的类(Operation 或类似的类)。然后，我目前只是检查 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()
    }
}