Truth Table for an expression( as string )

Question

I want to compute the truth table for an expression(valid logical expression) input by the user as a String. Can anybody post an existing solution to this or guide me in doing so?? I am thinking of using a BitArray (of size 2^no. variables) as the output (the truth table). But do not know how to start. Please help me with this.

Ex:-

 p or q or r

Should result as

 False True True True True True True True 

And

 a and b 

Should result as

 False False False True 

Answer 1

First, you will need to parse the string input to find the variables and the structure of the expression (i.e. what operations are applied to what sub-expressions).

Once you are done with that, you can represent the state of the variables as a binary integer. Whith this representation you can start from 0 (meaning all variables are false) and increment the integer representation by 1 for each row of the truth table. This way you can account for all possible combinations exactly once.

Then apply the values of the variables to the expression (subtitute true/false according to the bit value of the integer for the variables in question) and cacluate the value of the expression.

If you want compact representation of the result, you can just store the expression values for each input combination in a linear collection (e.g. vector) where the index of the output corresponds to the above integer representation of the variable values. If you know what variable maps to which bit of the input, you can re-create the full table any time you need to (e.g. for printing)

Answer 2

a way without any third party libraries is to use a DataTable with expression.

There you have even the possibility to evaluate on other result value types than just boolean.

System.Data.DataTable table = new System.Data.DataTable();
table.Columns.Add("", typeof(Boolean));
table.Columns[0].Expression = "true and false or true";

System.Data.DataRow r = table.NewRow();
table.Rows.Add(r);
Boolean result = (Boolean)r[0];

the expression syntax is not identical with your example but it does the same thing. An advantage is that its 100% .NET framework contained --> Microsoft managed. The error handling is not bad neither. Exceptions for missing operators etc...

available operators

Answer 3

I think CKen (http://cken.sourceforge.net/) (is good for you).

CKen supports both ''upper cases'' and ''lower cases'', so it supports 58 (= 2x29) single variables!

And the most important, multi-expressions can be used in it (by separators):

Example: a,b,c,d,e;(a+b)*c;d*e#a;

On the other hand, it is very fast!

---

You must define your variables before using it (variables) in your expressions.