The Nook Games™

For the first part of this practical, you will be given a queue struct. It is here to help you, don't hesitate to use it.

`Fundamentals/basic_tree.c`

In this part of the Practical, we will give you a header file, basic_tree.h, containing the struct you will use along with some functions to help you in this journey in basic_tree_aux.c.

The goal of this function is to insert a node into the binary tree. When you insert, you want to complete, if possible, the current row. You will add the node at the first left-most free place you find on the last row.
If there is no root, the node becomes the root. And if the last row is already complete, it is up to you to create a new one.
You must return the root of the tree.
After the insertion, the tree must remain complete (assuming it was already complete), aka, you must finish each row from left to right before starting a new one.
Here is an example of a complete tree :

Prototype(s)

struct node *insert(struct node *root, int value);

Code example(s)

int main() {
  struct node *root = insert(NULL, 0);
  root = insert(root, 1);
  root = insert(root, 2);
  printf("%d, %d, %d\n", root->value, root->left->value, root->right->value); // 0, 1, 2
}

This function is simple, you just have to delete every leaf that has the given value. If you don’t find any node that match these conditions, the function does nothing.
Do not forget to free the leaf and to set the fields in the parent nodes to NULL !
If you try to delete the root with this function, you must do nothing.

Warning(s)

Be aware that the tree may not be complete as you just delete the leaf, you don’t change its position and that’s okay :)

Prototype(s)

void delete_leaf(struct node *root, int value);

Code example(s)

int main() {
  struct node *root = insert(NULL, 0);
  root = insert(root, 1);
  root = insert(root, 2);
  delete_leaf(root, 2);
  printf("%d, %d\n", root->value, root->left->value); // 0, 1
}

The goal of this function is simple as well, you have to write a function that deletes the First Node that has the given value. For that, you will search in the tree using a BFS (Breadth First Traversal).
You must replace the deleted node with the right-most node from the last row.
You will return the root of the tree after the deletion.

Hint(s)

We recommend traversing the binary tree while storing the target node and the last encountered node (aka, the last leaf) in variables to perform operations on them.

Prototype(s)

struct node *delete_node(struct node *root, int value);

Code example(s)

int main() {
  struct node *root = insert(NULL, 0);
  root = insert(root, 1);
  root = insert(root, 2);
  root = delete_node(root, 0);
  printf("%d, %d\n", root->value, root->left->value); // 2, 1
}

The goal of this function is to display the binary tree in a readable way.
When printing, nodes at the same height in the tree are on the same line and separated by tabs ("\t"), from left to right. Each line must end with a newline character ("\n").

To achieve this, you will traverse the tree using a BFS. Do not forget to print a newline at the end.
If the tree is empty, the function doesn’t do anything.
Be aware that the indentation must be marked by a tabulation (\t) and that the indentation must not appear before newlines.
You can also assume that the given tree will always be complete.
For example :
The tree 1 (root), 2 (left child), 3 (right child) gives us :

1
2 3

Prototype(s)

void pretty_print(struct node *root);

Code example(s)

int main(int argc, char *argv[]) {
  if (argc == 1)
      return 1;
  
  struct node *root = NULL;
  for (int i = 1; i < argc; i++) {
      root = insert(root, atoi(argv[i]));
  }

  pretty_print(root);
  return 0;
}

Output

42sh $ ./pretty_print 1 2 3 4 5 6 7 8 9 10 11 12 13 14 | cat -e
1$
2    3$
4    5    6    7$
8    9    10    11    12    13    14$
42sh $

`Fundamentals/vector_tree.c`

In this part of the Practical, you will implement a binary tree using a vector instead of pointers.
The idea is to store the tree in an array while preserving its structure as a complete binary tree.

For a node stored at index i :
Its left child is at index 2 * i + 1
Its right child is at index 2 * i + 2

As the tree is stored in a vector, you will have to manage your memory wisely.
The vector struct is given in the vector_tree.h file, we advise you to take a look at it to better understand how it works.

The goal of this function is to insert a value into the tree and return the vector.
The insertion must respect the structure of a complete binary tree. This means that the value is added at the first available position in the last level, from left to right.
In practice, this corresponds to inserting the value at the end of the array.

In the case where there isn’t enough memory, you must double the length of the array.
And if the vector is NULL, you must create it, set the size to two and insert the value as the root.

If something fails, you just return NULL.

Prototype(s)

struct vector *insert(struct vector *tree, int value);

Code example(s)

int main() {
  struct vector *tree = insert(NULL, 1);
  tree = insert(tree, 2);
  tree = insert(tree, 3);
  for (size_t i = 0; i < tree->nb_elements; i++)
      printf("%d ", tree->values[i]);
  printf("\n"); // 1 2 3
}

The goal of this function is to delete the first node that has the given value.
The search must be performed using a Breadth First Search. In the case of a vector representation, this corresponds to iterating through the array from the beginning.
Once the node is found :

- Replace it with the last element of the vector and then remove the last element (replace it by 0).
- Divide the size of the array by 2 if the number of elements is less or equal to half of its size.

If no node matches the value, the function does nothing.

Prototype(s)

void delete_node(struct vector *tree, int value);

Code example(s)

int main() {
  struct vector *tree = insert(NULL, 1);
  tree = insert(tree, 2);
  tree = insert(tree, 3);
  delete_node(tree, 1);
  for (size_t i = 0; i < tree->nb_elements; i++)
      printf("%d ", tree->values[i]);
  printf("\n"); // 3 2
}

In the same way as in the pointer-based tree, you must implement the function pretty_print to display the tree with a row by line and with tabulations (\t) between nodes.
You will simulate the traversal using indices instead of pointers.
On an empty tree, you just print an empty string.
In any other case, you must print a newline at the end.

For example :
The vector 1, 2, 3 gives us :

1
2 3

Prototype(s)

void pretty_print(struct vector *tree);

Code example(s)

int main() {
  struct vector *tree = insert(NULL, 1);
  tree = insert(tree, 2);
  tree = insert(tree, 3);
  tree = insert(tree, 4);
  tree = insert(tree, 5);
  tree = insert(tree, 6);
  pretty_print(tree);
}

Output

42sh $ ./vector_pretty_print | cat -e
1$
2	3$
4	5	6$
42sh $

`Fundamentals/parsing.c`

In this part of the practical, you will have to parse a file containing expressions, one for each line. An expression is presented as follows :

instruction[number of times it should be repeated]
You will first store these instructions in an Binary Tree as shown in the first part of this practical.

To make your life easier, you will first write a function that takes a string and parses it to create a node. To be correct, the string you will receive will follow this format :
node_type[condition]\n
The “[condition]” is optional and may not be here every time. But when it is present, the condition will either be a positive number or the word “left” or “right”. And when don't detect a condition, it is the same thing as having the condition being "[1]" (you will see later why).
The node_type is a unique character that represents an action. It can be one of the following :

- ‘.’ represents the PRINT node type
- ‘+’ represents the PLUS node type
- ‘-’ represents the MINUS node type
- ‘E’ represents the EMPTY node type

If any of this is not respected or if the format is not correct, you must return NULL.
For now, you can leave left and right variables as NULL, we will update them later.

Hint(s)

The string lib (string.h) is very useful for this kind of work, do not hesitate to use functions like strcmp or strchr !

Prototype(s)

struct node *create_node(const char *line);

Code example(s)

int main() {
  struct node *n1 = create_node("+[3]\n");
  struct node *n2 = create_node(".\n");
  struct node *n3 = create_node("E\n");
  struct node *n4 = create_node("X\n");
  printf("%d\n", n1 != NULL); // 1
  printf("%d\n", n2 != NULL); // 1
  printf("%d\n", n3 != NULL); // 1
  printf("%d\n", n4 != NULL); // 0
}

To parse a file, you need to read a given file, each line represents a node.
This is similar to the vector representation, however, you have to translate it to fit into the given structure.
For a node located at line i, the left child is located at the line i * 2 and the right child is located at the line i * 2 + 1.
If the file doesn’t exist or if any error happens, you must return NULL.

Hint(s)

We advise you to use functions that you already implemented in the previous files, they could help you very much !

Prototype(s)

struct node *parse_file(const char *filename);

Output

// Given a file "example.nook" containing:
// +[2]
// .
// E
int main() {
  struct node *root = parse_file("example.nook");
  // root is a PLUS node with condition 2
  // root->left is a PRINT node
  // root->right is an EMPTY node
  printf("%d\n", root != NULL); // 1
}

In order to execute the tree, you will traverse the tree, using a DFS, and execute Nodes as you encounter them.
In order to do that, you will need to create a recursive function that takes a node node and an int value. The function will apply the operation specified by the node_type of node like so :

