Постфикс в Infix с минимальным количеством скобок

Question

Я ищу алгоритм постфикса в инфиксную нотацию, которая будет производить минимальное количество скобок.

Я обнаружил, что это приведет к множеству скобок: http://tajendrasengar.blogspot.com/2011/09/postfix-to-infix-algorithm.html

Например

Вход:

<ONP>abcd*/+~

Результат:

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

Answer 1

То, что вам нужно сделать, если вы действительно хотите использовать как можно меньше скобок, похоже на то, что говорит алгоритм, на который вы ссылаетесь. Тем не мение...

• Вы должны хранить оператор для каждого составного операнда в Stack, А именно, последний оператор, использованный в операнде. Вы могли бы использовать второй Stack за это. Если операнд не является составным, вы можете добавить null ко второму Stack, так как нет оператора.
• Не инкапсулируйте полученный результат String с круглыми скобками. Это делается в другом месте алгоритма (см. Ниже).

Когда вы открываете два верхних значения из каждого из Stacks, у вас есть 3 оператора под рукой:

• Текущий оператор
• Последний использованный оператор в первом операнде (если оператор существует)
• Последний использованный оператор во втором операнде (если оператор существует)

В зависимости от этих трех операторов, вы должны заключить первый и / или второй операнд в скобки, прежде чем объединять их.

Вы можете использовать приоритет оператора, чтобы определить, должны ли быть круглые скобки. Заказ идет так: (none), {"*", "/"}, {"+", "-"}

• Первый операнд нуждается в скобках, если и только если его оператор имеет более низкий приоритет, чем текущий оператор.
• Второй операнд нуждается в скобках, если его оператор имеет более низкий приоритет, чем текущий оператор, или если они имеют равный приоритет, когда текущий оператор либо "/" или же "-",

Остальное должно быть сделано так, как описан ваш алгоритм.

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

Answer 3

Я нашел пример решения этой проблемы. В ast библиотеке Python есть класс _Unparsing для разбора дерева AST.

В библиотеке есть функция require_parens для проверки скобок.

Пример:

      ~% python3.11
>>> import ast
>>> ast.unparse(ast.parse("(-(-1+2)+((2*3))-4)"))
'-(-1 + 2) + 2 * 3 - 4'
>>>

Если вы хотите, вы можете преобразовать дерево AST в постфиксную нотацию, используя функцию ast.walk. Связь