Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- import java.util.*;
- public class Solver {
- static ArrayList <Integer> minterms = new ArrayList <Integer>();
- static ArrayList <Integer> dontcares = new ArrayList <Integer>();
- static ArrayList <ArrayList <ArrayList<String>>> comparisons = new ArrayList <ArrayList <ArrayList <String>>>();
- static ArrayList <String> primeImplicants = new ArrayList <String>();
- static String [] combination = new String[26];
- static int MaxnumberOf_Vars;
- static boolean foundCombination = false;
- static Scanner in = new Scanner(System.in);
- private static void fillArrayList() {
- for(int i=0; i<26; i++) {
- comparisons.add(new ArrayList()); //comparisons
- for(int j=0; j<=MaxnumberOf_Vars; j++)
- comparisons.get(i).add(new ArrayList()); // groups
- }
- }
- private static int find_numOfvars()
- {
- int maxMinterm = 0,maxDontCare=0;
- if (minterms.isEmpty()==false)
- maxMinterm = Collections.max(minterms);
- if (dontcares.isEmpty()==false)
- maxDontCare = Collections.max(dontcares);
- int maxImplicant = Math.max(maxDontCare, maxMinterm);
- String binary = Integer.toBinaryString(maxImplicant);
- return binary.length();
- }
- private static String differBinary(String firstMinterm, String secondMinterm) {
- String result = "";
- int ones=0;
- for(int i=0; i<firstMinterm.length(); i++) {
- if(firstMinterm.charAt(i) != secondMinterm.charAt(i))
- result += "-";
- else
- result += firstMinterm.charAt(i);
- if(firstMinterm.charAt(i)=='1')
- ones++;
- }
- return result + " " + String.valueOf(ones);
- }
- private static void decimalToBinary() {
- for(int i=0; i<minterms.size(); i++) {
- int div = minterms.get(i), ones = 0;
- String res= "";
- while(div!=0) {
- if(div%2==1) {
- ones++;
- res = "1" + res;
- }
- else
- res = "0" + res;
- div/=2;
- }
- for(int j=0, len = res.length(); j<MaxnumberOf_Vars-len; j++)
- res = "0" + res;
- comparisons.get(0).get(ones).add(res + " " + Integer.parseInt(res,2));
- }
- for(int i=0; i<dontcares.size();i++) {
- int div = dontcares.get(i), ones = 0;
- String res = "";
- while(div!=0) {
- if(div%2==1) {
- ones++;
- res = "1" + res;
- }
- else
- res = "0" + res;
- div/=2;
- }
- for(int j=0, len = res.length(); j<MaxnumberOf_Vars-len; j++)
- res = "0" + res;
- comparisons.get(0).get(ones).add(res + " " + Integer.parseInt(res,2));
- }
- for(int i=0; i< comparisons.get(0).size(); i++)
- Collections.sort(comparisons.get(0).get(i));
- }
- private static void doComparisons() {
- int k;
- for(k=0; k<comparisons.size()-1; k++) { //comparisons
- boolean[][] takenToNextComparison = new boolean[10][100];
- for(int l=0; l<comparisons.get(k).size(); l++) { //groups
- if(comparisons.get(k).get(l).isEmpty())
- continue;
- int m = l+1;
- while(m< comparisons.get(k).size() && comparisons.get(k).get(m).isEmpty())
- m++;
- if(m==comparisons.get(k).size()) {
- for(int i=0; i< comparisons.get(k).get(l).size(); i++) {
- if(!takenToNextComparison[l][i]) {
- ArrayList <String> iData = new ArrayList <String>();
- for(String retval: comparisons.get(k).get(l).get(i).split(" "))
- iData.add(retval);
- String info = iData.get(0);
- for(int x=1; x<iData.size(); x++)
- info += " " + iData.get(x);
- primeImplicants.add(info);
- }
- }
- break;
- }
- for(int i=0; i<comparisons.get(k).get(l).size(); i++) {
- boolean fPrime = true;
- ArrayList <String> iData = new ArrayList <String>();
- for(String retval: comparisons.get(k).get(l).get(i).split(" "))
- iData.add(retval);
- for(int j=0; j<comparisons.get(k).get(m).size(); j++) {
- ArrayList <String> jData = new ArrayList <String>();
- for(String retval: comparisons.get(k).get(m).get(j).split(" "))
- jData.add(retval);
- float exponent = 0;
- int difference = 0;
- boolean fAccept = true;
- for(int x=1; x<iData.size(); x++) {
- int iDifference = Integer.parseInt(iData.get(x));
- int jDifference = Integer.parseInt(jData.get(x));
- int tempDifference = jDifference - iDifference;
- float tempExponent = (float) (Math.log(tempDifference) / Math.log(2));
- if(x==1) {
- difference = tempDifference;
- exponent = tempExponent;
- if(difference<0 || exponent - (int) exponent!=0) {
- fAccept = false;
- break;
- }
- }
- else {
- if(tempDifference!=difference || tempExponent!=exponent) {
- fAccept = false;
- break;
- }
- }
- }
- if(fAccept) {
- fPrime = false;
- String iBinary = iData.get(0);
- String jBinary = jData.get(0);
- takenToNextComparison[l][i] = true;
- takenToNextComparison[m][j] = true;
- ArrayList <String> dashesAndOnes = new ArrayList <String>();
- for( String retval: differBinary(iBinary, jBinary).split(" "))
- dashesAndOnes.add(retval);
- String differenceBinary = dashesAndOnes.get(0);
- int ones = Integer.parseInt(dashesAndOnes.get(1));
- boolean fDuplicate = false;
- for(int x=0; x<comparisons.get(k+1).size(); x++) {
- for(int y=0; y<comparisons.get(k+1).get(x).size(); y++) {
- String duplicate = comparisons.get(k+1).get(x).get(y).split(" ")[0];
- if(duplicate.equals(differenceBinary)) {
- fDuplicate = true;
- break;
- }
- }
- }
- if(!fDuplicate) {
- String info = differenceBinary;
- for(int x=1; x< iData.size(); x++) {
- info += " " + iData.get(x);
- }
- for(int x=1; x< jData.size(); x++) {
- info += " " + jData.get(x);
- }
- comparisons.get(k+1).get(ones).add(info);
- }
- else
- continue;
- }
- }
- if(fPrime && !takenToNextComparison[l][i]) {
- String info = iData.get(0);
- for(int x=1; x<iData.size(); x++)
- info += " " + iData.get(x);
- primeImplicants.add(info);
- }
- }
- }
- }
- for(int i=0; i<comparisons.get(k).size(); i++) //groups
- for(int j=0; j<comparisons.get(k).get(i).size(); j++) {
- ArrayList <String> data = new ArrayList <String>();
- for(String retval: comparisons.get(k).get(i).get(j).split(" "))
- data.add(retval);
- String info = data.get(0);
- for(int x=1; x<data.size(); x++)
- info += " " + data.get(x);
- primeImplicants.add(info);
- }
- }
- private static String find_Expression(ArrayList a)
- {
- String expression = new String ();
- ;
- StringBuilder Dashes_expression = null;
- StringBuilder expression_Builder = new StringBuilder();
- ///I want to know the maximum estimated number of variables;
- for (int i=0 ; i<a.size() ; i++ )
- {
- for( String retval: ((String) a.get(i)).split(" ")){
- Dashes_expression = new StringBuilder();
- Dashes_expression.append(retval);
- break;
- }
- for (int j=0 ; j < Dashes_expression.length();j++)
- {
- if (Dashes_expression.charAt(j)=='1')
- {
- char character = (char) ((int)('A')+j);
- expression_Builder.append(character);
- }
- else if (Dashes_expression.charAt(j)=='0')
- {
- char character = (char) ((int)('A')+j);
- String str = new String();
- str += character + "'";
- expression_Builder.append(str);
- }
- }
- if (i!=(a.size()-1))
- expression_Builder.append(" + ");
- }
- expression = expression_Builder.toString();
- return expression;
- }
- private static boolean checkCombination(int len) {
- ArrayList<Integer> checkedMinterms = new ArrayList<Integer>();
- for(int i=0; i<len; i++) {
- ArrayList <String> data = new ArrayList <String>();
- for(String retval: combination[i].split(" " ))
- data.add(retval);
- for(int j=1; j<data.size(); j++)
- checkedMinterms.add(Integer.parseInt(data.get(j)));
- }
- if(checkedMinterms.containsAll(minterms))
- return true;
- else
- return false;
- }
- private static void generateCombinations(int element, int m, int len) { //(1,0,size)
- if(m == len) {
- if(checkCombination(len)) {
- foundCombination = true;
- fillEssentialPrime(len);
- Arrays.fill(combination, "");
- }
- return;
- }
- if(element== primeImplicants.size()+1)
- return;
- combination[m] = primeImplicants.get(element-1);
- generateCombinations(element+1, m+1, len);
- generateCombinations(element+1, m, len);
- }
- private static void fillEssentialPrime(int numberOfEssential) {
- ArrayList<String> essential = new ArrayList<String>();
- for(int i=0; i< numberOfEssential; i++ ) {
- System.out.println(combination[i]);
- essential.add(combination[i]);
- }
- System.out.println();
- System.out.println(find_Expression(essential));
- }
- public static void main (String[] args) {
- System.out.println("Enter the minterms in decimal <-1 to finish>:");
- while(true) {
- int input;
- input = in.nextInt();
- if(input==-1)
- break;
- minterms.add(input);
- }
- System.out.println("Enter the dontcares in decimal <-1 to finish>:");
- while(true) {
- int input;
- input = in.nextInt();
- if(input==-1)
- break;
- dontcares.add(input);
- }
- MaxnumberOf_Vars = find_numOfvars();
- fillArrayList();
- decimalToBinary();
- doComparisons();
- for(int k=0; k<comparisons.size(); k++) {
- boolean comparisonHasElements = false;
- for(int i=0; i<comparisons.get(k).size(); i++) {
- if(comparisons.get(k).get(i).isEmpty())
- continue;
- for(int j=0; j<comparisons.get(k).get(i).size(); j++) {
- System.out.println(comparisons.get(k).get(i).get(j));
- }
- comparisonHasElements = true;
- System.out.println("-----------------");
- }
- if(comparisonHasElements) {
- System.out.println("______________________________________________________");
- System.out.println();
- }
- }
- System.out.println("Prime Implicants:");
- for(int i=0; i<primeImplicants.size(); i++) {
- System.out.println(primeImplicants.get(i));
- }
- System.out.println();
- System.out.println(find_Expression(primeImplicants));
- System.out.println();
- System.out.println();
- System.out.println("Essential Prime Implicants:");
- for(int i=1; i<=primeImplicants.size() && !foundCombination; i++) {
- generateCombinations(1 , 0, i);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement