Zamiana wyrażenia na ONP

Stos, kolejka i odwrotna notacja polska - Algorytmy: zakres rozszerzony (Python)

Zapis zwykły zamienia się na ONP stosem operatorów (algorytm stacji rozrządowej). Liczby trafiają od razu do wyniku. Operator przed odłożeniem na stos zdejmuje z niego operatory o priorytecie nie niższym (mnożenie przed dodawaniem). Nawias otwierający odkładamy, a zamykający zdejmuje operatory aż do otwierającego. Tokeny w wyrażeniu są rozdzielone spacjami.

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


def to_rpn(expression):
    output = []
    stack = []
    for token in expression.split():
        if token in PRIORITY:
            while stack and stack[-1] != "(" and PRIORITY[stack[-1]] >= PRIORITY[token]:
                output.append(stack.pop())
            stack.append(token)
        elif token == "(":
            stack.append(token)
        elif token == ")":
            while stack[-1] != "(":
                output.append(stack.pop())
            stack.pop()
        else:
            output.append(token)
    while stack:
        output.append(stack.pop())
    return " ".join(output)


print(to_rpn("3 + 4 * 2"))
print(to_rpn("( 3 + 4 ) * 2"))

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Algorytmy: zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.