Using stacks to do math

 Expressions in math can be ambiguous. Every few months, something like “6/(2+1)*2” goes viral on Twitter, and half the population says “I’m a math professor and the answer is 6” and the other half says “I have 4 math degrees and the answer is 1.”

We are now equipped to solve the problem with Postfix Notation, which takes all that ambiguity out and always produces the correct answer, using a Stack.

Before we look at Postfix, let’s look at Infix. We all know Infix, it’s just very uncommon to see it called that—it’s the expression above. When we have “the sum of a and b”, then that’s written as “a + b” with “a” and “b” surrounding the “+” operator, and so on. As written, “the sum of a and b” looks like Prefix, since “the sum of” comes before the arguments “a” and “b”. Naturally, then, Postfix is where we would see something (in plain English) as “a and b added together,” where a and b come first, and only after you have enough operands do you give the operation.

In Postfix, push onto a stack, until you have enough operators and operands that an operation is legal, pop them off, do the computation, and push the result back.

Let’s take as an example 2 + (3 + 4 + 5 * (6 - 7)), which has some of the same parenthetical ambiguities as the problems that go viral. This is equivalent (just adding some parentheses) to 2 + ((3 + 4) + (5 * (6 - 7))).

In Postfix, that looks like 2 3 4 + 5 6 7 - * + +.

Let’s now use a stack, tracking every operation:

Token	Operation	Stack State
2	Push 2	[2]
3	Push 3	[2, 3]
4	Push 4	[2, 3, 4]
+	Pop 4 and 3 (the top 2 numbers, since + takes 2 arguments), push 3+4=7	[2, 7]
5	Push 5	[2, 7, 5]
6	Push 6	[2, 7, 5, 6]
7	Push 7	[2, 7, 5, 6, 7]
-	Pop 7 and 6 (the top 2 numbers, since - takes 2 arguments), push 6-7=-1	[2, 7, 5, -1]
*	Pop -1 and 5 (the top 2 numbers since * takes 2 arguments), push 5×(-1)=-5	[2, 7, -5]
+	Pop -5 and 7, push 7+(-5)=2	[2, 2]
+	Pop 2 and 2, push 2+2=4	[4]

We’ve gotten to the end of the string, and we have nothing else to process, so the final answer on the stack is the correct answer.

Let’s go back to the fully-parenthesized infix and solve it, just to be sure.

2 + ((3 + 4) + (5 * (6 - 7)))  

1. The innermost parentheses are 6-7 = -1
2. Multiply that by 5 = -5
3. At the same level, we now have 2 additions: 3+4, and {that result}, plus our -5
4. 3 + 4 is 7
5. 7 - 5 is 2
6. Now we’ve cleared all the parentheses, and the result of all that was 2
7. The last step is to add 2 to the result of the parentheses, which is 4
8. Now we’ve cleared the whole expression, so the final answer is 4

 Come up with some relatively simple expressions in traditional infix, and do 3 things:

1. Convert to postfix
2. Use a stack to solve the postfix expression, stepping through with a table as shown above
3. Solve the expression in infix to validate the answer and show to yourself that the methods are equivalent

Java is hard. Trust me-- I know.

 Before we continue with more Java, I just wanted to take a quick break today to acknowledge how difficult programming (in Java or any language) can be and how frustrating it can be, especially at the beginning. (But, spoiler alert, the frustration doesn’t go away as you get more experienced; early problems get much easier, but harder problems can still be just as frustrating!)

You’ll write a lot of code on your way to Java proficiency—many thousands of lines. If you’re following along, learning from me, then you’re just getting started. People who do this for a full career from early adulthood to retirement will end up writing hundreds of thousands of lines over all those years.

And in all those years writing all those lines, there will be lots of bugs. If your lifetime output is 500,000 lines, you probably wrote at least 1,000,000 bugs along the way.  Brady, Manning, Montana, Brees, etc., are some of the greatest quarterbacks ever, and none of them has a career completion percentage over 70; each of them, as great as they were, made thousands of mistakes over their careers. Even the best make mistakes! That's OK! You will, but you'll improve over time! 

The more practice you get with the simple parts, the easier it is for those to be bug-free. There will be a point, as a programmer, where certain structures become so obvious that they become second nature. If you aren’t at that point yet, don’t worry! Bugs are a critical part of the learning process. (It took me an embarrassingly long time, for example, in 2017-18, to consistently remember to end my lines with a ;, and that’s a serious enough bug that your code will not run if even one of them is missing.)

