Forem: Nathanael Demacon

How calculators read mathematical expression with operator precedence

Nathanael Demacon — Tue, 28 May 2019 15:10:46 +0000

In my journey of creating a programming language, I faced an issue: how to handle mathematical expressions with operator precedence properly without having to write a big ass algorithm? So after long long researches, I found the Reverse Polish Notation, a mathematical notation made exactly for that and used in all modern calculators!

Reverse Polish Notation (or RPN) is a Postfix notation (operators after operands) while our mosly used notation is an Infix notation (operators between a left and right operands).

But how to easily convert an Infix mathematical expression to a Postfix one? Well, the Shunting-yard algorithm is here for us! And thanks to Wikipedia, we have a pseudo-code representation of the algorithm!

Perfect, now that I knew where to start, there was another issue: how to read that thing? I will give you an example:



infix = 1 + 2 - (5 + 2 * 4)
rpn = 1 2 + 5 2 4 * + -

Yeah I know - it looks like a big mess at first sight but I will tell you how to convert and read it by hand and you'll see, it's pretty easy.

Conversion

To convert from infix to RPN, we'll need 2 stacks: one is the output, the other one is the operator stack. We'll symbolise everything in array-style:



input = [1, +, 2, -, (, 5, +, 2, *, 4, )]

output = []
operators = []

We have 2 rules:

literals always goes to the output stack
when an operator with lower or equal precedence than the last element of the operators stack is comming, pop the last element of the operators stack to the output stack

Let's convert it!

First we have 1, a literal, like said in the rules above, it goes to the output stack:



input = [+, 2, -, (, 5, +, 2, *, 4, )]

output = [1]
operators = []

Then we encounter an operator so, in the operators stack it goes!



input = [2, -, (, 5, +, 2, *, 4, )]

output = [1]
operators = [+]

Again, we face a literal so we put it in the output stack:



input = [-, (, 5, +, 2, *, 4, )]

output = [1, 2]
operators = [+]

After that, we have an operator that have the same precedence than the last operator in the operators stack which means that the actual + will be poped into the output stack and we will push the - to the operators stack:



input = [(, 5, +, 2, *, 4, )]

output = [1, 2, +]
operators = [-]

Parentheses doesn't have precedence in Infix notation but we put it in the operators stack to separate the enclosed expression until we find a closing parenthese:



input = [5, +, 2, *, 4, )]

output = [1, 2, +]
operators = [-, (]

Again, 5 is a literal:



input = [+, 2, *, 4, )]

output = [1, 2, +, 5]
operators = [-, (]

+ is an operator, since the last operator in the operators stack is an opening parenthese, we don't care and just push it in the stack:



input = [2, *, 4, )]

output = [1, 2, +, 5]
operators = [-, (, +]

2 is a literal:



input = [*, 4, )]

output = [1, 2, +, 5, 2]
operators = [-, (, +]

* is an operator with higher precedence than the last operator in the stack (+) so we just push it:



input = [4, )]

output = [1, 2, +, 5, 2]
operators = [-, (, +, *]

4 is a literal, at this point I think that you must have understand that all literals goes in the output stack:



input = [)]

output = [1, 2, +, 5, 2, 4]
operators = [-, (, +, *]

Then we find a closing parenthese which means that we'll pop every operators into the output stack until the opening parenthese (we completly delete the opening parenthese, we don't need it anymore):



input = []

output = [1, 2, +, 5, 2, 4, *, +]
operators = [-]

Since we doen's have any more elements in our input stack, we pop all the operators into the output stack:



input = []

output = [1, 2, +, 5, 2, 4, *, +, -]
operators = []

You did it! You completly converted an Infix notation into a RPN!
Here's a graphical representation of what we did:

Now if you're not already bored by the length of this post, we'll see how to calculate it.

Calculation

We have our beautiful RPN: [1, 2, +, 5, 2, 4, *, +, -] but now we want to calculate the mathematical expression to get its value. It's a lot simpler than it seems:

We'll base on a single variable, doesn't need more than that:



rpn = [1, 2, +, 5, 2, 4, *, +, -]

Then we need to find the first operator in the stack (starting to the first element which is 1 here). Once we found it, we'll fetch the literal before and the one before the one before:



left = rpn[i - 2]
right = rpn[i - 1]
operator = rpn[i]

In our case, left is 1, right is 2 and operator is +. Seems like we got all we need! Simply doing left + right will give us the result (3). Then we have our number and just put it in replacement for the left, right and operator:



rpn = [3, 5, 2, 4, *, +, -]

