Display all True Boolean expression

This is an simple problem of mathematics. Our here given of some operands and operators, When combining operands and operators then this is produce an boolean value. Either true(1) or false(0) value. Our goal is to display possible combinations which is produce true (1) value.

Note that each expression will be contain all operators and operands. Here operand position are predefined but can be modified operator position. For example.

Example 1
char operand[] = "1101"; 
char operators[] = "|&^";

Output 
((( 1 | 1 ) & 0 ) ^ 1 )
((( 1 | 1 ) ^ 0 ) & 1 )
((( 1 & 1 ) ^ 0 ) | 1 )
((( 1 ^ 1 ) & 0 ) | 1 )

Example 2

char operand[] = "1001"; 
char operators[] = "|&^";

((( 1 | 0 ) & 0 ) ^ 1 )
((( 1 | 0 ) ^ 0 ) & 1 )
((( 1 & 0 ) | 0 ) ^ 1 )
((( 1 & 0 ) ^ 0 ) | 1 )
((( 1 ^ 0 ) & 0 ) | 1 )
((( 1 ^ 0 ) | 0 ) & 1 )

Example 3
char operand[] = "101"; 
char operators[] = "|&";
(( 1 | 0 ) & 1 )
(( 1 & 0 ) | 1 )


Example 4 

char operand[] = "01010"; 
char operators[] = "|&^>";
Output 
(((( 0 | 1 ) & 0 ) ^ 1 ) > 0 )
(((( 0 | 1 ) ^ 0 ) & 1 ) > 0 )
(((( 0 | 1 ) > 0 ) & 1 ) ^ 0 )
(((( 0 & 1 ) | 0 ) ^ 1 ) > 0 )
(((( 0 & 1 ) ^ 0 ) | 1 ) > 0 )
(((( 0 & 1 ) > 0 ) ^ 1 ) | 0 )
(((( 0 & 1 ) > 0 ) | 1 ) ^ 0 )
(((( 0 ^ 1 ) & 0 ) | 1 ) > 0 )
(((( 0 ^ 1 ) | 0 ) & 1 ) > 0 )
(((( 0 ^ 1 ) > 0 ) & 1 ) | 0 )
(((( 0 > 1 ) & 0 ) ^ 1 ) | 0 )
(((( 0 > 1 ) & 0 ) | 1 ) ^ 0 )

Example 5

char operand[] = "10100"; 
char operators[] = "|&^>";
Output 
(((( 1 | 0 ) & 1 ) ^ 0 ) > 0 )
(((( 1 | 0 ) & 1 ) > 0 ) ^ 0 )
(((( 1 & 0 ) | 1 ) ^ 0 ) > 0 )
(((( 1 & 0 ) | 1 ) > 0 ) ^ 0 )
(((( 1 & 0 ) ^ 1 ) | 0 ) > 0 )
(((( 1 & 0 ) ^ 1 ) > 0 ) | 0 )
(((( 1 ^ 0 ) & 1 ) | 0 ) > 0 )
(((( 1 ^ 0 ) & 1 ) > 0 ) | 0 )
(((( 1 > 0 ) & 1 ) ^ 0 ) | 0 )
(((( 1 > 0 ) & 1 ) | 0 ) ^ 0 )

Note that parenthesis is indicates execution of expression. You can write same expression in different ways. For example

0 | 1 & 0 ^ 1 > 0

