AI Program in Java: Expression Processing and Truth Table Generation

This document provides a comprehensive solution for an AI assignment that involves creating a Java program to process logical expressions and generate truth tables. The program's methodology includes formulating expressions, identifying independent variables and sub-expressions, and constructing truth tables. The code is thoroughly commented for easy understanding. The formulateExpression function handles user input, expression validation, and identification of variables and sub-expressions. The makeTruthTable function generates the truth table based on the independent variables and sub-expressions, utilizing a 2D array to store truth values. The printTruthTable function displays the generated truth table in a tabular format. The solution also includes an analysis of the searching algorithm, including its partial correctness and worst-case time complexity, which is determined to be O(n) where n is the number of independent variables. This assignment showcases a practical application of AI principles in logical expression processing and truth table generation.

METHODOLOGY
In this program, the approach that I used was to get towards the program goal step by step. The
program required three main goals or outputs to be achieved –
 Print the list of all independent variables in the given expression
 Print all the possible logical expressions and sub-expressions
 Print the truth table for the input expression.
In our program, the approach that we used is simple as it includes completing the above tasks one after
another. The code is made fully commented so that our approach becomes easy to understand for any
person who reads those comments.
Very first, we declared the two main required variables in the program as expressionVariables and
midExpressions, both ArrayList which will store independent variables and logical expression in the
program. We have made a simple and clear main method by minimizing the number of statements,
added three function call statements in the main method. The first function called is
formulateExpression(), which is tasked to formulate and process the given expression. The second
function call made is makeTruthTable(), which will create truth table based on the expressionVariables
and midExpressions parameters. The third function called is printTruthTable(), which will print the truth
table passed as input to console.
Now, we will discuss in depth what actually our formulateExpression function is performing –
 The function will get input expression from user by creating a scanner class object getExpress,
this input expression is stored in actualExpression variable. Before getting input from user, the
user is given some instructions about how input expression should look like, this is done so as to
minimize the error in input. Finally getExpression object is closed after input is taken.
 Next, first expression length is checked if its equal to 0 i.e. empty string then an exception is
thrown. Otherwise we will continue with the expression processing. charactersOfExpression is a
char array that is made from input expression by converting input string into char array for ease
in further processing.
 We will now traverse through each and every character of the expression so as to classify them
into operator or variable and subsequently throwing exceptions if the expression has wrong
syntax. Adding of the variable to expressionVariable list is done only after ensuring that the
variable is already not present in list. For checking, one for loop is added before adding variable
to list.
 If the character is not found to be a variable, then the character is checked to be equal to either
opening or closing parenthesis. If it is ‘(‘ then firstly syntax error in expression is checked and an
exception is thrown if it is found. The bracket count is incremented by 1. The same is done for
‘)’ character i.e. first exception is thrown if syntax is incorrect then bracketCount is
decremented.
 Next the bracketCount is checked each time we encounter any ‘)’ character. This count is
checked to be less than 0 that means incorrect syntax else if this count is zero or greater then it

means that we can check for subexpression now. For this, we will set three variables counter,
end and start. End will be set to current index i plus 1 and start will be set to zero. Counter will
be set to 1, which is a local variable for count.
 Now a for loop is made to iterate backwards to check for subexpressions, the logic used is
incrementing the counter when any closed bracket is encountered and decrementing the same
if open bracket is encountered. If in any case this counter becomes equal to zero then save the
start and end index as it will be our subexpression.
 We will extract this subexpression by using substring method and passing stroed start and end
index. The last thing we need to check after getting subexpression is that if this subexpression is
equal to the original input expression or if this subexpression is less than 3 characters length. If
none of the two is the case then we will add this subexpression to midExpressions arraylist.
 Now After we have checked that the character is not a variable and it is neither any parenthesis,
then another else condition will check if this character is equal to any of the operators i.e. *, +, -.
If the character is equal to any of these operators then we will check certain sub conditions like
AND/ OR operators should not be at the beginning of expression and neither at last of
expression or no operator must be followed by any other operator or parenthesis.
 After all the possible conditions is checked, now we will check if bracketCount is more than 0
this will again throw an exception as this means number of closed bracket exceeds the number
of open brackets in expression. With this we performed all the required tasks in formulate
expression function.
We will now discuss how makeTruthTable function works and what tasks are accompolished by it in the
program –
 The parameters that need to be passed in this function are expressionVariables ArrayList and
midExpressions ArrayList.
 The number of rows in truth table will be computed first by setting rows variable equal to the
2^n where n represents the number of independent variables.
 Noe we will set columns variable i.e. number of columns of the truth table to number of
independent variables plus number of sub expressions.
 The next step is declaring a 2D array called truthTable of rows X columns matrix. We will add
headings or name of independent variables and sub expressions to the zero row of matrix.
 Now for remaining rows traversal will be performed starting from row 1 to rows, where for each
row binaryRows is calculated as binary representation of row indices. And it is checked if the
length of binary representation of rows is equal to number of columns by iterating over columns
one by one.
 Now again iteration is done over columns to check whether they are zero or one and fill T or F
accordingly in the table.
 Now the part in which the truth values will be added in the table for actual and sub expressions,
this section will begin after the expressionVAriables or independent variables have finished.
 For loop will run from expressionCount equal to 0 to length of truthTable at 0 row ant ith
column. We will check if the character is equal to ‘(‘ or ‘)’ or any operator. Then they will be

directly concatenated to boolString, which is responsible for storing bool expression for each
case in truth table. If its neither any operator nor any parenthesis then it means that it is a
variable. Then we will check which column header matches the independent variable character
encountered and subsequently adding truth value of variable to boolString.
 Now after all expressionVariables are traversed we will now convert the created boolString to
Boolean and then insert into table. For this, we will use scripting engine for both conversion and
evaluation of Boolean string. Using valueOf function to evaluate the string and getting resultant
Boolean value. Setting truthTable at index ith row and jth column value to the result obtained.
 Finally the function returns the truthTable created.
We will now discuss how printTruthTable function works and what tasks are accompolished by it in the
program –
 This is a very simple function which iterates over the rows and columns of the input parameter
matrix, in order to traverse each cell and prints all values in a matrix or tabular format.
Prove correctness for your searching algorithm of section C.2.ii, i.e., partial correctness and termination
–
As no variable in C.2.ii in our program is ending with infinite loop therefore partial correctness of our
program is proved.
Analysis for your searching algorithm and worst case –
The searching algorithm implemented in our program runs expressionVariables size times which means
that it will run for the number of times independent variables are encountered by our program till now.
So, for each character independent variable it will iterate over the independent variables found till now,
which may vary for different cases. If we see worst case complexity then, suppose we have 5
independent variables in expression which are all found by the program till now. But the program will
run 5 times each time there is an independent variable found in the expression to check whether it is
already in the list. So, for ‘n’ independent variables in subexpression the worst case complexity becomes
O(n).