Solve boolean algebra in assembly?

Question

I need to write a program to solve boolean expressions.

I have a string such as: '1+0*(1*0)'

How could I go about getting the result of this expression?

I'm thinking of changing it into postfix using the Shunting-yard algorithm algorithm and then solving it but I don't know if it's necessary. Any ideas on how to do this will be appreciated.

Answer 1

If the equation is already in post-fix notation, you can solve it without the Shunting-Yard algorithm. For example, the above 1+0*(1*0) would be 1 0 1 0 * * +. Just push the elements onto a stack until you reach an operator, then pop 2 elements, and evaluate the result, pushing it back onto the stack.

In the example, 1, 0, 1, and 0 get pushed onto the stack. Then * causes the stack to pop 0 and then 1. The result is 0. It is pushed onto the stack, which now contains 1, 0, 0 (order from bottom to top). The * pops 0 and 0 from the stack, which results in 0, which is pushed back onto the stack. Finally, + pops 0 and 0 from the stack, leaving the stack empty, and the result is 0.

This can be implemented in assembly quite easily because almost every CPU has a built in stack. Just read of the characters from the string and follow the steps above. You won't have to worry about parsing words because the operands/operators will not be longer than one character each.