teaching machines

CS 245 Lecture 19 – Stack Algorithms

November 7, 2013 by . Filed under cs245, fall 2013, lectures.

Agenda

Program This

  1. Write LinkedList.getFirst. Write LinkedList.removeFirst, which chops off and returns the first element. What happens if the list is empty?
  2. Write LinkedList.getLast. Write LinkedList.removeLast, which chops off and returns the last element. What happens if the list is empty?

Code

test.html

</alan>

<html>

<body>
adsfads
</body>

</html>

TagChecker.java

package lecture19;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Stack;
import javax.swing.JFileChooser;

public class TagChecker {
  public static void main(String[] args) throws FileNotFoundException {
//    JFileChooser fileChooser = new JFileChooser();
    
//    String homeDirectory = System.getProperty("user.home");
//    System.out.println(homeDirectory);
    
    Scanner in = new Scanner(new File("src/lecture19/test.html"));
    in.useDelimiter("(\\A|>)[^<]*(\\Z|<)");
    
    Stack<String> unclosedTags = new Stack<String>();
    
    while (in.hasNext()) {
      String tag = in.next();
      
      if (!tag.startsWith("/")) {
        unclosedTags.push(tag);
      } else {
        
        if (unclosedTags.isEmpty()) {
          System.out.println(tag + " was never opened");
          System.exit(1);
        } else if (unclosedTags.peek().equals(tag.substring(1))) {
          unclosedTags.pop();
        } else {
          System.out.println(unclosedTags.peek() + " wasn't closed before " + tag);
          System.exit(1);
        }
      }
    }
    
    in.close();

    if (unclosedTags.isEmpty()) {
      System.out.println("A-OK");
    } else {
      System.out.println(unclosedTags.peek() + " was not closed");
    }
    
    // while there's a tag to read
    //   read it
    //   if its an opening tag
    //     let's mark that we're looking for a closing tag
    //   else
    //     let's see that we have an opened tag
  }
}

Haiku

Hansel and Gretel
Birds ate their List<Crumb>
Stack<Crumb> would have broken beaks
Protect you from you