Bugs come in two general flavors:

• Errors in syntax
• Errors in logic

Syntax errors, generally, are easier to grow out of: “oops, I called an int a ‘num’ because I forgot the name of the data type” or “oops, I left off a semicolon, or didn’t pair () inside () inside () correctly so there was one too many (”. These come down to learning the conventions of the language and being careful, just like a college professor makes fewer spelling mistakes than her 5-year-old kindergartener. The professor has been reading and writing far longer, so she has seen much more correct spelling and had many more opportunities to practice it.

Logic errors, on the other hand, are the real nasty bugs—the reason people in coding make so much: because it’s our job to work through an algorithm to do something, put it on paper, explain it to a coworker (this is great at catching these bugs), and then translate plain English into computable Java. If a problem is just particularly hard, or if your boss’s requirements aren’t clear, or if you’re working with something new, or if you’ve had a bad day, you’re much more likely to make logic errors, even after 10, 20, 30 years of coding. That is to say: professionals write bugs all the time, so if you’re just getting started, don’t beat yourself up!

But at the same time, don’t look for the easy way out. If you’re learning Hanoi, don’t Google the solution, or read too far down my article without playing with plates first. If you have an infinite loop or StackOverflowException somewhere, don’t throw your hands up and give the problem to an LLM to fix for you. It’s totally normal, especially early, to feel the pressure to get things right, right away—but this does not (or should not) exist. You will, and you can, make mistakes. You are learning!

If you're learning a new algorithm and you come across a bug, then the best things to do are any of the following:

• Take a break
• Ask questions 
• Find a good explainer video/article
• Ask someone else for help
• Try to teach someone the algorithm and answer their questions
• Make your learning experience multi-sensory somehow

But DON'T:

• Go to an LLM right away for a quick and easy answer
• Copy a solution from somewhere like StackOverflow or ChatGPT
• Give up
• Ask someone else to write it for you

Generic Types

Generics allow you to write code that works with any data type, making your classes and methods more reusable and type-safe. Instead of writing the same code for every type (imagine how much repetition you would need, if you had to cover every type you can come up with!), you can write it once and use it for many types.

Here’s a simple generic class that can store any type of data:

// A generic class that can store any type of data

class Box<T> {

    private T value;

    public Box(T value) {

        this.value = value;

    }

    public T getValue() {

        return value;

    }

}

public class Main {

    public static void main(String[] args) {

        Box<Integer> intBox = new Box<>(123);

        Box<String> strBox = new Box<>("Hello Generics!");

        System.out.println(intBox.getValue()); // Output: 123

        System.out.println(strBox.getValue()); // Output: Hello Generics!

    }

}

Here, T is a placeholder for the type you want to use. When you create a Box<Integer>, T becomes Integer; for Box<String>, it becomes String. 

You can also make methods generic:

public class Main {

    // Generic method

    public static <T> void printItem(T item) {

        System.out.println("Item: " + item);

    }

    public static void main(String[] args) {

        printItem(42);           // Output: Item: 42

        printItem("Java");       // Output: Item: Java

    }

}

This method works with any type you pass to it because you're passing a T, a generic. A "T" can be a CollegeStudent, a FluffyUnicorn, a PepperoniPizza, whatever you want.

Java has primitive data types like int, double, and char. However, sometimes you need to use objects instead of primitives—for example, when working with collections like ArrayList. That’s where wrapper classes come in.
What Are Wrapper Classes?

Wrapper classes “wrap” primitive values in an object. The name of the wrapper class is, capitalized, the written-out name of the data type (as in, "Integer" or "Double", etc.)


You use wrapper classes whenever you need an object instead of a primitive.

You can’t use primitives in collections like ArrayList, as we've already seen. You must use their wrapper classes:

import java.util.ArrayList;

public class Main {

    public static void main(String[] args) {

        // ArrayList<int> numbers = new ArrayList<int>(); // Invalid!

        ArrayList<Integer> numbers = new ArrayList<>();   // Valid!

        numbers.add(10);

        numbers.add(20);

        System.out.println(numbers); // Output: [10, 20]

    }

}

Here, Integer is used instead of int.


Autoboxing is when Java automatically converts a primitive to its wrapper class when needed. Unboxing is the opposite process by which Java automatically converts a wrapper object back to a primitive.

Integer myInt = 5;      // Autoboxing: int to Integer

int num = myInt;        // Unboxing: Integer to int

System.out.println(myInt); // Output: 5

System.out.println(num);   // Output: 5

This makes it easy to switch between primitives and objects.


Generics make your code flexible and type-safe, letting you write reusable classes and methods.


Wrapper classes let you use primitive values as objects, especially useful in collections and when object methods are needed.


Java handles most conversions between primitives and wrapper classes automatically (autoboxing/unboxing).

These concepts are foundational for modern Java programming—mastering them will make your code safer, cleaner, and more powerful

Short-circuit evaluation of booleans

 By now, you may have noticed this already, but it’s so important that it merits an article of its own: there are some instances in which you don’t care—so you don’t even compute—what certain expressions’ values are.

Suppose you have something like:

if(isMonday  || isWednesday || isFriday){
// stuff
}

Then, knowing that || means logical-or (so this means, in English, “if today is Monday, Wednesday, or Friday…”), one might look at the truth table for OR. The truth table contains all the possible inputs and their corresponding outputs:

For “OR”, that looks like:

Var1	Var2	Result
TRUE	TRUE	TRUE
TRUE	FALSE	TRUE
FALSE	TRUE	TRUE
FALSE	FALSE	FALSE

That is, 2-way logical OR is false only if BOTH are false (3-, 4-way, etc., would only be false if ALL are false). Put another way, if ANY are true, then OR is true.

AND, likewise, has a table.

Var1	Var2	Result
TRUE	TRUE	TRUE
TRUE	FALSE	FALSE
FALSE	TRUE	FALSE
FALSE	FALSE	FALSE

For a logical AND to return true, both things being AND-ed must be true (likewise for multi-way AND, ALL must be true for it to be true; any falses cause an overall false). If BOTH are true, then AND is true; if ANY are false, then AND is false.

Back to our day-of-the-week example, once we see that any day matches with today, we don’t have to look at any of the other checks, since the expression is entirely OR-based. Just the fact that one of those is true, provided that they’re all connected by OR, is enough to make the whole expression true, and we can jump into whatever code is prescribed for that case.

Similarly, in a situation where

if(is16OrOlder && hasLicense && noRestrictions && carIsWorking){
// do stuff

}

If any of these are found to be false, we don’t need to check the others. AND works in such a way that, unless all chained ANDs are true, the whole thing is false.

This is a simple and incredibly common logical optimization in Java performed at the compiler level, known as short-circuit evaluation. If you have a sophisticated IDE, it will also probably tell you if it finds any variables that can be short-circuited. IntelliJ, at least in light mode, highlights such expressions in a sepia-like color (which it also uses for infinite loops, or loops that don’t loop).

 

Break and Continue

 Sometimes, it might be necessary to either stop a loop prematurely—without returning from a method—or skip over an iteration of a loop.

It is for this reason that Java has two special keywords: break (for the former case), and continue (for the latter).

Suppose we want to exit a loop early. The break keyword would be used to do that, like so:

public class BreakExample {

    public static void main(String[] args) {

        for (int i = 1; i <= 10; i++) {

            if (i == 5) {

                break; // Exit the loop when i is 5

            }

            System.out.println("i = " + i);

        }

        System.out.println("Loop ended.");

    }

}

(Never mind that, in this instance, the loop was written very badly—why loop from 1 to 10, if you’re going to break out of the loop and stop it completely, at 5? Poor design as this may be, it serves our purpose of illustrating how break is used.)

This works for any loop—even those for which the index is not exposed (the for-each/enhanced-for loop):

public class BreakForEachExample {

    public static void main(String[] args) {

        String[] laptops = {"Windows", "Samsung", "Apple", "Dell", "Asus"};

 

        for (String laptop : laptops) {

            if (laptop.equals("Apple")) {

                System.out.println("Yes, we want an Apple company laptop");

                break; // Exit the loop when "Apple" is found

            }

        }

    }

}

The “continue” keyword, meanwhile, keeps the loop running, but skips over one particular iteration.

Here, we see continue used in a while loop—just to drive home the point that both these keywords can be used (meaning the same thing), regardless of what particular loop they’re in: continue skips one, break comes out.

public class ContinueWhileExample {

    public static void main(String[] args) {

        int i = 0;

        while (i < 5) {

            i++;

            if (i == 3) {

                continue; // Skip the rest of the loop when i is 3

            }

            System.out.println("i = " + i);

        }

    }

}

Now, that’s all well and good if all we have is one loop to deal with—if that’s true, then the behavior of these breakpoints is straightforward—but what happens if we have nested loops, that is, loops inside loops, inside loops, inside loops…?

This, for example, is a nested loop:

public class NestedLoopExample {

    public static void main(String[] args) {

        for (int i = 1; i <= 3; i++) { // Outer loop for rows

            for (int j = 1; j <= 5; j++) { // Inner loop for columns

                System.out.print("* ");

            }

            System.out.println(); // Move to the next line after each row

        }

    }

}

For each of the 3 rows, the program prints 5 * characters—producing something like

*****
*****
*****

If someone were to break or continue in a situation like this, where there are nested loops—which can be of mixed types (for inside while, while inside do-while, indexed-for inside for-each, while inside for-each, etc.)—break and continue only apply to the innermost loop in which they could:

For example, the following code:

public class NestedLoopBreakExample {

    public static void main(String[] args) {

        for (int i = 1; i <= 3; i++) { // Outer loop

            for (int j = 1; j <= 5; j++) { // Inner loop

                if (j == 3) {

                    break; // Exit the inner loop when j is 3

                }

                System.out.println("i = " + i + ", j = " + j);

            }

        }

    }

}

has this output:

i = 1, j = 1

i = 1, j = 2

i = 2, j = 1

i = 2, j = 2

i = 3, j = 1

i = 3, j = 2

But if we use “continue” in the outer loop, then something like this might happen:

public class OuterContinueExample {

    public static void main(String[] args) {

        for (int i = 1; i <= 3; i++) { // Outer loop

            if (i == 2) {

                continue; // Skip the rest of this outer loop iteration when i is 2

            }

            for (int j = 1; j <= 3; j++) { // Inner loop

                System.out.println("i = " + i + ", j = " + j);

            }

        }

    }

}

i = 1, j = 1

i = 1, j = 2

i = 1, j = 3

i = 3, j = 1

i = 3, j = 2

i = 3, j = 3

Both break and continue are vitally important logical flow controllers—so be sure you understand how each works (and is different from the other!). Don’t just stick to these code examples; write your own, or modify these, and see how the behavior changes as you make changes to your code.

Stacks

 Imagine you’ve just unloaded the dishwasher, and you’ve created a stack of plates. What can you do? You can see what the top plate is, you can add plates to the top, you can count how many plates there are, and you can remove the top plate to get access to plates underneath it.

Java has a data structure that behaves exactly like the stack of plates—the Stack. A stack has several operations like we’ve already seen with other data structures: you can add and you can remove, but, just like we saw with queues, how you do that (where you have access) has special meaning.

As I alluded to last time, looking at queues, some data structures preserve special ordering: the FIFO queue of people at the checkout counter, or the LIFO stack of plates in the cupboard. You can’t see the bottom plate, nor can you add, remove, or check out some random plate in the middle—everything you do must be done to the top visible plate. It's for this reason that a stack is LIFO-- the last thing to be added is the first to come off.

A queue, recall, lets you access only the oldest thing. A stack, by contrast, allows you to access only the newest thing. Think about it - again, with the stack of plates. (Go get a literal stack of plates or maybe books, and put numbers on sticky notes on each plate or book; I promise it’ll help.) When you add to a stack, you can only do so to the top. When you take away from a stack, you can only do so from the top. When you look at a value in a stack, you can only see the top element’s value, not the values of anything under it. 

Stacks call the “add” operation “push,” and the “remove” operation “pop.”  There are certainly problems in which asking if there is anything left in the stack (Think about why? perhaps… because a loop has been running?), so you can do so by calling isEmpty(), which, naturally, returns a Boolean: true if it’s empty, and false otherwise. (This can make working with this call quite annoying, since the resulting Boolean answers “is there nothing?” when the more natural question is probably “is there anything here?”, which is exactly the opposite)

import java.util.Stack;

 

public class StackExample {

    public static void main(String[] args) {

        // Create a stack

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

 

        // Push elements onto the stack

        stack.push(1);

        stack.push(2);

        stack.push(3);

 

        System.out.println("Stack: " + stack);

 

        // Peek at the top element (without removing)

        System.out.println("Top element (peek): " + stack.peek());

 

        // Pop the top element (remove and return)

        int poppedItem = stack.pop();

        System.out.println("Popped element: " + poppedItem);

 

        System.out.println("Stack after pop: " + stack);

    }

}

By now, I’m sure you’ve been working with imports for a while, so seeing that you have to pick it up from java.util should be nothing new. Get in the habit, at least in the beginning of typing out that import yourself, if only so you commit to memory that Stack lives in util. Once you’ve really got stacks down, you can save a second or two by not typing it yourself, writing the rest of your code, and letting the IDE realize for you that you need to put in the import (which the IDE will either do automatically, or which you’ll approve by the click of a button).

Stacks, again, use generics, including the wrapper classes for the primitive types. They’ll be covered in the next post! Stay tuned!

Queues: Just like at the grocery store

 A Queue is another data structure that operates with many similar functions as Lists do, but with a key difference. In a List (as in an array—either with arr[37] or list.get(41) or whatever you want), it’s easy to get to any particular element and do something with it: check its value, change its value, remove it, add it, and so on.

But a queue is different. A queue is, really, just an implementation of “I’m in line at the grocery store to check out, and there’s an order of the people who got here.” Social norms dictate that the cashier only helps the first person in line—the person who has been in line longer than anyone else. They got there because the person ahead of them cleared the queue, and the person before that cleared before them, and the person before that, and so on.

The line only shrinks from the cashier end of the line, and only grows from the back end of the line. The longer you’ve been in line, the sooner you’ll get the cashier’s attention. If you just arrived, you have to wait for everyone ahead of you. Jumping ahead (technically possible with real people) is not allowed with a Queue.

Queues implement the “first-in-first-out” principle, which we call “FIFO” for short. (There is also a “LIFO”—you may have guessed “last-in-first-out”—structure called a Stack. We’ll cover it very soon.)

To add to a queue, you use add(). Queues are like Lists—they take generics, so you make a Queue<Puppy> to store a queue of (only) Puppy objects, or Queue<Student> to store a queue of Student objects. To remove from a queue, you use remove(). Under certain circumstances, you may remove with poll().

You may not want to outright add or remove an element, just look at something—remember, only the front element is visible—and, to do this (again, only for the front element), you can use poll().

Look at this example:

import java.util.Queue;

import java.util.LinkedList;

 

public class QueueExample {

    public static void main(String[] args) {

        // Create a queue using LinkedList

        Queue<Integer> queue = new LinkedList<>();

 

        // Enqueue (add) elements to the queue

        queue.offer(1);  // offer() is preferred for adding elements

        queue.offer(2);

        queue.offer(3);

 

        System.out.println("Queue: " + queue);

 

        // Dequeue (remove) the front element

        int removedItem = queue.poll();

        System.out.println("Removed element: " + removedItem);

 

        System.out.println("Queue after dequeue: " + queue);

    }

}

Adding an element is called “enqueueing,” and removing is also called “dequeueing.” Notice the declaration Queue<Integer> queue = new LinkedList<>();. What does that tell us? Recall from our discussion of inheritance that this is valid, if and only if (and this is true), a Queue is implemented as a LinkedList, since every Queue is a LinkedList, but not every LinkedList is a Queue.

On account of this, the element indexed 0—the “first” element—is the element at the head of the queue, or, the next one to be processed (the person being checked out by the cashier in our earlier story). The highest index in the queue, therefore, lies at the opposite end, at the tail of the queue.

This queue we have shown here is the simplest kind of queue. Later, we’ll get to a more specialized queue called a priority queue. Priority queues aren’t that much different, so don’t be too scared; in essence, they keep elements in the proper order, by some priority (“keep the seniors above the juniors above the sophomores above the freshmen”; or “keep the oldest people at the back of the queue.”)

The general queue imposes no such restriction, and you’re free to enqueue and dequeue as much as you want—add 3 things, remove 1, add 57, remove 48, add 1, take away 2, and so on—without messing with order.

Play around with building your own queue of an object of your choice (or the wrapper classes of primitives like Integer for integers), and have fun enqueueing and dequeing.