java - 最小数の括弧を使用した後置から中置へ

Question

最小数の括弧を生成する中置記法へのアルゴリズム後置を探しています。

私はそれを見つけましたが、それは非常に多くの括弧を生成します: http://tajendrasengar.blogspot.com/2011/09/postfix-to-infix-algorithm.html

例えば

入力:

<ONP>abcd*/+~

結果：

<INF>~(a+b/(c*d))

Answer 1

括弧をできるだけ少なくしたい場合に必要なことは、リンク先のアルゴリズムが言っていることと似ています。でも...

• の複合オペランドごとに演算子を格納する必要がありStackます。つまり、オペランドで使用される最後の演算子です。これには1秒Stackを使用できます。nullオペランドが複合でない場合、演算子がないため、2 番目のに加算できますStack。
• String結果を括弧でカプセル化しないでください。これは、アルゴリズムの他の場所で行われます (以下を参照)。

のそれぞれから上位 2 つの値をポップすると、Stack3 つの演算子が手に入ります。

• 現在の運営者
• 最初のオペランドで最後に使用された演算子 (演算子が存在する場合)
• 2 番目のオペランドで最後に使用された演算子 (演算子が存在する場合)

これら 3 つの演算子に応じて、結合する前に、第 1 および/または第 2 オペランドを括弧でカプセル化する必要があります。

演算子の優先順位を使用して、括弧が必要かどうかを判断できます。順序は次のようになります。(none), {"*", "/"}, {"+", "-"}

• 最初のオペランドには、その演算子の優先順位が現在の演算子よりも低い場合にのみ、括弧が必要です。
• 2 番目のオペランドには、その演算子の優先順位が現在の演算子よりも低い場合、または現在の演算子が または のいずれかで同じ優先順位がある場合、括弧が必要"/"です"-"。

残りは、アルゴリズムが説明した方法で行う必要があります。

Answer 2

実装は次のとおりです。

public class PostfixToInfixConverter implements ExpressionConverter {

@Override
public String convert(String postfix) {
    String[] expressions = postfix.split("\\s");
     Deque<Expression> stack = new LinkedList<Expression>();
    for (String exp : expressions) {
        if (exp.equals("+") || exp.equals("-")) {
            String right = stack.pop().getExpression();
            String left = stack.pop().getExpression();
            Expression newExp = new Expression(right + exp + left, exp);
            stack.push(newExp);
        } else if (exp.equals("*") || exp.equals("/")) {
            String right = correctExpression(stack.pop());
            String left = correctExpression(stack.pop());
            stack.push(new Expression(right +  exp +  left, exp));
        } else {
            stack.push(new Expression(exp, ""));
        }
    }
    return stack.pop().getExpression();
}

private String correctExpression(Expression exp) {
    String result = exp.getExpression();
    if (exp.getOperatorUsed().equals("+") || exp.getOperatorUsed().equals("-")) {
        result = "(" + result + ")";
    }
    return result;
}

private static class Expression {
    String expression;
    String operatorUsed;
    public Expression(String exp, String operator) {
        this.expression = exp;
        this.operatorUsed = operator;
    }
    public String getExpression() {
        return expression;
    }
    public String getOperatorUsed() {
        return operatorUsed;
    }       
}   

}

ここに単体テストがあります

@Test
public void test() {
    ExpressionConverter converter = new PostfixToInfixConverter();
    assertThat(converter.convert("1 2 * 3 4 * + 5 *"), equalTo("5*(4*3+2*1)"));
    assertThat(converter.convert("a b + c + 2 *"), equalTo("2*(c+b+a)"));
}