CS111 Lab 10

Stack



A Stack is a container that implements the Last-in-First-Out (LIFO) protocol. The Java library provides a simple Stack class.



Part I:
Give the output for the following segments of code. NOTE: No errors exist.

  1. Exercise 1: What does the code below produce?
    Stack <String> words = new Stack <String>();
    String play;
    words.push("Bobo");
    words.push("Red");
    play = words.peek();
    words.push("Biffy");
    play = words.pop();
    words.push("Blue");
    words.push("White");
    while (!words.isEmpty()) {
      play = words.pop();
      System.out.println(play);
    }



  2. li>
  3. Exercise 2: What does the code below produce?
    Stack <String> words = new Stack <String>();
    words.push("Bobo");
    words.pop();
    words.push("Red");
    words.push("Biffy");
    words.pop();
    words.push("Blue");
    words.push("White");
    words.pop();
    while (!words.isEmpty()) {
      System.out.println(words.peek());
      System.out.println(words.pop());
    }




  4. Exercise 3: What does the code below produce?
    Stack <String> words = new Stack <String>();
    string s;
    words.push("Bobo");
    s = words.peek();
    words.push("Red");
    s += words.peek();
    words.push("Biffy");
    s += words.peek();
    words.push("Blue");
    s += words.peek();
    words.push("White");
    s += words.peek();
    System.out.println(s);



  5. Exercise 4: What does the code below produce?
    Stack <String> words = new Stack <String>();
    String s;
    words.push("Bobo");
    s = words.peek();
    words.push("Red");
    s += words.peek();
    words.push("Biffy");
    s += words.peek();
    words.push("Blue");
    s += words.peek();
    words.push("White");
    s += words.peek();
    while (!words.isEmpty()) {
      s += words.peek();
      words.pop();
    }
    System.out.println( s);






Part II: Infix, postfix, and prefix notation for arithmetic expressions.


    Algorithm for evaluating a postfix expression by hand.
      while (expression contains operators)
      1. Scan the expression from left to right until an operator is found.
      2. Evaluate the postfix expression consisting of this operator and the two operands immediately to its left.
      3. Replace the two operands and the operator by this value.
    Translate each of the following postfix expressions into infix.
  1. 4 5 * 6 - 7 / 8 +
  2. 4 5 6 * 7 8 + / -
  3. 6 5 4 3 2 1 - + / + *
  4. 6 5 * 4 3 2 + 1 - / +


    Translate each of the following infix expressions into postfix.
  5. 6 + 4 - 2
  6. 6 * 4 / 7
  7. 6 * 4 / (7 - (3 + 2))
  8. 6 * 4 / (7 - 3 + 2))
  9. (2 + 7) * (8 / (6 - ( 3 + 1)))
  10. (2 + 7) * (8 / ((6 - 3) + 1))






Part III


  1. Write a short Java application that translates any given postfix expression into infix.



Part IV:
Create a perfect maze.





MazeCell.java





PerfectMaze.java