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<String>> mintermsBinary = new ArrayList <ArrayList<String>>();
- static ArrayList <String> primeImplicants = new ArrayList <String>();
- static ArrayList <ArrayList <ArrayList<String>>> comparisons = new ArrayList <ArrayList <ArrayList <String>>>();
- static Scanner in = new Scanner(System.in);
- private static void fillArrayList() {
- for(int i=0; i<8; i++) {
- mintermsBinary.add(new ArrayList());
- comparisons.add(new ArrayList()); //comparisons
- for(int j=0; j<8; j++)
- comparisons.get(i).add(new ArrayList()); // groups
- }
- }
- private static void decimalToBinary() {
- fillArrayList();
- 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<8-len; j++)
- res = "0" + res;
- mintermsBinary.get(ones).add(res);
- }
- 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<8-len; j++)
- res = "0" + res;
- mintermsBinary.get(ones).add(res);
- }
- for(int i=0; i<mintermsBinary.size(); i++)
- Collections.sort(mintermsBinary.get(i));
- }
- 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 handleInput() {
- for(int k=0; k<mintermsBinary.size()-2; k++) {
- if(mintermsBinary.get(k).isEmpty())
- continue;
- int l = k+1;
- while(l<mintermsBinary.size() && mintermsBinary.get(l).isEmpty())
- l++;
- if(l==mintermsBinary.size())
- return;
- for(int i=0; i<mintermsBinary.get(k).size(); i++) {
- boolean fPrime = true;
- for(int j=0; j<mintermsBinary.get(l).size(); j++) {
- String iBinary = mintermsBinary.get(k).get(i);
- String jBinary = mintermsBinary.get(l).get(j);
- int iDecimal = Integer.parseInt(iBinary, 2);
- int jDecimal = Integer.parseInt(jBinary, 2);
- int difference = jDecimal - iDecimal;
- float exponent = (float) (Math.log(difference) / Math.log(2));
- if(difference>0 && exponent - (int) exponent ==0) {
- fPrime = false;
- 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 m=0; m<comparisons.get(0).size(); m++) //groups
- for(int n=0; n<comparisons.get(0).get(m).size(); n++) { //implicants
- String duplicate = comparisons.get(0).get(m).get(n).split(" ")[0];
- if(duplicate.equals(differenceBinary))
- fDuplicate = true;
- }
- if(!fDuplicate) {
- comparisons.get(0).get(ones).add(differenceBinary + " " + iDecimal + " " + jDecimal);
- }
- }
- else
- continue;
- }
- if(fPrime) {
- String primeBinary = mintermsBinary.get(k).get(i);
- int primeDecimal = Integer.parseInt(primeBinary, 2);
- String info = primeBinary + " " + String.valueOf(primeDecimal);
- primeImplicants.add(info);
- }
- }
- }
- }
- private static void doComparisons() {
- int k;
- boolean fStop = false;
- for(k=0; k<comparisons.size()-2 && !fStop; k++) { //comparisons
- 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()) {
- fStop = true;
- break;
- }
- for(int i=0; i<comparisons.get(k).get(l).size(); i++) { //implicants
- 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);
- 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) {
- 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);
- }
- }
- 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);
- }
- decimalToBinary();
- handleInput();
- doComparisons();
- for(int i=0; i<comparisons.get(0).size(); i++) {
- for(int j=0; j<comparisons.get(0).get(i).size(); j++)
- System.out.println(comparisons.get(0).get(i).get(j));
- System.out.println();
- }
- for(int i=0; i<comparisons.get(1).size(); i++) {
- for(int j=0; j<comparisons.get(1).get(i).size(); j++)
- System.out.println(comparisons.get(1).get(i).get(j));
- System.out.println();
- }
- for(int i=0; i<primeImplicants.size(); i++) {
- System.out.println(primeImplicants.get(i));
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement