teaching machines

CS 245 Lecture 20 – More Stack

November 12, 2013 by Chris Johnson. Filed under cs245, fall 2013, lectures.

Agenda

• what ?s
• is-a vs. has-a
• program this
• solve this
• postfix calculator
• searching the filesystem

TODO

• Write a static method reverseString that accepts a String parameter and returns the reversed version. Use a stack instead of the more straightforward algorithm. 1/4 sheet.

Program This

Solve This

Code

Stack.java

package lecture20;

import java.util.LinkedList;

public class Stack<T> {
  private LinkedList<T> items;
  
  public Stack() {
    items = new LinkedList<T>();
  }
  
  public boolean isEmpty() {
    return items.isEmpty();
  }

  public int size() {
    return items.size();
  }
  
  public void push(T itemToAdd) {
    items.add(itemToAdd);
  }
  
  public T pop() {
    return items.removeLast();
  }
  
  public T peek() {
    return items.getLast();
  }
  
//  public void push(T itemToAdd) {
//    super.pu
//  }
  
  public static void main(String[] args) {
    Stack<Integer> numbers = new Stack<Integer>();
    
    numbers.push(10);
//    process(numbers);
//    numbers.add(0, 20);
    
    System.out.println(numbers.peek());
    System.out.println(numbers.pop());
  }
  
//  public static void process(LinkedList<Integer> l) {
//    l.add(0, 56);
//  }
}

Postfix.java

package lecture20;

import java.util.Scanner;

public class Postfix {
  public static void main(String[] args) {
    System.out.println("Enter your maths: ");
    Scanner in = new Scanner(System.in);

    Stack<Integer> operands = new Stack<Integer>();

    while (in.hasNext()) {
      if (in.hasNextInt()) {
        int number = in.nextInt();
        operands.push(number);
      } else {
        String operator = in.next();

        int b = operands.pop();
        int a = operands.pop();

        if (operator.equals("+")) {
          operands.push(a + b);
        } else if (operator.equals("-")) {
          operands.push(a - b);
        } else if (operator.equals("*")) {
          operands.push(a * b);
        } else if (operator.equals("/")) {
          operands.push(a / b);
        } else {
          throw new RuntimeException("Bad math, you foobag!");
        }
      }
    }
    
    int result = operands.pop();
    System.out.println("Your answer is: " + result);
  }
}

DiskSearcher.java

package lecture20;

import java.io.File;

public class DiskSearcher {
  public static void main(String[] args) {
    Stack<File> directoriesToSearch = new Stack<File>();
    
    directoriesToSearch.push(new File("/Users/johnch/Desktop"));
 
    while (!directoriesToSearch.isEmpty()) {
      // pull off a directory
      // look at its files
      // if there's a match, we're done
      // or if there's a directory, add it to the stack
      
      File dirToSearch = directoriesToSearch.pop();
      File[] contents = dirToSearch.listFiles();
      for (File entry : contents) {
        if (entry.getName().endsWith(".png")) {
          System.out.println(entry);
        } else if (entry.isDirectory()) {
          directoriesToSearch.push(entry);
        }
      }
    }
  }
}

Haiku