And we repeat. First operator is *, left is 2, right is 4, calculate and replace (2 * 4 = 8):



rpn = [3, 5, 8, +, -]

Again with the +, left is 5 and right is 8, 5 + 8 = 13:



rpn = [3, 13, -]

Next first operator is -, right is 3 and left is 13, 3 - 13 = -10:



rpn = [-10]

Since we doesn't have any other operators, the last number in the stack is the result, otherwise you did it wrong at some point.

So rpn[0] is our result, which is the result of 1 + 2 - (5 + 2 * 4) as we wanted. Yay!

Conclusion

Now that you learned a new mathematical notation, you can have fun with and build your own calculator or programming language that can properly resolve operator precedence.

What other mathematical expression do you know and why do you use them?

Twitter: @qtmsheep
Github: Nathanael Demacon

Basics of Multithreading in C

Nathanael Demacon — Wed, 09 Jan 2019 17:20:11 +0000

C programs run on a single thread by default - meaning only one instruction is executed at a time. But what if you need to perform multiple tasks simultaneously? For example, a graphical interface must remain responsive even while performing time-consuming operations in the background. This is where multithreading comes in.

Note: Multithreading is different from asynchronous programming, which allows a single thread to handle multiple tasks without blocking.

🧵 What Is a Thread?

A thread is a single sequence of instructions within a process. Each process starts with one thread, but it can create additional threads that run concurrently. These threads share the same memory space, making communication between them efficient, but also introducing risks like race conditions.

🔧 Creating a Thread in C

Let’s dive into how to use threads in C.

On POSIX systems (like Linux), the pthread library provides thread functionality. To use it, you must link your program with -lpthread. For example:

gcc -o main main.c -lpthread

Here’s a simple program that creates and runs a thread:

#include <pthread.h>
#include <unistd.h>
#include <stdio.h>

void* wait_fn(void* arg) {
    sleep(2);
    printf("Done.\n");
    return NULL;
}

int main() {
    pthread_t thread;

    int err = pthread_create(&thread, NULL, wait_fn, NULL);
    if (err != 0) {
        printf("An error occurred: %d\n", err);
        return 1;
    }

    printf("Waiting for the thread to end...\n");
    pthread_join(thread, NULL);
    printf("Thread ended.\n");

    return 0;
}

Expected Output:

Waiting for the thread to end...
Done.
Thread ended.

Explanation:

pthread_create starts a new thread and runs the wait_fn function.
pthread_join blocks the main thread until the new thread finishes.
The sleep() call pauses the thread for 2 seconds to simulate work.

Pretty straightforward, right?

🔐 Using Mutexes to Prevent Race Conditions

Multithreading introduces the risk of race conditions, especially when multiple threads access shared resources (e.g., a file or a variable). To prevent this, we use a mutex (short for mutual exclusion).

Here’s an example that shows how to safely increment a shared variable:

#include <pthread.h>
#include <unistd.h>
#include <stdio.h>

pthread_mutex_t lock;
int j;

void* do_process(void* arg) {
    pthread_mutex_lock(&lock);

    int i = 0;
    j++;

    while (i < 5) {
        printf("%d", j);
        sleep(1);
        i++;
    }

    printf("...Done\n");

    pthread_mutex_unlock(&lock);
    return NULL;
}

int main(void) {
    pthread_t t1, t2;

    if (pthread_mutex_init(&lock, NULL) != 0) {
        printf("Mutex initialization failed.\n");
        return 1;
    }

    j = 0;

    pthread_create(&t1, NULL, do_process, NULL);
    pthread_create(&t2, NULL, do_process, NULL);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    pthread_mutex_destroy(&lock);
    return 0;
}

Output:

11111...Done
22222...Done

The threads run sequentially because the mutex ensures only one thread can access the shared section at a time.

Tip: Even if you switch the order of pthread_join, the output will be the same because the threads themselves are synchronized by the mutex.

🚦 Semaphores: Flexible Synchronization

Semaphores are another synchronization mechanism, similar to mutexes, but more flexible. Unlike mutexes, semaphores don’t have ownership - any thread can lock or unlock them.

This makes semaphores suitable for managing access to a limited set of resources (like a pool of connections or permits).

We won't dive into full semaphore examples here, but if you're interested, check out the semaphore.h library and functions like sem_init, sem_wait, and sem_post.

✅ Wrapping Up

As you’ve seen, multithreading in C is powerful yet surprisingly approachable. With just a few function calls, you can start writing concurrent programs - but always keep safety in mind with tools like mutexes and semaphores.

How did I started learning a new technology

