Here are suggested solutions to some of the exercises about stacks, queues and lists.
The idea is to go through the program and use a counter to track how deeply nested the current position is. This counter behaves like a stack where we don’t care about the elements, only the size (instead of push/pop, we increment/decrement).
comments = 0
for each character in program:
if character == "{":
comments += 1
else if character == "}":
if comments == 0:
throw error "comment end without start"
comments -= 1
else:
if comments == 0:
add character to new program
if comments > 0:
throw error "comment start without end"
Assuming we use a dynamic array to store the new program, the time complexity of this algorithm is linear in the length of the original program (i.e., O(n)).
For the hard part, we really have to use a stack.
There are different kinds of nested comments, { ... } (type A) and [ ... ] (type B).
When we encounter {, we push “A” onto the stack.
Similarly, when we encounter [, we push “B”.
When we encounter }, we pop from the stack and check that we get “A”.
Similarly, when we encounter ], we pop from the stack and check that we get “B”.
After going over the whole program, we check that the stack is empty (otherwise we have an unclosed comment).
Here’s an explanation of postfix expressions together with a high-level description of the algorithm. The main idea can be summarised as follows:
Solution:
stack = new Stack()
for each token in the input stream:
if token == ".":
print stack.pop()
else if token == "+":
stack.push(stack.pop() + stack.pop())
else if token == "+":
stack.push(stack.pop() + stack.pop())
else if token == "-":
stack.push(stack.pop() + stack.pop())
else if token == "*":
stack.push(stack.pop() + stack.pop())
else:
stack.push(token parsed as an integer)
Regardless of the order in which you give the enqueue/dequeue operations, the result will always be the same: the elements are returned in the same order as they were enqueued.
So if you enqueue the numbers 0 to 9, then the only sequence that can occur is 0, 1, …, 9.
This is a variant of a dynamic array.
class UnlimitedSizeArray:
array = new Array of size 1
get(index):
return array[index]
# Here is one way to implement `set`.
set(index, value):
# Repeatedly double the array until it's big enough
while index >= array.size():
resize(array.size()*2)
array[index] = value
# Here is another way. Both ways work!
set(index, value):
# If the array is too small, increase its size.
# But, to avoid having to copy the array too often,
# at least double the size of the array.
if index >= array.size():
resize(max(array.size()*2, index+1))
array[index] = value
# A private method to resize the array.
resize(newSize):
oldArray = array
array = new Array of size newSize
for i in 0 ... array.size()-1:
array[i] = oldArray[i]
This is much trickier than A3!
Suppose the sequence looks like this: […, a, …, b, …, c, …], where there might or might not be numbers between a, b and c. Now, if a > b, a > c and b < c, then the sequence is impossible!
Informal proof: When a is popped, we know that both b and c must be on the stack (because they are pushed in numerical order). But b was pushed earlier than c (because b < c), and therefore b cannot be popped before c is popped.
Heading “Exercises” on the book website: https://algs4.cs.princeton.edu/13stacks/
Heading “Web Exercises” on the book website: https://algs4.cs.princeton.edu/13stacks/
Linked list exercises from the book
previous = null
current = list.first
while current is not null:
if current.item is not equal to key:
previous = current
else if previous is null:
list.first = current.next # we remove the first element in the list
else:
previous.next = current.next # we remove an inner element
current = current.next
max = 0
current : Node = list.first
while current is not null:
if current.item > max:
max = current.item
current = current.next
Creative problems from the book