One impact that stacks have had in the area of computer organization is in the realization of socalled stack machines. Here, the entries in a stack are arithmetic operands and the machine instruction set contains arithmetic operators.
For example for a stack $s$, MUL
is equivalent to s.push(s.pop() * s.pop())
. All other elementary operations (ADD
, DIV
, SUB
) are defined in a similar way. What will POP
return once the stack machine evaluates the operations below?
1 2 3 4 5 6 7 8 9 

The objective of Towers of Hanoi puzzle is to move all discs to stack three, obeying the following simple rules:
We can consider each stack as a stack object. For example moving the purple disk (the top disk on the second stack) to the third stack would require the following two operations:
stack_2.pop()
stack_3.push(purple)
In general, moving a disk from the top of one stack to the top of another will require two operations in a row. Consider the nearly complete puzzle below
How many operations are needed if the above puzzle is solved using the fewest number of stack operations?
Consider the standard algorithm for converting a decimal number (base 10) into a binary number (base 2). This algorithm makes use of a single stack and works by continually taking the modulo $2$ of the number and also continually dividing it by two. This allows us to finally obtain the bits of the integer.
The number of times $n$ a number has to be pushed to this stack in order to be fully converted can be expressed as a function $f(n)$. What is $f(n)$?