Coding A Boolean Algebra Expression Solver
How I coded a boolean algebra expression solver to simplify my homework and more importantly my HSC.
Introduction
In years 11 & 12, through my subject, Software Design & Development. Hardware concepts, binary & hex conversions, logic gates, and much more low-level concepts and theory were taught through my hardware major selection. While a lot of this concept was confusing and needlessly complex, such as bidirectional shift registers. Many other ideas weren't as complicated but just repetitive or boring. One of the most essential but also tedious tasks was calculating & simplifying Boolean algebra expressions. Like any maths, repetitive problem solving as well as practice & validation is the key to success. An issue we had, however, in SDD was finding questions!
While Software Design & Development is a great subject (assuming you have a good teacher, of course), the small number of people being enrolled in it each year, around 400-500 people, the available questions, especially at a public school, minimal. Excluding the official HSC questions, for my school, there was only a total of 2 official practice papers to use and review for our HSC. While sites like THSC were a great help, providing many more questions than typically available, there still were only so many papers to use. As a result, we often had to create our own questions to use and answers.
While creating questions using Boolean algebra was simple, validating and checking them was anything but. There were often times when my classmates and I would all get unique or different answers for a Boolean algebra question, with no one at all knowing which one specifically was correct.
Due to this inherent problem, I decided to do what I know best and automate the thing, and thus my journey of coding a Boolean algebra expression solver started.
The Process
Using what I knew best at the time, C# using WPF. I decided to work on this calculator. Like any other maths, however, Boolean algebra worked in well binary or Boolean expressions being true or false instead of having numbers from 1-10. However, one significant similarity that it did have was it also following the order of operations rule. Due to this, to start, I first explored how scientific calculators themselves worked and, in extension, how to program them.
Calculating Equations Through Reverse Polish Notation
After some further research, I discovered how most scientific calculators worked, through reverse polish notation or simply postfix notation. Many other scientists and mathematicians throughout history had this problem of the order of operation. Early computers/calculators could not automatically abide by the rules of the orders of operations. Instead, they went from left to right, evaluating each expression with the same priority. Due to this, a standard was created in which the operators precede their operands, eliminating the need for parentheses and priorities. By organizing an equation this way, early calculators could read left to right while also maintaining the correct order of operation.
An example of an equation converted from infix notation (normal) to reverse polish notation (or postfix) is shown below.
\( ( 3 - 4 ) x 5 \)
Later becomes:
\( 3 4 - 5 x \) or \( 5 3 4 - x \) respectively.
Using the same logic of RPN in our Boolean expression solver, we were able to correctly follow the correct order of operations and allow parenthesis support. The only issue that remained was converting our infix notation to postfix notation.
Converting To Reverse Polish Notation Using the Shunting Yard Algorithm
To resolve this last issue of converting our infix notation to postfix, we can use an algorithm called the shunting yard algorithm to solve. The method the shunting yard algorithm uses is as the following:
- Expressions are parsed left to right
- Each time a number or operand is read, we push it back
- Each time an operator comes up, we pop the required operands from the stack, perform the operation, and push the result back to the stack
- We are finished when there are no tokens (numbers, operators, or any other mathematical symbol) to read. The final number on the stack is the result.
Additionally, a pseudocode implementation of the algorithm is as of below:
1. While there are tokens to be read:
2. Read a token
3. If it's a number add it to queue
4. If it's an operator
5. While there's an operator on the top of the stack with greater precedence:
6. Pop operators from the stack onto the output queue
7. Push the current operator onto the stack
8. If it's a left bracket push it onto the stack
9. If it's a right bracket
10. While there's not a left bracket at the top of the stack:
11. Pop operators from the stack onto the output queue.
12. Pop the left bracket from the stack and discard it
13. While there are operators on the stack, pop them to the queue
Bypassing our Boolean algebra equation firstly through the shunting yard algorithm to convert infix to postfix notation and then finally following standard implementations of postfix calculators, we can create this Boolean expression solver. The only edits we had to do were create custom operations and implement such features and replace numbers with alphanumeric variable names.
By then giving the Boolean expression solver a bunch of pseudo values through a truth table, we calculated each expression automatically with minimal effort.
Conclusion
Overall this project was a great success! This solution allowed me to personally save tens if not multiple dozens of hours validating solutions and let the rest of my classmates solve Boolean algebra equations quickly, giving us a ton of practice questions for the HSC.
For those interested in viewing or even using this project for your own Boolean algebra needs, feel free to check out the project here, available on GitHub:
ShaanCoding