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);
    }
}

/**
 * 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));
        }
    }
}