A Data Structures class final project that reads infix expressions, converts them to postfix, evaluates them, builds expression trees, and demonstrates hash table collision strategies.
When you enter an expression like 3 + 4 * 2 / (1 - 5) ^ 2, it goes through 5 steps:
Splits the expression string into individual tokens (numbers, operators, parentheses).
Example:
Input: 3 + 4 * 2 / ( 1 - 5 ) ^ 2
Output: [3, +, 4, *, 2, /, (, 1, -, 5, ), ^, 2]
How it works:
- Scans the string character by character
- Multi-digit numbers and decimals are buffered (e.g.,
100is kept together) - Negative signs are detected when a
-appears before a number - Each token is added to a
Queue<String>usingadd()
Converts the infix expression (human-readable) to postfix notation (computer-friendly) using the Shunting Yard algorithm.
Example:
Infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2
Postfix: 3 4 2 * 1 5 - 2 ^ / +
How it works:
- Numbers go directly to the output queue
- Operators are pushed onto a stack
- Operators with lower or equal precedence are popped from the stack to the output before pushing the current operator
- Parentheses:
(is pushed to stack, when)is found everything until(is popped to output
Operator Precedence:
| Operator | Precedence |
|---|---|
^ |
3 (highest) |
* / % |
2 |
+ - |
1 (lowest) |
Evaluates the postfix expression to get the numerical result.
Example:
Postfix: 3 4 2 * 1 5 - 2 ^ / +
Result: 3.5
How it works:
- Numbers are pushed onto the stack
- When an operator is found, the top two numbers are popped, the operation is applied, and the result is pushed back
- Division by zero throws an
ArithmeticException
Builds a binary expression tree from the postfix notation, then shows three traversal orders.
Tree structure for 3 + 4 * 2 / (1 - 5) ^ 2:
+
/ \
3 /
/ \
* ^
/ \ / \
4 2 - 2
/ \
1 5
Traversals:
- Preorder (Root → Left → Right):
+ 3 / * 4 2 ^ - 1 5 2 - Inorder (Left → Root → Right):
3 + 4 * 2 / 1 - 5 ^ 2(the original expression without parentheses) - Postorder (Left → Right → Root):
3 4 2 * 1 5 - 2 ^ / +(same as postfix)
How the tree is built:
- Numbers create leaf nodes and are pushed onto a stack
- Operators create parent nodes, popping two children from the stack (right child first, then left)
Demonstrates four ways to handle hash table collisions. The hash function is Math.abs(round(value) % 10).
Example with result = 25:
| Strategy | Hash | Index | How it works |
|---|---|---|---|
| Linear Probing | 25 % 10 = 5 | 5 | Try index 5, if occupied try 6, 7, 8... |
| Quadratic Probing | 25 % 10 = 5 | 5 | Try index 5, then 5+1, 5+4, 5+9... (i²) |
| Double Hashing | 25 % 10 = 5 | 5 | Primary hash + secondary hash (7 - value%7) |
| Separate Chaining | 25 % 10 = 5 | 5 | Each bucket holds a linked list of values |
- Type:
Queue<T>using linked list (QNode<T>) - Methods:
add(T x)— enqueue: adds to the rearT poll()— dequeue: removes and returns from the frontboolean isEmpty()— checks if queue is emptyQueue(Queue<T> other)— copy constructor to clone a queue
- How it works: Maintains
frontandrearpointers. Adding creates a new node at the rear. Polling removes the front node and movesfrontforward.
- Type:
Stack<T>using fixed-size array (Object[]) - Methods:
push(T x)— adds element to the topT pop()— removes and returns the top elementT peek()— returns the top element without removing itboolean isEmpty()— checks if stack is emptyboolean isFull()— checks if stack is at capacity
- How it works: Uses an array with a
topindex. Pushing incrementstop, popping decrements it. ThrowsRuntimeExceptionif popping from an empty stack.
- Type:
LinkedList<T>using nodes (LLNode<T>) - Methods:
add(T x)— adds a node to the end of the listint count()— returns the number of nodesvoid print()— prints all node values
- How it works: Maintains a
headpointer. Adding traverses to the last node and links a new node to it. Used in the hash table's separate chaining strategy.
- Fields:
String value,Node left,Node right - Purpose: Represents nodes in the expression tree where leaf nodes hold numbers and internal nodes hold operators
| File | Purpose |
|---|---|
Main.java |
Entry point with menu system (live input, file input, exit) |
ExpressionProcessor.java |
All processing logic + inner HashTable class |
Stack.java |
Custom generic stack (array-based) |
Queue.java |
Custom generic queue (linked list-based) |
LinkedList.java |
Custom generic linked list |
Node.java |
Expression tree node |
compile.sh |
Compiles all Java files |
run.sh |
Runs the program |
clean.sh |
Deletes compiled .class files |
input.txt |
Input file for batch processing (bonus) |
output.txt |
Generated output file (bonus) |
Stacks are LIFO (Last In, First Out). This is perfect because operators that appear later may need to be processed first (higher precedence). The stack temporarily holds operators until their operands are ready.
Queues are FIFO (First In, First Out). Tokens are read in order from the expression and must be processed in the same order during conversion and evaluation.
Developed by Edsger Dijkstra. It uses a stack to handle operator precedence and parentheses. The key insight: push operators to stack, pop them to output when a lower-precedence operator arrives or when a closing parenthesis is found.
Every binary expression can be represented as a tree where:
- Leaf nodes = operands (numbers)
- Internal nodes = operators
- The tree naturally encodes the order of operations
- Inorder traversal gives the infix expression
- Postorder traversal gives the postfix expression
When two values hash to the same index, we need a strategy:
- Linear Probing: Check next slot sequentially — simple but causes clustering
- Quadratic Probing: Check slots at i² intervals — reduces clustering
- Double Hashing: Use a second hash function for the step size — best distribution
- Separate Chaining: Each bucket holds a linked list — simple, handles any number of collisions