4. Chapter 4 Solutions

Written by Kelvin Lau & Jonathan Sande

Solution to Challenge 1

One of the prime use cases for stacks is to facilitate backtracking. If you push a sequence of values into the stack, sequentially popping the stack will give you the values in reverse order.

void printInReverse<E>(List<E> list) {
  var stack = Stack<E>();

  for (E value in list) {
    stack.push(value);
  }

  while (stack.isNotEmpty) {
    print(stack.pop());
  }
}

If you try it with ['d', 'r', 'a', 'w', 'e', 'r'] you’ll get a reward. :]

The time complexity of pushing all of the list elements into the stack is O(n). The time complexity of popping the stack to print the values is also O(n). Overall, the time complexity of this algorithm is O(n).

Since you’re allocating a container (the stack) inside the function, you also incur an O(n) space complexity cost.

Note: The way you should reverse a list in production code is to call the reversed method that List provides. This method is O(1) in time and space. This is because as an iterable it’s lazy and only creates a reversed view into the original collection. If you traverse the items and print out all of the elements, it predictably makes the operation O(n) in time while remaining O(1) in space.

Solution to Challenge 2

To check if there are balanced parentheses in the string, you need to go through each character of the string. When you encounter an opening parenthesis, you’ll push that onto a stack. Conversely, if you encounter a closing parenthesis, you should pop the stack.

Lufe’q cnas lle tiso jausb liri:

bool checkParentheses(String text) {
  var stack = Stack<int>();

  final open = '('.codeUnitAt(0);
  final close = ')'.codeUnitAt(0);

  for (int codeUnit in text.codeUnits) {
    if (codeUnit == open) {
      stack.push(codeUnit);
    } else if (codeUnit == close) {
      if (stack.isEmpty) {
        return false;
      } else {
        stack.pop();
      }
    }
  }
  return stack.isEmpty;
}

Dxo divu kivwricimd oh qzer egdumantg ed I(y), vkebe n er xfe zimvot ow qefa olofy ak gdo sbkoqm. Htuz epzaqovlw ufde aqbacj er A(c) kqara qofnguqoph tuxz hie ti gxa atemi eb lzu Cdadh mugo hmguptasi.