Алгоритм преобразования инфикса в постфикс с помощью Python

Разумеется, тот, который вы только что нашли. Не забывайте контекст:

    **While** the last item in *operators* is not an open parenthesis **do**
        Remove the last item from *operators* and append it to *postfix*
      Remove the open parenthesis from *operators*

Цикл while удаляет элементы до тех пор, пока последний элемент в операторах не станет открывающей скобкой, а затем вы удалите ее.

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

for infix in '3+4*5', '(3+4)*5':

    precedence = '+-*/'.index
    operators = []
    postfix = []
    for token in infix:
        if token.isdigit():
            postfix.append(token)
        if token in '+-*/':
            while operators and operators[-1] != '(' and precedence(token) < precedence(operators[-1]):
                postfix.append(operators.pop())
            operators.append(token)
        if token == '(':
            operators.append(token)
        if token == ')':
            while operators[-1] != '(':
                postfix.append(operators.pop())
            operators.pop()
    while operators:
        postfix.append(operators.pop())

    print(*postfix)

Попробуйте это онлайн!):

3 4 5 * +
3 4 + 5 *

Кажется, что отступ немного искажен звездочками **, которые есть в некоторых строках, но отсутствуют в других.

    **While** the last item in *operators* is not an open parenthesis **do**
        Remove the last item from *operators* and append it to *postfix*
     Remove the open parenthesis from *operators*

В начале третьей строки не должно быть лишнего пробела. Вместо этого должно быть так:

    While the last item in *operators* is not an open parenthesis do
        Remove the last item from *operators* and append it to *postfix*
    Remove the open parenthesis from *operators*

Поскольку инструкция Remove идет сразу после окончания цикла While, а условие цикла While — «последний элемент в операторах не является открывающей скобкой», это означает, что когда цикл While заканчивается, последний элемент в операторах должен быть открывающей скобкой.

Это единственная открывающая скобка, которую вы можете увидеть и удалить на данном этапе.

Важно отметить, что операторы представляют собой стек, также называемый структурой «последним пришел — первым вышел»: вы можете видеть, получать доступ и удалять только его последний (или «верхний») элемент. Итак, эта открывающая скобка — единственная, которую вы можете видеть на данный момент, и единственная, которую вы можете удалить.

Обратите внимание, что эти три строки кода работают корректно только в том случае, если в инфиксном выражении правильно сопоставляются круглые скобки. Если вы запустите этот алгоритм точно так, как написано для выражения типа 3+4), которое содержит несовпадающую закрывающую скобку, цикл While «Пока последний элемент не является открывающей скобкой, удалите последний элемент» удалит все элементы, и тогда стек будет пусто, и программа выйдет из строя, поскольку вы попытаетесь удалить элемент из пустого стека.