Convert prefix to infix with minimum number of parentheses

Question

Right now this is my code:

precedence = {
    "+": 1,
    "-": 1,
    "*": 2,
    "/": 2,
    "": 0
}

def is_operator(token):
    ope = set(['+', '-', '*', '/'])
    return token in ope

def prefix_to_infix(expression):
    stack = []

    for pos, i in enumerate(expression):
        if is_operator(i):
            value1 = stack.pop()
            value2 = stack.pop()
            result = f"{value1}{i}{value2}"

            next_ope = check_next_operator(pos, expression)

            # Adds parenthesis if needed
            if compare_precedence(i, next_ope):
                result = f"{result}"             

            stack.append(result)
        else:
            stack.append(str(i))

    return result

def check_next_operator(pos, expression):
    i = pos + 1
    while i < len(expression):
        if is_operator(expression[i]):
            return expression[i]
        i += 1
    return ""

def compare_precedence(actual, next):
    if precedence[actual] <= precedence[next] and precedence[next] != 0:
        return True
    else:
        return False

However, when I try to print the infix value of + / - 9 4 * 5 - 7 3 6, the parentheses between (5 * (7 - 3)) are missing. This, of course, is because - has less precedence than *. Also, in cases like - + - - - + 7 8 * / 5 4 2 6 * 7 2 3 0 it returns more parenthesis than what it should have.

NOTE: the expression i'm passing is already backwards, meaning it's been converted to its postfix form: ['6', '3', '7', '-', '5', '*', '4', '9', '-', '/', '+']

I am thinking of an approach but I'm not sure if it would work:

• If the next operator has bigger precedence: add parentheses
• If the next operator has the same precedence: only add parentheses if it's a different operator or if this operator isn't commutative.
• If the next operator has less precedence: check if there are operations left for this expression. If there are operations left with the same operator, only add parenthesis if this operator is not conmutative; if it's a different operator, then add parenthesis; if there are no operations left with this expression, don't add parentheses.

Answer 1

@Lonenebula posted a good algorithm in this answer to convert postfix to infix with minimal number of parentheses, which keeps track of the last operator used to produce each composite operand, and adds parentheses to the left operand if its last operator has less precedence than that of the current operator, and adds paretheses to the right operand with the same condition, but also when the precedence of the last operator for the right operand is less than that of the current operator, and the current operator is non-communicative (i.e. - or /).

Here's an implementation of the algorithm:

precedence = {
    '+': 1,
    '-': 1,
    '*': 2,
    '/': 2
}
noncommunicative = '-/'

def prefix_to_infix(prefix):
    stack = []
    for token in reversed(prefix):
        if precedence_current := precedence.get(token):
            value_left, precedence_left = stack.pop()
            value_right, precedence_right = stack.pop()
            if 0 < precedence_left < precedence_current:
                value_left = f'({value_left})'
            if (
                0 < precedence_right < precedence_current or
                precedence_right == precedence_current and
                token in noncommunicative
            ):
                value_right = f'({value_right})'
            stack.append((f'{value_left}{token}{value_right}', precedence_current))
        else:
            stack.append((token, 0))
    return stack[0][0]

print(prefix_to_infix('+/-94*5-736'))
print(prefix_to_infix('-+---+78*/5426*7230'))

so that:

print(prefix_to_infix('+/-94*5-736'))
print(prefix_to_infix('-+---+78*/5426*7230'))

outputs:

(9-4)/(5*(7-3))+6
7+8-5/4*2-6-7*2+3-0

Demo: https://ideone.com/lewcMb