Algorithm for converting infix to postfix with Python

Question

I am attempting to write up the following algorithm (provided in ordinary English) in Python for converting simple mathematical expressions from infix form to postfix form:

Create a new empty list, 'operators'
Create a new empty list 'postfix'

For each token in the infix expression
  If the token is an integer then
    Append the token to 'postfix'
  If the token is an operator then
    While 'operators' is not empty and the last item in 'operators' is not an open parenthesis
    and precedence(token) < precedence(last item in 'operators') do
        Remove the last item from 'operators' and append it to 'postfix'
      Append the token to 'operators'
  If the token is an open parenthesis then
    Append the token to 'operators'
  If the token is a close parenthesis then
    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 'operators' is not the empty list do
  Remove the last item from 'operators' and append it to 'postfix'

Return 'postfix' as the result of the algorithm

However, I am a little puzzled by the "Remove the open parenthesis from operators" line. I have seen cases where there is more than one open parenthesis in operators at one time. In which case, which one should be removed?

Answer 1

The indentation appears to be a bit mangled by the asterisks ** that are on some lines but not others.

    **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*

There shouldn't be an extra space at the beginning of the third line. Instead it should be like this:

    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*

Since the Remove instruction comes directly after the end of the While loop, and the condition of the While loop is "the last item in operators is not an open parenthesis", it means that when the While loop ends, the last item in operators must be an open parenthesis.

This is the only open parenthesis you can see and remove at this point.

Importantly, note that operators is a stack, also called a last-in first-out structure: you can only ever see, access and remove its last (or "top") element. So, this open parenthesis is the only one that you can see at this point, and the only one that you can remove.

Note that these three lines of code only work correctly under the assumption that parentheses are correctly matched in the infix expression. If you run this algorithm exactly as written on an expression like 3+4), which contains an unmatched closed parenthesis, the While loop "While the last item is not an open parenthesis, remove the last item" will remove all items and then the stack will be empty and the program will crash since you attempt to remove an item from an empty stack.

Answer 2

The one you just found, of course. Don't forget the context:

    **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*

The while loop removed stuff until the last item in operators is an open parenthesis, and then you remove that one.

I wanted to see the algorithm in a less wordy easier to read format, so I just did write a simplistic Python version.

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)

Attempt This Online!):

3 4 5 * +
3 4 + 5 *