You can use the axioms for a stack to prove that the stack defi ned by the sequence of operations
Create an empty stack
Push a 5
Push a 7
Push a 3
Pop (the 3)
Push a 9
Push a 4
Pop (the 4)
which you can write as
(((((((new Stack()).push(5)).push(7)).push(3)).pop()).push(9)).push(4)).pop()
is exactly the same as the stack defined by the sequence
Create an empty stack
Push a 5
Push a 7
Push a 9
which you can write as
(((new Stack()).push(5)).push(7)).push(9)
Similarly, you can use the axioms to show that
(((((((new Stack()).push(1)).push(2)).pop()).push(3)).pop()).pop()).isEmpty()
is true.
a. The following representation of a stack as a sequence of push operations without any pop operations is called a canonical form:
(...(new Stack()).push()).push())... ).push()
Prove that any stack is equal to a stack that is in canonical form.
b. Prove that the canonical form is unique. That is, a stack is equal to exactly one stack that is in canonical form.
c. Use the axioms to show formally that
((((((((((new Stack()).push(6)).push(9)).pop()).pop()).push(2)).pop()).push(3)).
push(1)).pop()).peek()
equals 3.