Nathanael Demacon — Sun, 02 Dec 2018 16:39:28 +0000

There are a lot of technologies, out there and for every needs: programming languages, softwares, operating systems, etc... But what if you wanted to learn a new technology? Because of any reason? In this post, we will see how I learned a new technology to give you an idea of how to start.

Why

It's a fact: some technologies are better for doing things that other ones can't do better and vice versa. While some technologies can be the same, there are differences that can lead to change to another one.

Programming languages for example are a matter of syntax, performance and community while softwares are used for their usefulness or design; and operating systems are for what they can do (Windows has Active directory, Linux has full customisation, etc...).

Jobs offers can also be a great reason of why to learn a technology.

However, what makes me learn a technology is mostly the hype. I know that most peoples thinks that following the trend isn't a great thing but who know? Go was just a trend and becomes one of the most used programming languages and the same thing applied for the BlockChain. It's just a matter of wanting to learn this technology because it's popular, if it's popular it's certainly a good one.

How

The tech's documentation will become your life, tutorials and forums too. There is not really a good way to learn something, it depends on your determination and how you learn better.

Books are the first choice for most peoples. Personnally, doing little projects for fun is how I learn a technology but it keeps me away from the theorical side.

What did I learned?

The technology I chosen to learn was the Crystal programming language. Why? Because it's a trend and have the Ruby's syntax. Also, I recently started to learn how to use Arch Linux, totally for fun.

The fact is that I don't want to stay in one technology, which is boring in the long term. I want to discover things everyday because of my curiosity.

Conclusion

Maybe that after this post you will start learning a new technology, for any good reason. Or maybe that you will create something that other people will learn because it's a fantastic idea.

Discovering new things and making the world evolve is something that moves us and needs to continue like that.

And you: how and why do you started learning something?

How to properly use passwords

Nathanael Demacon — Mon, 12 Nov 2018 00:05:25 +0000

There are different kind of passwords uses:

the "my memory isn't that good" (also call the "I don't care anymore" method) with passwords like qwerty or 123456 or literally password
the one that uses social information, ex: 199105Bob
the good ones

Let's be real, the first two aren't secure at all, not even a little. But what about "the good ones"? Well, they are what we are talking about.

Maybe sometimes you wonder if your password is safe enough, and you hope that your account will not be taken by someone else by any way. First, we need to take a look at what attacks can be done to find your password.

Brute-force attack

This method is used to try every possibility in a way find your password. It's not used a lot because it requires massive amounts of time and power to be achieved, depending on the target's password length.

The longer a password is, the longer it will take to try every possibility.

Dictionary attack

While brute-force attack tries every possible characters, security researchers found a way to escape the useless trials and focus on commonly used passwords.

A dictionary attack use pre-defined passwords list instead of random characters. Rules can even be added to match the target's information and remove passwords that may not work, like its birthdate, its name, etc... That's social engineering.

To prevent this method, don't use obvious personnal information in your password and check if it's not already in a database.

Your web browser's saved passwords

Maybe that you use the "Remember my password" option while using the internet. While this option can be very comfortable to use, it's not secure at all.

Web browsers cipher your passwords, but they also decipher them to fill password inputs, to make this happen, they use a stored key. So why can't we decipher them too? Well, we can, tools like LaZagne are the proof, that's why you should never use this option.

Solutions

Now that I told you how your password can be hacked, I must tell you how to create strong passwords that are not a plague to use.

Password managers

Those are softwares that helps you to manage your passwords. The best use of them is to export your password with a file (that can be transferred in a secure way using WarShield or something else).

Dashlane - Very popular and self-hosted
Vault - Open-source one

You can find a lot of password managers on the internet, maybe you will find the one who match your needs.

Easy to remember strong passwords

A dream for your accounts, a nightmare for hackers, the sure thing is that you can remember sentences. What about using our brain's capacity in order to create passwords?

This method doesn't need a random sentence, just try to make logic. I will create John Lemmon, a man that live in London at 41 Abbey Street, his password will be MniJL@Il41ab&. I see you, behind your screen, with a face saying "wtf is that?", it can be really hard the first time you use a password like this but it's really easy to remember.

The sentence was My name is John Lemmon and I live at 41 Abbey Street, the ampersand (&) is a random character with no logic behind it.

Like you see, it's pretty easy to create a very strong password without breaking your mind every time you need to remember it.

Conclusion

Today, there is no excuse for not having a secure password.

I think that there should be computer security awareness in schools to teach children to protect their data in the digital world. In the next years, it will evolve, more and more peoples are learning security and the security war will never end.

Stay safe with your data.