(((( 0 | 1 ) & 0 ) ^ 1 ) > 0 ) = true
or
(((0 | 1 ) & 0 )  ^ ( 1  > 0 )) = true
or
(((0 | 1 ) & (( 0 ^ 1 ) > 0 ))) = true
or
(((0 | ((1  & 0 ) ^ ( 1  > 0 )))) = true
//more ...

In this situation pick any one result. Before solve this problem note that size of operand - 1 operator will used in given inputs. Mainly {^,>,<,|,&} operator are using in expression.

Here given code implementation process.

//C Program
//Display all True Boolean expression
#include<stdio.h>
//Swap element in array
void swap(char *str,int i,int j)
{
  char temp=str[i];
  str[i]=str[j];
  str[j]=temp;
}
//This method is execute an expression
//Using two operands and one operator and return its result
int operate(int a,char op,int b)
{
  //Assume (&^|><) operator are used
  switch(op)
  {
    case '&':
      return a & b;

    case '|':
      return a | b;


    case '^':
      return a ^ b;

    case '>':
      return a > b;

    case '<':
    return a < b;

  }
  //invalid operator

  return -1;
}

void brackets(int size)
{
  for (int i = 0; i <= size; ++i)
  {
    printf("(");
  }
}

//Find and Display true boolean expression
void expression(char operand[], char operators[],int s1 ,int s2 ,int k )
{
  if(k > s2)
  {
   return;
  }
  if(k==s2)
  {
    int size=0;

    int result=0;

    for (int i = 1; i < s1-1; ++i)
    {
     if(i==1)
     {  
        //Base case
        result = operate(operand[0]-'0',operators[size],operand[i]-'0');
    
        size++;
      }
      else
      {
        result = operate(result,operators[size],operand[i]-'0');
        
         size++;
      }
    }
    if(result == 1)
    {
        //Display valid expression


        size=0;

        //Add open bracket
        brackets(s1-3);
        
        for (int i = 1; i < s1-1; ++i)
        {
          if(i==1)
          {
            printf(" %c %c %c )", operand[0],operators[size],operand[i]);
            size++;
          }
          else
          {
            printf(" %c %c )", operators[size],operand[i]);
            size++;
          }
        }
      printf("\n");
    }
  }

  for (int i = k; i <= s2; ++i)
  {
    swap(operators,k,i);
    
    //recursive call   
    expression(operand, operators, s1, s2,k+1);

    //back to previous operator position
    swap(operators,k,i);
  }
}


int main()
{
  //operands
  char operand[] = "01010"; 

  int length = sizeof(operand) / sizeof(operand[0]); 

  char operators[] = "|&^>";

  int size = sizeof(operators) / sizeof(operators[0]);

  expression(operand, operators, length, size-2,0);

  return 0;
}

Output

(((( 0 | 1 ) & 0 ) ^ 1 ) > 0 )
(((( 0 | 1 ) ^ 0 ) & 1 ) > 0 )
(((( 0 | 1 ) > 0 ) & 1 ) ^ 0 )
(((( 0 & 1 ) | 0 ) ^ 1 ) > 0 )
(((( 0 & 1 ) ^ 0 ) | 1 ) > 0 )
(((( 0 & 1 ) > 0 ) ^ 1 ) | 0 )
(((( 0 & 1 ) > 0 ) | 1 ) ^ 0 )
(((( 0 ^ 1 ) & 0 ) | 1 ) > 0 )
(((( 0 ^ 1 ) | 0 ) & 1 ) > 0 )
(((( 0 ^ 1 ) > 0 ) & 1 ) | 0 )
(((( 0 > 1 ) & 0 ) ^ 1 ) | 0 )
(((( 0 > 1 ) & 0 ) | 1 ) ^ 0 )
//C++ Program 
//Display all True Boolean expression
#include <iostream>
#include <string.h>
using namespace std;

class MyString
{
  string operand;
  string operators;	
  public:
  	MyString(string,string);
    int operate(int,char,int);
    void brackets(int);
    void expression(int);
    void swap(int,int);
  
};
MyString :: MyString( string operand, string operators)
{
  this->operand = operand;
  this->operators = operators;
}
//This method is execute an expression
//Using two operands and one operator and return its result
int MyString:: operate(int a,char op,int b)
{
	
  //Assume (&^|><) operator are used
  switch(op)
  {
    case '&':
      return a & b;
    break;
    case '|':
      return a | b;
    break;

    case '^':
      return a ^ b;
    break;
    case '>':
      return a > b;
    break;
    case '<':
       return a < b;

  }
  //invalid operator

  return -1;
}
void MyString:: brackets(int size)
{
  for (int i = 0; i <= size; ++i)
  {
    cout<<"(";
  }
}
//Swapping two array elements by index
void MyString :: swap(int start,int end)
{
  char temp = operators[start];
  operators[start] = operators[end];
  operators[end] = temp;
}

//Find and Display true boolean expression
void MyString :: expression( int k )
{
  if(k > operators.length())
  {
   return;
  }
  if(k == operators.length()-1)
  {
  	
    int size=0;

    int result=0;

    for (int i = 1; i < operand.length(); ++i)
    {

     if(i==1)
     {  
     	
        //Base case
        result = operate( operand[0]-'0',operators[size],operand[1]-'0');
       
        size++;
      }
      else
      {
        result = operate(result,operators[size],operand[i]-'0');
        
        size++;
      }
      // cout<<" "<<result;
    }
    if(result == 1)
    {
        //Display valid expression


        size=0;

        //Add open bracket
        brackets(operand.length()-2);
        
        for (int i = 1; i < operand.length(); ++i)
        {
          if(i==1)
          {
           cout<<" "<< operand[0] << " "<<operators[size]<<" " <<operand[i]<<" )";
            size++;
          }
          else
          {
            cout<<" "<< operators[size] <<" " << operand[i]<<" )";
        
            size++;
          }
        }

     cout<<endl;
    }
  }

  for (int i = k; i < operators.length(); ++i)
  {
  	
    swap(k,i);
    
    //recursive call   
    expression(k+1);

    //back to previous operator position
    swap(k,i);
  }
}


int main(){
 
  //Create object
  MyString obj = MyString("01010","|&^>");
   
  obj.expression(0);


  return 0;
}

Output

(((( 0 | 1 ) & 0 ) ^ 1 ) > 0 )
(((( 0 | 1 ) ^ 0 ) & 1 ) > 0 )
(((( 0 | 1 ) > 0 ) & 1 ) ^ 0 )
(((( 0 & 1 ) | 0 ) ^ 1 ) > 0 )
(((( 0 & 1 ) ^ 0 ) | 1 ) > 0 )
(((( 0 & 1 ) > 0 ) ^ 1 ) | 0 )
(((( 0 & 1 ) > 0 ) | 1 ) ^ 0 )
(((( 0 ^ 1 ) & 0 ) | 1 ) > 0 )
(((( 0 ^ 1 ) | 0 ) & 1 ) > 0 )
(((( 0 ^ 1 ) > 0 ) & 1 ) | 0 )
(((( 0 > 1 ) & 0 ) ^ 1 ) | 0 )
(((( 0 > 1 ) & 0 ) | 1 ) ^ 0 )

//Java program
//Display all True Boolean expression
public class MyString
{
  
  private String operand;

  private String operators;

  MyString(String operand,String operators)
  {
    this.operators = operators;
    this.operand = operand;
  }
  public boolean operate(int a,char op,int b)
  {
    boolean a1=true,b1=true;

    if(a==0)
    {
      a1=false;
    }
    if(b==0)
    {
      b1=false;
    }

    //Assume (&^|><) operator are used
    switch(op)
    {
      case '&':

        return a1 & b1;

      case '|':

        return a1 | b1;

      case '^':

        return a1 ^ b1;

      case '>':

        return a > b;
   
      case '<':

         return a < b;

    }
    //invalid operator

    return false;
  }
  public void brackets(int size)
  {
    for (int i = 0; i <= size; ++i)
    {
      System.out.print("(");
    }
  }
  //Swapping two string elements by index
  public void swap(int start,int end)
  {
    char a = operators.charAt(start);

    char b = operators.charAt(end);

    operators = operators.substring(0, end) 
              + a 
              + operators.substring(end + 1);

      operators = operators.substring(0, start) 
              + b 
              + operators.substring(start + 1);
  }

  //Find and Display true boolean expression
  public void  expression( int k )
  {
    if(k > operators.length())
    {
     return;
    }
    if(k == operators.length()-1)
    {
      
      int size=0,b=0,a=0;

      boolean result=false;

      for (int i = 1; i < operand.length(); ++i)
      {

       if(i==1)
       {  
          b = 0;
          a = 0;
          if(operand.charAt(0) == '1')
          {
            a = 1;
          }
          if(operand.charAt(i) == '1')
          {
            b = 1;
          }
          //Base case
          result = operate(a,operators.charAt(size), b);
         
          size++;
        }
        else
        {
           b = 0;
           a = 0;
          if(operand.charAt(i) == '1')
          {
            b = 1;
          }
          if(result==true)
          {
            a = 1;
          }
          result = operate(a,operators.charAt(size),b);
          
          size++;
        }
        // cout<<" "<<result;
      }
      if(result == true)
      {
          //Display valid expression
          size=0;

          //Add open bracket
          brackets(operand.length()-2);
          
          for (int i = 1; i < operand.length(); ++i)
          {
            if(i==1)
            {
              
              System.out.print(" "+operand.charAt(0)+" " +operators.charAt(size)+ " " +operand.charAt(i)+" )");
              size++;
            }
            else
            {
              System.out.print(" "+operators.charAt(size)+ " " +operand.charAt(i)+ " )");
            
              size++;
            }
          }

       System.out.println();
      }
    }

    for (int i = k; i < operators.length(); ++i)
    {
      
      swap(k,i);
      
      //recursive call   
      expression(k+1);
  

      //back to previous operator position
      swap(k,i);
    }
  }
  public static void main(String[] args)
  {
     //Create object
  MyString obj = new MyString("01010","|&^>");
   
  obj.expression(0);
  }
}

Output

(((( 0 | 1 ) & 0 ) ^ 1 ) > 0 )
(((( 0 | 1 ) ^ 0 ) & 1 ) > 0 )
(((( 0 | 1 ) > 0 ) & 1 ) ^ 0 )
(((( 0 & 1 ) | 0 ) ^ 1 ) > 0 )
(((( 0 & 1 ) ^ 0 ) | 1 ) > 0 )
(((( 0 & 1 ) > 0 ) ^ 1 ) | 0 )
(((( 0 & 1 ) > 0 ) | 1 ) ^ 0 )
(((( 0 ^ 1 ) & 0 ) | 1 ) > 0 )
(((( 0 ^ 1 ) | 0 ) & 1 ) > 0 )
(((( 0 ^ 1 ) > 0 ) & 1 ) | 0 )
(((( 0 > 1 ) & 0 ) ^ 1 ) | 0 )
(((( 0 > 1 ) & 0 ) | 1 ) ^ 0 )
# Python Program
# Display all True Boolean expression
class MyString:

  def __init__(self, operand,operators):
    self.operators = operators
    self.operand = operand

  #Swapping two elements by index
  def swap(self,start,end):
   
   
    first = self.operators[start]
    second = self.operators[end]
    newtext =self.operators[0]

    if(start==0):
      newtext= second
    elif(second ==0):
      newtext = first  


    for i in range(1,len(self.operators)):
      if(i==start):

        newtext=newtext+second;

      elif(i==end):

        newtext=newtext+first;

      else:

        newtext = newtext + self.operators[i]

    self.operators = newtext

  def brackets(self, size):

    for value in range(0,size):
      print("(",end="")

  def operate(self, a, op, b):
   
    if(op=='&') :
    
      return a & b
   
    if(op=='^') :
    
      return a ^ b
    if(op=='|') :
    
      return a | b
    if(op=='>') :
    
      return a > b

    if(op=='<') :
    
      return a < b
        
  #Find and Display true boolean expression
  def  expression(self,k ):

    if(k > len(self.operators)):
     return
    
    if(k == len(self.operators)-1):
      size=0
      b=0
      a=0
      result=False

      for i in range(1,len(self.operand)):
        b = 0
        a = 0
        if(self.operand[i] == '1'):
          b = 1
        
        if(result == True):
          a = 1
        
        result = self.operate(a,self.operators[size], b)
         
        size+=1
        
       

      
      if(result == True):
        #Display valid expression
        size=0

        #Add open bracket
        self.brackets(len(self.operand)-1)
        
        for i in range(1,len(self.operand)):

          if(i==1):
            print(" "+self.operand[0]+" " +self.operators[size]+" "+self.operand[i]+ " )",end="")
            size+=1
          
          else :
            print(" "+self.operators[size]+ " " +self.operand[i]+ " )",end="")
            size+=1
        
        #new line
        print("")

      

    for x in range(k,len(self.operators)):
      
      self.swap(k,x)
      
      #recursive call   
      self.expression(k+1)
      #back to previous operator position
      self.swap(k,x)
    
def main():
  #Create object
  obj = MyString("01010","|&^>");
   
  obj.expression(0);
 

 
  
if __name__=="__main__":
  main()

Output

(((( 0 | 1 ) & 0 ) ^ 1 ) > 0 )
(((( 0 | 1 ) ^ 0 ) & 1 ) > 0 )
(((( 0 | 1 ) > 0 ) & 1 ) ^ 0 )
(((( 0 & 1 ) | 0 ) ^ 1 ) > 0 )
(((( 0 & 1 ) ^ 0 ) | 1 ) > 0 )
(((( 0 & 1 ) > 0 ) ^ 1 ) | 0 )
(((( 0 & 1 ) > 0 ) | 1 ) ^ 0 )
(((( 0 ^ 1 ) & 0 ) | 1 ) > 0 )
(((( 0 ^ 1 ) | 0 ) & 1 ) > 0 )
(((( 0 ^ 1 ) > 0 ) & 1 ) | 0 )
(((( 0 > 1 ) & 0 ) ^ 1 ) | 0 )
(((( 0 > 1 ) & 0 ) | 1 ) ^ 0 )

//C# Program
//Display all True Boolean expression
using System;

public class MyString
{
	public String operand;

	public String operators;

	MyString(String operand,String operators)
	{
		this.operators = operators;
		this.operand = operand;
	}
	public Boolean operate(int a,char op,int b)
	{
		Boolean a1=true,b1=true;

		if(a==0)
		{
			a1=false;
		}
		if(b==0)
		{
			b1=false;
		}

		//Assume (&^|><) operator are used
		switch(op)
		{
		case '&':

			return a1 & b1;

		case '|':

			return a1 | b1;

		case '^':

			return a1 ^ b1;

		case '>':

			return a > b;

		case '<':

			return a < b;

		}
		//invalid operator

		return false;
	}
	public void brackets(int size)
	{
		for (int i = 0; i <= size; ++i)
		{
			Console.Write("(");
		}
	}
	//Swapping two string elements by index
	public void swap(int start,int end)
	{
		if(start > operators.Length || end  > operators.Length || start == end )
		{
			return;
		}
		char a = operators[start];

		char[] ch = operators.ToCharArray();
		ch[start] = operators[end]; 
		ch[end] = a; 
		operators = new string (ch);
	}

	//Find and Display true boolean expression
	public void expression( int k )
	{

		if(k > operators.Length)
		{
			return;
		}

		if(k == operators.Length-1)
		{

			int size=0,b=0,a=0;

			Boolean result=false;

			for (int i = 1; i < operand.Length; ++i)
			{
				b = 0;
				a = 0;
				if(operand[i] == '1')
				{
					b = 1;
				}
				if(result==true)
				{
					a = 1;
				}
				result = operate(a,operators[size], b);

				size++;

			}
			if(result == true)
			{
				//Display valid expression
				size=0;

				//Add open bracket
				brackets(operand.Length-2);

				for (int j = 1; j < operand.Length; ++j)
				{
					if(j==1)
					{
						Console.Write(" {0} {1} {2} )", operand[0],operators[size],operand[j]);
						size++;
					}
					else
					{
						Console.Write(" {0} {1} )", operators[size],operand[j]);
						size++;
					}
				}

				Console.Write("\n");
			}
		}


		for (int i = k; i < operators.Length; ++i)
		{

			swap(k,i);
		
			//recursive call   
			expression(k+1);


			//back to previous operator position
			swap(k,i);
		}
	}

	public static void Main(String[] args) {

		//Create object
		MyString obj = new MyString("01010","|&^>");

	    obj.expression(0);

	}
}

Output

(((( 0 | 1 ) & 0 ) ^ 1 ) > 0 )
(((( 0 | 1 ) ^ 0 ) & 1 ) > 0 )
(((( 0 | 1 ) > 0 ) & 1 ) ^ 0 )
(((( 0 & 1 ) | 0 ) ^ 1 ) > 0 )
(((( 0 & 1 ) ^ 0 ) | 1 ) > 0 )
(((( 0 & 1 ) > 0 ) ^ 1 ) | 0 )
(((( 0 & 1 ) > 0 ) | 1 ) ^ 0 )
(((( 0 ^ 1 ) & 0 ) | 1 ) > 0 )
(((( 0 ^ 1 ) | 0 ) & 1 ) > 0 )
(((( 0 ^ 1 ) > 0 ) & 1 ) | 0 )
(((( 0 > 1 ) & 0 ) ^ 1 ) | 0 )
(((( 0 > 1 ) & 0 ) | 1 ) ^ 0 )

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved