# Program to Print Truth Table of Given Boolean Expression

Write a program to print truth table of any given Boolean Expression.

For example,

```Input
A.B'+C
Output
A         B         C         f
0         0         0         0
0         0         1         1
0         1         0         0
0         1         1         1
1         0         0         1
1         0         1         1
1         1         0         0
1         1         1         1```

Steps

1. Ask the user to enter a Boolean expression. Let the input Boolean expression be s.
2. After that, convert the Boolean expression s to its corresponding postfix expression. Let the name of the variables that stores the postfix expression of s be postfix.
3. Count the number of unique Boolean variables in s. Let N be the number of Boolean variables in s. Initialize an array of size N with all zeros. Let the name of the array be val[]. Each index of the array stores the value of a boolean variable.
Note: Instead of using an array of size N, it is better to use an array of size 26. By doing so, we can directly map a boolean variable to its value. For example, the value of the Boolean variable ‘A’ is stored at val[0], the value of ‘B’ is stored at val[1], and so on.
4. The total number of rows in a Truth Table is equal to 2N. We repeat the following steps 2N times.
• Evaluate the expression – postfix. The value of each variable in the postfix expression is obtained from val[].
• Print the value of each Boolean variable and its output.
• Increment val[].

## Program to Print Truth Table of a Boolean Expression

Assumptions

1. The Boolean expression does not contain any spaces.
2. The Boolean expression only accepts 3 Boolean operators.
• AND operator is denoted by ” . “
• OR operator is denoted by ” + “
• NOT operator is denoted by ” ‘ “
3. The Boolean variables are denoted by uppercase alphabets.
``````#include <iostream>
#include <iomanip>
#include <stack>
#include <vector>
#include <math.h>
using namespace std;

// Expression class is a utility class
// it provides 2 functionalties
// infix_to_postfix() method converts a boolean string to postfix form
// evluate_postfix() methods evalutes a postfix expression and retuns the answer
class Expression {

static int prece(char t) {
if (t == '\'')		return 2;
else if (t == '.') return 1;
else 			return 0;
}

static bool isOperator(char t) {
return t == '.' || t == '+' || t == '\'';
}

static bool isOperand(char t) {
return t >= 'A' && t <= 'Z';
}

public:

// the function convert given infix expression to postfix expression and returns the postfix expression
// it accepts 1 argument
// infix - it is the input infix expression we want to covnert
static string infix_to_postfix(string infix) {

stack<char> opStack;

// it stores final postfix expression
string postfix;

// it stores each token of infix expression
char token;

infix.insert(0, 1, '(');
infix.push_back(')');

postfix = "";
for (int i = 0; i < infix.length(); ++i) {
token = infix[i];
if (token == '(') {
opStack.push(token);
}
else if (isOperand(token)) {
postfix.push_back(token);
}
else if (isOperator(token)) {
while (isOperator(opStack.top()) && (prece(opStack.top()) >= prece(token))) {
char temp = opStack.top();
opStack.pop();
postfix.push_back(temp);
}
opStack.push(token);
}
else if (token == ')') {
while (opStack.top() != '(') {
char temp = opStack.top();
opStack.pop();
postfix.push_back(temp);
}
// pop again to remove extra '(' from the stack
// as it is already paired with ')'
opStack.pop();
}
}

return postfix;

}

// the function evaluates a postfix expression
// it accepts 2 arguments
// 1. postfix - it is the postfix expression we want to evaluates
// 2. val - it stores the values of boolean variables in postfix expression
static int evluate_postfix(string& postfix, vector<int>& val) {

stack<int> stk;
char token;

for (int i = 0; i < postfix.length(); ++i) {
token = postfix[i];
if (isOperand(token)) {
stk.push(val[token - 'A']);
}
else if (isOperator(token)) {
int v1, v2;
if (token == '\'') {
v1 = stk.top();
stk.pop();
stk.push(!v1);
}
else {
v1 = stk.top();
stk.pop();
v2 = stk.top();
stk.pop();
switch (token) {
case '+':
stk.push(v2 or v1);
break;
case '.':
stk.push(v2 and v1);
break;
}
}
}
}
return stk.top();

}

};

// this function increments val in binary
// for example if the content of val is 011011
// the content of val after incrementing will be 011100
// 011011
// +    1
// ______
// 011100
// NOTE: Not every value in val is considered while incrementing
// only those position that var corresponds are considered
void increment(vector<char>& var, vector<int>& val) {

int carry = 1;
for (int i = var.size() - 1; i >= 0; --i) {
if (val[var[i] - 'A'] == 1 && carry == 1) {
val[var[i] - 'A'] = 0;
}
else if (carry == 1) {
val[var[i] - 'A'] = 1;
carry = 0;
}
}

}

// this function prints truth table of a boolean expression - s
// for simplicity, each variable of the boolean expression is denoted by a uppercase alphabet
// the boolean expression should contain only 3 operators - " . " (AND), " + " (OR) and " ' " (NOT)
void print_truth_table(string s) {

vector<char> var;	// stores all variables that are present in bool expression s
vector<int> val(26, -1);	// stores value of each boolean variables
// value of boolean variable 'A' is stored at val[0]
// value of boolean variable 'B' is stored at val[1]
// ....
// value of boolean variable 'Z' is stored at val[25]
string postfix; // stores postfix form of s
int n;

for (int i = 0; i < s.length(); ++i) {

if (s[i] >= 'A' && s[i] <= 'Z' && val[s[i] - 'A'] == -1) {
val[s[i] - 'A'] = 0;
var.push_back(s[i]);
}

}

postfix = Expression::infix_to_postfix(s); // returns the postfix of s
n = var.size(); // number of variables in boolean expression

cout << "\nTRUTH TABLE FOR INPUT BOOLEAN EXPRESSION\n";

for (int i = 0; i < n; ++i) {
cout << "-----------";
}
cout << endl;

for (int i = 0; i < n; ++i) {
cout << var[i] << setw(10);
}
cout << "f" << endl;

for (int i = 0; i < pow(2, n); ++i) {

for (int i = 0; i < n; ++i) {
cout << val[var[i] - 'A'] << setw(10);
}
cout << Expression::evluate_postfix(postfix, val) << endl;
increment(var, val);

}

}

int main() {

string s;
cout << "Enter Boolean Expression: ";
cin >> s;

print_truth_table(s);

}
``````

Output

``````Enter Boolean Expression: A.B+B.C

TRUTH TABLE FOR INPUT BOOLEAN EXPRESSION
---------------------------------
A         B         C         f
0         0         0         0
0         0         1         0
0         1         0         0
0         1         1         1
1         0         0         0
1         0         1         0
1         1         0         1
1         1         1         1
``````
``````Enter Boolean Expression: A.B'+A'.C'+C.D

TRUTH TABLE FOR INPUT BOOLEAN EXPRESSION
--------------------------------------------
A         B         C         D         f
0         0         0         0         1
0         0         0         1         1
0         0         1         0         0
0         0         1         1         1
0         1         0         0         1
0         1         0         1         1
0         1         1         0         0
0         1         1         1         1
1         0         0         0         1
1         0         0         1         1
1         0         1         0         1
1         0         1         1         1
1         1         0         0         0
1         1         0         1         0
1         1         1         0         0
1         1         1         1         1``````