What I learned about cryptography in 3 weeks

Nathanael Demacon — Sun, 04 Nov 2018 23:31:52 +0000

It's been 3 weeks that I started developing WarShield, a file encryption CLI. So I wanted to tell you everything important I know today about cryptography.

Keys (passwords) in cryptography

In case you want to encrypt your data, it's good to be able to decrypt it too: that's why you use a key, more commonly named as password.

Keys in cryptography are grouped in two categories:

Symmetric-key cryptography
Public-key cryptography, also called as asymmetric-key cryptography

Symmetric-key cryptography algorithms uses only one key to encrypt and decrypt a value, unlike public-key cryptography algorithms that uses a "public key" to encrypt and a "private key" to decrypt.

^{^{Image credits: SSL2Buy}}

Those keys must be exactly the same length as required by the encryption algorithm. For instance, an algorithm like AES-256-GCM require a 128 bit key (32 characters), GCM being the "mode of operation" that define how the algorithm works to provide additional informations like authenticity.

But don't worry, you don't need to have 32 characters passwords, event though it would be secure. You can (and must) hash your keys to provide a secure and well sized key.

Random and authenticity

If you encrypt multiple values with the same key, the outputs would leak some informations about your key. Which you don't want for security reasons. A great way to secure your encrypted values is to make them fully random. And here you have: the Initialization Vector.

Initialization Vector (IV)

This technique is basically a way to mix your key with another value, best being a random value.

It's size depends on the defined encrypting algorithm mode of operation and must be given manually. It's not generated by the algorithm.

Authentication and integrity

Maybe you heard about MD5 algorithm to check if your downloaded file contain all the wanted data? Well, it's called integrity. It ensure that your data is exactly the one you want.

Authentication involve integrity and make sure that your data has been encrypted by a specific entity (for instance, a computer). It's a way to ensure the non-repudiation of data, in clear, it's mean to be sure that the data isn't falsified. An authentification value is called a Tag or a MAC (Message Authentication Code).

The most used integrity algorithms are SHA1 and MD5. For authentication algorithms it's HMAC, checksum and CMAC. There is bunch of others algorithms but here's the main ones.

^{^{Image credits: Wikipedia}}

And... That's it! There is nothing more to say about the basics of cryptography. Sure I could talk about different encryption algorithms but I find it useless in this case.

I will learn more and more about cryptography, improve my projects and maybe my own security. Hope that you learned too about cryptography 😄

Why you should reinvent the wheel

Nathanael Demacon — Sat, 27 Oct 2018 23:27:23 +0000

Sometimes some people tell to not "reinvent the wheel" by creating things that already exists. It's been time to clarify why we should reinvent the wheel and why they are wrong!

Learning

The best argument you can say in this situation is that you want to learn. Revolutionary ideas don't come that easy, if you want to learn just do something you would like to do, don't focus on creating new things especially.

You need skills to create your ideas. Get those skills by doing anything that comes in your mind!

Understanding how something works

Doing something that already exists can make yourself understand how it works and how can it be improved. Things are not perfects but are perfectibles, let's see the smartphone industry for instance.

You want to do it

You reinvent the wheel? So what? Peoples should not lead you in unwanted situations. Just have fun making things. Doesn't matter if those already exists, at least you'll be happy and that's what matters the most.

The "wheel" has been improved

The metaphor "don't reinvent the wheel" is so wrong! The wheel, strictly speaking, has been reinvented tons of times. We didn't come with a full rubber wheel in high technology cars in the first try. Things evolves because peoples "reinvent the wheel", and it should continue like that.

In conclusion, just improve yourself without thinking about making a brand new idea. It's ain't easy to find something that haven't been created yet so don't think too much about it if your only goal is to discover and explore new things.

Ideas comes with discovery.
Discoveries comes with time.

Protect your data with WarShield

Nathanael Demacon — Sat, 20 Oct 2018 22:57:01 +0000

Security has been evolving with information technology, peoples find new ways to protect your data and privacy because we need to feel secure.
Sometimes you want to go deep into security and you start to put passwords everywhere. This is why WarShield was created.

What is WarShield?

WarShield is a CLI tool made to cipher and decipher your files with a password using AES-256. It was made to ensure a full files protection inside a USB flash drive or an external hard drive. If those are lost, malicious peoples can take over your files and their data.

This is when WarShield comes with his fast and reliable solution.

How to use WarShield?

WarShield can be installed with NPM:

npm install -g warshield

After the (very) short installation, you can use the warshield CLI.

warshield (encrypt|decrypt) (file)

