A stack is an order collection of objects which can only be operated on in two ways. We can add an object to the end of the collection, known as pushing an object onto the stack, or we can remove the last item on the stack, known as popping the stack. We can only inspect the last item on the stack too. The rest of the collection is hidden from us, strictly speaking, although this depends greatly on the implementation of the stack. The airport luggage example illustrates the working of a stack. The first person to check their baggage in finds that their baggage is the last available at the other end on the conveyor belt. Sometimes being late does pay off. In fact the baggage will come out in the reverse order it was put in.
Stacks are one of those tools in every programmer's toolkit. Which is not to say they can solve every problem, but they are found in a surprising variety of solutions. The key concept to understand about a stack is that they are good for reordering things in a variety of ways, not just for reversing things. They are also good a 'remembering things' so they can be undone, hence the term 'undo stack'.
Python offers us a convenient set of methods to operate lists as stacks.
<list>[-1].<list>.pop(),
that removes the last value from the list and returns it.Python 2.4.3 (#1, Oct 2 2006, 21:50:13) [GCC 3.4.6 (Gentoo 3.4.6-r1, ssp-3.4.5-1.0, pie-8.7.9)] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> stack = [] >>> stack.append(3) >>> stack [3] >>> stack.append(2) >>> stack [3, 2] >>> stack.append(1) >>> stack [3, 2, 1] >>> stack.pop() 1 >>> stack.pop() 2 >>> stack.pop() 3 >>>
There are various ways to write down an arithmetic expression. We are used to a method know as infix notation, called such because operator's are written in between operands. Infix notation suffers a severe drawback, in that the precedence of operators is implicit and changes the order of evaluation. Consider the expression '4*(2+3)'. We cannot simply evaluate this expression from left to right. We want to change the order in which it is evaluated to match the order of precedence. Order changing, sounds like a job for soooperr-stack!
The other two notations are called prefix and postfix notation respectively. Prefix notation lists operators prior to their operands, whilst postfix lists operators after their respective operands. We would write the former expression as '*4+23' or '423+*' in prefix and postfix notation respectively. Although basically equivalent except for order, computer science has settled on postfix as a preferred method for evaluating expressions. Note that the precedence of the operators in in the post- and pre-fix notations does not need brackets to define a change in precedence. We can evaluate these expressions from left to right, as such in the case of prefix notation
Since it is trivial to evaluate a postfix (or prefix) expression, we want to write a function that converts an infix expression to a postfix one. For the sake of example, we shall only allow single digit numbers, and the binary operators '+', '-', '*', '/', and parentheses.
def postfix(infix):
operator_stack = []
output_queue = ''
for c in infix:
if c.isdigit():
output_queue += c
elif c in ['+', '-', '*', '/']:
while len(operator_stack) > 0
and operator_stack[len(operator_stack)-1] in ['*', '/']
and c in ['+', '-']:
output_queue += operator_stack.pop()
operator_stack.append(c)
elif c == '(':
operator_stack.append(c)
elif c == ')':
o = operator_stack.pop()
while o != '(':
output_queue += o
o = operator_stack.pop()
while len(operator_stack) > 0:
output_queue += operator_stack.pop()
return output_queue