- for PRINT, you will print the current value as a character (for example, printing the value 48 will print the char ‘0’).
- for PLUS, you will increment the value by one.
- for MINUS, you will decrement the value by one.
- for EMPTY, nothing happens

If there is a condition, there are two possible scenarios :

- the union contains an int. In that case, you will repeat the operations a number of times equal to that int
- in case of LEFT or RIGHT, you will execute the left or right child (depending on which one you find) a number of times equal to the calculated value of the current node (aka, after the current node operation).

You will then call the function recursively on the left and right child of the node. If at least one of them is NULL, you must print the current value like with the PRINT command, but only once, even if the two children are NULL and thus, before the two children are called. Some characters don't have any representation in the terminal, so it is normal you don't see them appear. For example the number 2 won't display anything in the terminal.

If node is NULL or if value is strictly negative, you must return and do nothing.

Prototype(s)

void execute_tree(struct node *node, int value);

Code example(s)

// Given a file "hello.nook" containing:
// +[72]
int main() {
  struct node *root = parse_file("hello.nook");
  execute_tree(root, 0); // prints 'H' (ASCII 72)
}

Code example(s)

// Given a file "hello_weird.nook" containing:
// +[2]
// +[left] <- executes the left node 3 more times because the value is 3 after the value is updated, then executes both children
// E
// +[69]
int main() {
  struct node *root = parse_file("hello_weird.nook");
  execute_tree(root, 0); // prints "HHHH" four times
}

Finally, you will create a program that can take arguments. This program will take the name of a file containing some “code” as first argument. If more than one file name is detected, it is considered as an error.
Using the functions that you have already coded, you will create the corresponding Binary Tree, execute it with a base value of 0 and don't forget the newline at the end.
You will have to handle errors, if anything bad happens, you must return 1, else 0.
Do not forget to free everything at the end.

Output

42sh $ cat hello.nook
+[72]
42sh $ ./parser hello.nook | cat -e
H$
42sh $ echo $?
0
42sh $ ./parser
42sh $ echo $?
1
42sh $

You will now have to add the pretty-printing.
You will have to create the Binary Tree and print it in stdout without executing the tree.
The implementation is up to you, but just know that you will have to print the character (aka, the node_type and only the node_type) associated with each instruction of your nodes.

To activate the pretty-print, you will have to detect the flag “-p” or “--pretty-print” in the arguments of the binary. If any error occurs, print nothing and return 1, else 0.

Hint(s)

To detect a flag, you just have to check if the string is present in the arguments.

Output

42sh $ cat empty.nook
E
E
E
42sh $ ./parser -p empty.nook
E
E    E

`Fundamentals/expansion.c`

Information

In this part of the practical, you will implement a simple parser that handles variable assignments and substitutions.
For that, we will give you a linked list with some functions. They are located at expansion.h and implemented in expansion_aux.c, don’t hesitate to add your own functions or modify the given ones if they not please you.
The implementation is up to you, you can even use other structs or remove the given ones if you want.

You will implement the char *weird_copy(const char *input) function which takes a string as input and basically returns a copy, except for some exceptions.
The input will be composed of multiple lines that will follow one of these two formats :

- “var1=var2”
- “$var3”
where var1, var2, and var3 each represent different variables.
When you encounter a line of type “var1=var2”, you will have to store in your struct the value var2 associated to the key var1, in this case, you can just copy this part of the line to the result.
And when you encounter “$var3”, you will have to “expand” it. Aka to search in your struct for the value associated to the key var3, let’s say that the value is toto here, and replace it by toto ($ included).

Be aware that you will have to handle cases where the expansion is located at the declaration of a variable. For example :

"var1=var2\n
yes=$var1"

Will give :

"var1=var2\n
yes=var2"

and the declaration should still work as expected after the expansion of the variable (yes will be associated with the value var2).
and you can also have :

"var1=toto\n
$var1=var1"

Will give :

"var1=toto\n
toto=var1"

Here, you will have in your struct, the key var1 associated with the value toto AND the key toto associated with the value var1.