The first argument is encrypt or decrypt, describing the wanted action. Don't worry if you try to decrypt something that isn't encrypted, it will not do it.

Next is the file (or folder) you want to encrypt/decrypt. If it's a folder, every files in it will be processed recursively.

Launching that command will make the program asking you the password you want or need to use to encrypt or decrypt the file.

When you launch the encryption/decryption, WarShield will scan all the wanted files first. If the selected file a folder, it can take a while depending on the files weight.

WarShield on NPM: https://www.npmjs.com/package/warshield/
Github repository: https://github.com/QuantumSheep/warshield/

Thanks to 💖 this article if you enjoyed it :)

All you need to know about destructuring in JavaScript

Nathanael Demacon — Mon, 08 Oct 2018 13:30:43 +0000

There is one fact that nobody can deny- everything , once built, can be destroyed. This concept also applies to programming. In this article, I will be discussing destructuring in JavaScript.

In JavaScript, destructuring is when you decompose the properties of an object or the indexes of an array to separate them to create specific variables. This does not mean that these separated objects or arrays can never be used again in the program.

Before we begin, however, I will quickly outline some important differences between arrays and objects. Arrays have number indexes and objects have string indexes. In addition, arrays and objects use different syntax.

In JavaScript, we can put objects in arrays and arrays in objects too, the syntax let us put everything where we want.

Now let's talk about the main subject, the destructuration. Destructing an object or an array doesn't mean that you will erase it from the program and can't ever use it again, it means that you'll get a specific part of it. Let's use examples, with Axios, a famous library. We can do an HTTP request (like with Fetch API or XmlHttpRequest) which returns us the following object's schema:

We'll stick to the data property! It's an object that contains all the server's response data. Let's say that we want to get all our users from our NodeJS API with MongoDB database, we may do something similar to the following code.

In this case, the req constant will be an object with the same schema as seen before. So to get the users data, we has the req.data containing our array of users.

Now that we saw how to perform an Axios request, let's say that we only want one user that we can get from the route /api/users/:userid. For instance if the wanted user's id is 7, we do a request to /api/users/7. But what if the API returns an array? Then we can do req.data[0] which can be a good way to do it but not as practical as if we used destructors…

First, let's get the data object. We can do req.data but we don't care about others req's properties so let's only get data. What we will do is an object destructuring assignment. (Finally, some excitment)

Yes, we only got the data property and it created an object named data! And you've done a "destructuring assignment" in JavaScript, great!

For instance we can destruct multiple properties in the same destructuring assignment, Axios provide a status property so let's get it by destructuration!

We can also give default values to any destructed property like bellow.

Default value to a destructed propertyBut our object's name isn't what we really wanted, we want a users object to become easier to understand. So let's do a name's assignation without creating any more new variables.

It's cool right? You can assign destructed properties to new variable's name in the same line and it doesn't look bad at all! So now we have our well named users object.

Still, users keep being an array, what could we do with it? I present you, the array's destructing assignment:

Destructing assignment with an arrayIn this case, a is a new constant which will receive the index 0 of the array [1, 2, 3] (Which has the value 1). The constant declaration's position in the destructing assignment define the selected index that will have it's value taken.

In this case, a is a new constant which will receive the index 0 of the array [1, 2, 3] (Which has the value 1). The constant declaration's position in the destructing assignment define the selected index that will have its value taken.

Like for objects, we can have default values and multiple declarations. Their position always match the selected array's indexes.

We can also bypass any indexes we want by putting a , without any variable declaration. In the following case we will bypass the indexes 0 and 1 (2 comas). c will be equal to the third index which have a value of 6.

Bypassing indexes in an array's destructing assignmentNow that we know how to use array's and object's destructing assignment, we finally could resolve our case of the variable users being an array with only one index.

We can use destructing assignments inside one another and it will works. So put an array's destructuring assignment in an object's destructuring assignment and you'll get the same result on the selected property:

To sum up, we've destructed the property data of the axios.get('/api/users/7') instruction's. Next we assigned data to a proper variable's name, users. After that we used the array's destructing assignment to define the variable users as the first index of the data property.

Every destructuring assignment can be used recursivly like seen previously, in any order you want. Object's destructuring assignment can be used in others object's destructuring assignment and same goes for array's destructuring assignment.

Now we perfectly know how to destructs objects and arrays in JavaScript. But there's another trick you can do with destructive assignments, the " rest pattern" or "spreading". This give you the possibility to take the remaining undestructed properties/indexes to a new variable. Here's a demonstration with arrays but you can do the same with objects :

Thanks you for reading, hope that now you know everything about destructuring in JavaScript!