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?
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.