Practical activity

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class ListStack {
    private List<Object> stack;

    //The constructeur replace the initialise primitive
    public ListStack() {
        this.stack = new ArrayList<>();
    }

    public boolean isEmpty() {
        /**
         * This function checks if the stack is empty.
         * @return True if the stack is empty, False otherwise.
         */
        return this.stack.isEmpty();
    }

    public void push(Object item) {
        /**
         * This function adds an element to the stack.
         * The element is added at the end.
         * @param item Element to add.
         */
        this.stack.add(item);
    }

    public Object pop() {
        /**
         * This function removes the last element of the stack.
         * @return The last element of the stack.
         */
        if (this.stack.isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return this.stack.remove(this.stack.size() - 1);
    }
}

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */

// Needed imports
import java.util.Stack;

public class Main {

    /**
     * This function uses a stack to evaluate a postfix expression.
     * The function takes a string as input, which is a postfix expression.
     * The function returns the result of the expression.
     *
     * @param expression Expression to be evaluated.
     * @return Evaluated result of the postfix expression.
     */
    public static double evaluatePostfix(String expression) {
        // Create an empty stack
        Stack<Double> stack = new Stack<>();

        // Iterate over the expression
        String[] splitExpression = expression.split(" ");
        for (String i : splitExpression) {

            // If the character is a number, push it to the stack
            if (i.matches("-?\\d+(\\.\\d+)?")) {
                stack.push(Double.parseDouble(i));
            }

            // If the character is an operator, apply it
            else {

                // Pop the last two elements from the stack
                double a = stack.pop();
                double b = stack.pop();

                // Apply the operator
                switch (i) {
                    case "+":
                        stack.push(b + a);
                        break;
                    case "-":
                        stack.push(b - a);
                        break;
                    case "*":
                        stack.push(b * a);
                        break;
                    case "/":
                        stack.push(b / a);
                        break;
                    default:
                        throw new IllegalArgumentException("Invalid operator: " + i);
                }
            }
        }

        // Return the result
        return stack.pop();
    }
}

import java.util.ArrayList;
import java.util.List;

public class ListQueue {
    private List<Object> queue;

    public ListQueue() {
        this.queue = new ArrayList<>();
    }

    public boolean isEmpty() {
        /**
         * This function checks if the queue is empty.
         * @return True if the queue is empty, False otherwise.
         */
        return this.queue.isEmpty();
    }

    public void push(Object item) {
        /**
         * This function adds an element to the queue.
         * The element is added at the end.
         * @param item Element to add.
         */
        this.queue.add(item);
    }

    public Object pop() {
        /**
         * This function removes the last element of the queue.
         * @return The removed element.
         */
        if (this.queue.isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return this.queue.remove(0);
    }
}

/**
 * This class provides methods to manipulate a doubly-linked list.
 * The list is represented with a head and tail pointing to the first and last nodes, respectively.
 * Each node is represented with data, prev, and next fields.
 */

import java.util.Optional;

 class DoublyLinkedList {
     // Define the Node structure
     static class Node {
         int data;
         Node prev;
         Node next;
 
         Node(int data) {
             this.data = data;
             this.prev = null;
             this.next = null;
         }
     }
 
     private Node head;
     private Node tail;
 
     // Initialize the list
     public DoublyLinkedList() {
         this.head = null;
         this.tail = null;
     }

    
    /**
     * Check if the list is empty.
     *
     * @return true if the list is empty, false otherwise.
     */
    public boolean isEmpty() {
        return head == null;
    }
    
     /**
      * Insert a new node with the given data at the beginning of the list.
      *
      * @param data The data to store in the new node.
      */
     public void insertAtBeginning(int data) {
         Node newNode = new Node(data);
         if (head == null) {
             head = tail = newNode;
         } else {
             newNode.next = head;
             head.prev = newNode;
             head = newNode;
         }
     }
 
     /**
      * Insert a new node with the given data at the end of the list.
      *
      * @param data The data to store in the new node.
      */
     public void insertAtEnd(int data) {
         Node newNode = new Node(data);
         if (tail == null) {
             head = tail = newNode;
         } else {
             newNode.prev = tail;
             tail.next = newNode;
             tail = newNode;
         }
     }
 
     /**
      * Delete the first node with the given data from the list.
      *
      * @param data The data of the node to delete.
      */
     public void deleteNode(int data) {
         Node current = head;
         while (current != null) {
             if (current.data == data) {
                 if (current.prev != null) {
                     current.prev.next = current.next;
                 } else {
                     head = current.next;
                 }
                 if (current.next != null) {
                     current.next.prev = current.prev;
                 } else {
                     tail = current.prev;
                 }
                 return;
             }
             current = current.next;
         }
     }

      /**
     * Remove and return the data from the node at the head of the list.
     *
     * @return The data from the node at the head of the list, or -1 if the list is empty.
     */
    public int popFromHead() {
        if (head == null) {
            throw new RuntimeException("Empty list");//notion of Exception seen in prog session 
        }
        int data = head.data;
        head = head.next;
        if (head != null) {
            head.prev = null;
        } else {
            tail = null;
        }
        return data;
    }

    /**
     * Remove and return the data from the node at the tail of the list.
     *
     * @return The data from the node at the tail of the list, or -1 if the list is empty.
     */
    public int popFromTail() {
        if (tail == null) {
            throw new RuntimeException("Empty list");
        }
        int data = tail.data;
        tail = tail.prev;
        if (tail != null) {
            tail.next = null;
        } else {
            head = null;
        }
        return data;
    }
 
     /**
      * Search for a node with the given data.
      *
      * @param data The data to search for.
      * @return An Optional containing the found node, or an empty Optional if no node was found.
      */
     public Optional<Node> searchNode(int data) {
         Node current = head;
         while (current != null) {
             if (current.data == data) {
                 return Optional.of(current);
             }
             current = current.next;
         }
         return Optional.empty();
     }
 
     /**
      * Display the data of all nodes in the list.
      */
     public void displayList() {
         Node current = head;
         while (current != null) {
             System.out.print(current.data + " ");
             current = current.next;
         }
         System.out.println();
     }
 }

/**
      * Delete the first node with the given data from the list.
      *
      * @param data The data of the node to delete.
      */
     public void deleteNode(int data) {
         Node current = head;
         while (current != null) {
             if (current.data == data) {
                 if (current.prev != null) {
                     current.prev.next = current.next;
                 } else {
                     head = current.next;
                 }
                 if (current.next != null) {
                     current.next.prev = current.prev;
                 } else {
                     tail = current.prev;
                 }
                 return;
             }
             current = current.next;
         }
     }

 /**
     * Apply the selection sort algorithm on the list
     */
    public void selectionSort() {
        if (head != null) {
    
            Node current = head;
            while (current != null) {
                Node minNode = current;
                Node nextNode = current.next;
        
                while (nextNode != null) {
                    if (nextNode.data < minNode.data) {
                        minNode = nextNode;
                    }
                    nextNode = nextNode.next;
                }
        
                // Swap the data of the current node and the minNode
                if (minNode != current) {
                    int temp = current.data;
                    current.data = minNode.data;
                    minNode.data = temp;
                }
        
                current = current.next;
            }
        }
    }

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */

// Needed imports
import java.util.Stack;
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

    /**
     * This function uses a stack and a queue to transform an infix expression to a postfix expression.
     * All expressions are supposed to be well parenthesized.
     *
     * @param infixExpression Expression to be transformed to postfix.
     * @return Postfix expression equivalent to the input infix expression.
     */
    public static String infixToPostfix(String infixExpression) {
        // Define the precedence of the operators
        var precedence = new java.util.HashMap<String, Integer>();
        precedence.put("*", 2);
        precedence.put("/", 2);
        precedence.put("+", 1);
        precedence.put("-", 1);
        precedence.put("(", 0);
        precedence.put(")", 0);

        // Initialize the stack and the queue
        Stack<String> stack = new Stack<>();
        List<String> queue = new ArrayList<>();

        // Split the infix expression into tokens
        Pattern pattern = Pattern.compile("(\\+|\\-|\\*|\\/|\\(|\\))");
        Matcher matcher = pattern.matcher(infixExpression);
        List<String> tokens = new ArrayList<>();
        int lastIndex = 0;
        while (matcher.find()) {
            if (matcher.start() > lastIndex) {
                tokens.add(infixExpression.substring(lastIndex, matcher.start()).trim());
            }
            tokens.add(matcher.group());
            lastIndex = matcher.end();
        }
        if (lastIndex < infixExpression.length()) {
            tokens.add(infixExpression.substring(lastIndex).trim());
        }

        // Iterate over tokens
        for (String token : tokens) {
            // If the token is an operand, add it to the queue
            if (token.matches("\\d+")) {
                queue.add(token);
            }

            // If the token is a left parenthesis, add it to the stack
            else if (token.equals("(")) {
                stack.push(token);
            }

            // If the token is a right parenthesis, pop all the operators from the stack and add them to the queue until a left parenthesis is found
            else if (token.equals(")")) {
                while (!stack.isEmpty() && !stack.peek().equals("(")) {
                    queue.add(stack.pop());
                }
                stack.pop();
            }

            // If the token is an operator, pop all the operators from the stack with higher precedence and add them to the queue
            // Then, add the operator to the stack
            else {
                while (!stack.isEmpty() && precedence.get(stack.peek()) >= precedence.get(token)) {
                    queue.add(stack.pop());
                }
                stack.push(token);
            }
        }

        // Add the remaining operators to the queue
        while (!stack.isEmpty()) {
            queue.add(stack.pop());
        }

        // Return the postfix expression
        return String.join(" ", queue);
    }


    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Test the function
        System.out.println("3*(((12-3)/3)-1) transformed into " + infixToPostfix("3*(((12-3)/3)-1)"));
        System.out.println("1+(2*3) transformed into " + infixToPostfix("1+(2*3)"));
        System.out.println("(1+2)*3 transformed into " + infixToPostfix("(1+2)*3"));
        System.out.println("3*(2+1) transformed into " + infixToPostfix("3*(2+1)"));
    }

}

 import java.util.*;