If the given string is NULL or if any malloc fails, you just return NULL.
If a string can’t be expanded (because it is not stored in your struct), you just replace it by an empty string.
Beware that you only have to expand what is stored at the moment (so if a variable is defined later, you don't have to expand it).

Prototype(s)

char *weird_copy(const char *input)

Code example(s)

int main() {
  char *result = weird_copy("a=hello\n$a\n");
  printf("%s", result);
  free(result);
  return 0;
}

Output

42sh $ ./expansion | cat -e
a=hello$
hello$
42sh $

Code example(s)

int main() {
  char *result = weird_copy("a=var\ncoucou_$a\n");
  printf("%s", result);
  free(result);
  return 0;
}

Output

42sh $ ./expansion | cat -e
a=var$
coucou_var$
42sh $

Hint(s)

We highly advise you to write an auxiliary function to retrieve the expanded variable.

Warning(s)

Do not forget to copy the newline each time !

During this practical, you will continue working on parsing. This time, instead of using binary trees, you will manipulate stacks and queues to evaluate mathematical expressions.

The goal of this exercise is to evaluate expressions written in Reverse Polish Notation (RPN) using the structures already provided in queue.c and stack.c.

`Proficiencies/`

Reverse Polish Notation (also called postfix notation) is a way of writing mathematical expressions where operators come after their operands.
Example :

Output

3 4 + 2 *

This expression is equivalent to :

Output

(3 + 4) * 2

`Proficiencies/parse_exp.c`

You will first write a function that parses a string containing an RPN expression and stores it inside a queue.
Numbers are positive integers only and supported operators are :

- +
- -
- *
- /
If the string is not valid or contains an invalid character, you must return NULL.
The expression will always follow this format :

Output

number number operator number operator ...

Output

number

Each element of the expression is separated by a space.
Examples :
“3 4 + 2 *” must become :

Output

3 -> 4 -> + -> 2 -> * -> NULL

“42” must become :

Output

42 -> NULL

“4 2” must become :

Output

NULL

Prototype(s)

struct queue *parse_expression(const char *str);

`Proficiencies/evaluate_rpn.c`

Once the queue is filled, you must evaluate the RPN expression using a stack.
Keep in mind these rules :

- If the expression is invalid, or contains an invalid character, the function must return 0
- If a division by zero occurs, the function must return 0
- At the end of the evaluation, the stack must contain exactly one value
- You must destroy the stack when the evaluation is finished
- You must destroy the queue if it has not been used entirely for any reason.

You will have to follow these instructions :

1. Pop an element from the queue
2. If the element is a number → push it into the stack
3. If the element is an operator :
- pop the last two numbers from the stack
- apply the operation
- push the result back into the stack
4. Repeat from step 1

Prototype(s)

int evaluate_rpn(struct queue *queue);

For example, with the queue 3 -> 4 -> + -> 2 -> * -> NULL, we get these steps :

Output

push 3
push 4
+  -> pop 4 and 3 -> push 7
push 2
*  -> pop 2 and 7 -> push 14

`Proficiencies/main.c`

You must now create a program that reads an expression from the program arguments and prints the result on stdout. For examples :

Output

42sh $ ./rpn "3 4 + 2 *" | cat -e
14$
42sh $

Output

42sh $ ./rpn "2 2 +" "minimake is coming"
42sh $ echo $?
1$
42sh $

The program must return 1 if :

- no argument is given
- more than one argument is given
- the expression is invalid or contains an invalid character

Otherwise, it must return 0.

The Nook Games™ `1.0.2`

Binary trees / Parsing

Introduction

`Fundamentals/basic_tree.c`

`Fundamentals/vector_tree.c`

`Fundamentals/parsing.c`

`Fundamentals/expansion.c`

`Proficiencies/`

`Proficiencies/parse_exp.c`

`Proficiencies/evaluate_rpn.c`

`Proficiencies/main.c`

This page and all subpages are for internal use at EPITA only.

Copyright © 2026-2027 - EPITA

The Nook Games™ 1.0.2

Binary trees / Parsing

Introduction

Fundamentals/basic_tree.c

Fundamentals/vector_tree.c

Fundamentals/parsing.c

Fundamentals/expansion.c

Proficiencies/

Proficiencies/parse_exp.c

Proficiencies/evaluate_rpn.c

Proficiencies/main.c

This page and all subpages are for internal use at EPITA only.

Copyright © 2026-2027 - EPITA

The Nook Games™ `1.0.2`

`Fundamentals/basic_tree.c`

`Fundamentals/vector_tree.c`

`Fundamentals/parsing.c`

`Fundamentals/expansion.c`

`Proficiencies/`

`Proficiencies/parse_exp.c`

`Proficiencies/evaluate_rpn.c`

`Proficiencies/main.c`