	Jupyter at Bryn Mawr College
Public notebooks: /services/public/dblank / CS206 Data Structures / 2017-Spring / Notebooks

Stacks and Queues¶

Some sample code for binary trees:

for (int i = 0; i < 1000000; i++) {
    while (! bt.add(getRandomNumber())) {
    }
}

Stacks¶

%%file Stack.java
    
public interface Stack<T> {
    public void push(T value);
    public T pop();
}

%%file Stack.java
    
public interface Stack {
    public void push(Number value);
    public Number pop();
}

Created file '/home/dblank/public_html/CS206 Data Structures/2017-Spring/Notebooks/Stack.java'.

! javac Stack.java

%%file Node.java
    
public class Node {
    Node next;
    Number value;
    
    Node(Number value) {
        this.value = value;
    }
}

Created file '/home/dblank/public_html/CS206 Data Structures/2017-Spring/Notebooks/Node.java'.

! javac Node.java

%%file Calculator.java
    
public class Calculator implements Stack {
    Node stack;
    
    public void push(Number value) {
        Node tmp = new Node(value);
        tmp.next = stack;
        stack = tmp;
    }
    
    public Number pop() {
        Node tmp = stack;
        stack = tmp.next;
        return tmp.value;
    }
    
    public Number eval(String[] args) {
        for (int i = 0; i < args.length; i++) {
            if (args[i].equals("+")) {
                // pop value off stack
                Number num = pop();
                // get the next number
                i++;
                Double d = new Double(args[i]);
                // push the sum onto stack
                push(d + num.doubleValue());
            } else { // assume it is an Integer
                push(new Integer(args[i]));
            }
        }
        return pop();
    }
    
    public static void main(String[] args) {
        Calculator calc = new Calculator();
        System.out.println("The answer is: " + calc.eval(args));
    }
}

Created file '/home/dblank/public_html/CS206 Data Structures/2017-Spring/Notebooks/Calculator.java'.

! javac Calculator.java

! java Calculator 1 + 2 + 3

The answer is: 6.0

! java Calculator 34 + 21

Our calculator has some serious limits.

Reverse Polish Notation¶

The algorithm for evaluating any postfix expression is fairly straightforward:

While there are input tokens left
- Read the next token from input.
- If the token is a value
  - Push it onto the stack.
- Otherwise, the token is an operator (operator here includes both operators and functions).
  - It is already known that the operator takes n arguments.
  - If there are fewer than n values on the stack
    - (Error) The user has not input sufficient values in the expression.
  - Else, Pop the top n values from the stack.
  - Evaluate the operator, with the values as arguments.
  - Push the returned results, if any, back onto the stack.
If there is only one value in the stack
- That value is the result of the calculation.
Otherwise, there are more values in the stack
- (Error) The user input has too many values.

(After https://en.wikipedia.org/wiki/Reverse_Polish_notation)

5 1 2 + 4 * + 3 -

Input	Action	Stack at end	Notes
5	Operand	5	Push onto stack.
1	Operand	1 5	Push onto stack.
2	Operand	2 1 5	Push onto stack.
+	Operator	3 5	Pop the two operands (1, 2), calculate (1 + 2 = 3) and push onto stack.
4	Operand	4 3 5	Push onto stack.
×	Operator	12 5	Pop the two operands (3, 4), calculate (3 * 4 = 12) and push onto stack.
+	Operator	17	Pop the two operands (5, 12), calculate (5 + 12 = 17) and push onto stack.
3	Operand	3 17	Push onto stack.
−	Operator	14	Pop the two operands (17, 3), calculate (17 - 3 = 14) and push onto stack.
	Result	14

%%file RPN.java
    
public class RPN implements Stack {
    Node stack;
    
    public void push(Number value) {
        Node tmp = new Node(value);
        tmp.next = stack;
        stack = tmp;
    }
    
    public Number pop() {
        Node tmp = stack;
        stack = tmp.next;
        return tmp.value;
    }
    
    public Number eval(String[] args) {
        for (int i = 0; i < args.length; i++) {
            if (args[i].equals("+")) {
                // pop value off stack
                Number num1 = pop();
                Number num2 = pop();
                // push the sum onto stack
                push(num1.intValue() + num2.intValue());
            } else if (args[i].equals("*")) {
                // pop value off stack
                Number num1 = pop();
                Number num2 = pop();
                // push the sum onto stack
                push(num1.intValue() * num2.intValue());
            } else if (args[i].equals("-")) {
                // pop value off stack
                Number num1 = pop();
                Number num2 = pop();
                // push the sum onto stack
                push(num2.intValue() - num1.intValue());
            } else { // assume it is an Integer
                push(new Integer(args[i]));
            }
        }
        return pop();
    }
    
    public static void main(String[] args) {
        RPN calc = new RPN();
        System.out.println("The answer is: " + calc.eval(args));
    }
}

Created file '/home/dblank/public_html/CS206 Data Structures/2017-Spring/Notebooks/RPN.java'.

! javac RPN.java

! java RPN 5 1 2 + 4 \* + 3 -

The answer is: 14

Queue¶

First-in First-Out

%%file Queue.java
    
public class Queue implements Stack {
}

Double Ended Queue¶

public class DoubleEndedQueue {

}

or for short:

public class Deque {

}

Pronounced "deck".

Overload¶

When a class has many methods with the same name, but different signatures.

public class BinaryTree {
    void count() {
    }

    void count(Node node) {
    }
}

not the same as:

Overridden¶

When a extended class method has the same name as the parent. Recall Inheritance.ipynb.

%%file TestMe.java

public class TestMe {
    void count(Node node, boolean other) {
    }

    void count(Node node) {
    }
}

Created file '/home/dblank/public_html/CS206 Data Structures/2017-Spring/Notebooks/TestMe.java'.

! javac TestMe.java

Jupyter at Bryn Mawr College