public class ConvexHull {
    /**
     * This function calculates the Euclidean distance between two points.
     * @param p1 point 1 defined by its two coordinates - array of 2 integers
     * @param  p2 point 2 defined by its two coordinates - array of 2 integers
     * @return the Euclidean distance.
     */

    public static double euclideanDistance(int[] p1, int[] p2) {
        return Math.pow(p2[0] - p1[0], 2) + Math.pow(p2[1] - p1[1], 2);
    }

    /**
     * This function calculates the direction of the vector product of the two vectors defined by the points p, q and p, r
     * @param p point 1 defined by its two coordinates - array of 2 integers
     * @param q point 2 defined by its two coordinates - array of 2 integers
     * @param r point 3 defined by its two coordinates - array of 2 integers
     * @return  true if the vector product is negative, false otherwise
     */

    public static boolean rightTurn(int[] p, int[] q, int[] r) {
        int direction = (q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0]);
        return direction < 0;
    }

    /**
     * This function implements the Graham algorithm to compute the convex hull of point in a 2D plane.  
     * @param points list of points in the plane, each represented by its coordinates (abscissa, ordinate) - a tuple with two integer elements.
     * @return list of integer arrays representing the points forming the convex envelope.
     */

    public static List<int[]> grahamScan(List<int[]> points) {
        // Find the point with the lowest y-coordinate, if there are multiple points with the same y-coordinate, pick the one with the smallest x-coordinate
        int[] minY = Collections.min(points, Comparator.comparingInt((int[] p) -> p[1]).thenComparingInt(p -> p[0]));

        // Sort the set of points in increasing order of the angle they and the pivot point make with the x-axis.
        points.sort((p1, p2) -> {
            double angle1 = Math.atan2(p1[1] - minY[1], p1[0] - minY[0]);
            double angle2 = Math.atan2(p2[1] - minY[1], p2[0] - minY[0]);
            if (angle1 != angle2) {
                return Double.compare(angle1, angle2);
            } else {
                return Double.compare(euclideanDistance(minY, p1), euclideanDistance(minY, p2));
            }
        });

        // Create the convexe hull
        Stack<int[]> hull = new Stack<>();
        for (int[] point : points) {
            while (hull.size() > 1 && rightTurn(hull.get(hull.size() - 2), hull.peek(), point)) {
                hull.pop(); // remove the point from the stack
            }
            hull.push(point); // add the point to the stack and move to the next one
        }

        return new ArrayList<>(hull);
    }
    public static void main(String[] args) {
        // Example 
        List<int[]> points = Arrays.asList(
            new int[]{0, 0}, new int[]{1, 1}, new int[]{1, 2}, new int[]{2, 2},
            new int[]{3, 0}, new int[]{3, 2}, new int[]{0, 3}, new int[]{3, 3},
            new int[]{2, 4}
        );

        List<int[]> hull = grahamScan(points);
        System.out.println("Convex hull:");
        for (int[] point : hull) {
            System.out.println(Arrays.toString(point));
        }
    }
}