API tools faq
paste
Advertisement
anas_harby

Untitled

anas_harby
May 2nd, 2016
54
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 18.85 KB | None | 0 0
raw download clone embed print report
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Collections;
  4. import java.util.Scanner;
  5.  
  6. /**
  7.  * The Class QM Solver.
  8.  */
  9. public class Solver {
  10.  
  11.     /** The minterms (Decimal integers). */
  12.     static ArrayList<Integer> minterms = new ArrayList<Integer>();
  13.    
  14.     /** The dontcares (Decimal integers). */
  15.     static ArrayList<Integer> dontcares = new ArrayList<Integer>();
  16.    
  17.     /** The comparisons (3D arrayList, 1st Dimension holds comparison, 2nd holds groups
  18.      * ,3rd holds binary representation alongside the minterms it fulfills, e.x: 0--1 1 3 5 7).
  19.      * . */
  20.     static ArrayList<ArrayList<ArrayList<String>>> comparisons = new ArrayList<ArrayList<ArrayList<String>>>();
  21.    
  22.     /** The essential prime implicants. (same representation as the above) */
  23.     static ArrayList<String> essentialPrimeImplicantsContainingOne = new ArrayList<String>();
  24.    
  25.     /** The minterms apperancescount */
  26.     static int[][] mintermsApperancescount;
  27.    
  28.     /** The prime implicants (taken before coverage table). */
  29.     static ArrayList<String> primeImplicants = new ArrayList<String>();
  30.  
  31.     /** The combination (combination of terms generated in coverage table). */
  32.     static String[] combination = new String[26];
  33.  
  34.     /** number of variables/bits needed to represent each minterm. */
  35.     static int numberOfBits;
  36.    
  37.     /** checks if generateCombinations() method has found a suitable combination. */
  38.     static boolean foundCombination = false;
  39.  
  40.     /** The scanner. */
  41.     static Scanner in = new Scanner(System.in);
  42.  
  43.     /**
  44.      * Pre-fills array lists with empty data to enable accessing it with random indexes.
  45.      */
  46.     private static void fillArrayList() {
  47.         for (int i = 0; i < 26; i++) {
  48.             comparisons.add(new ArrayList()); // comparisons
  49.             for (int j = 0; j <= numberOfBits; j++)
  50.                 comparisons.get(i).add(new ArrayList()); // groups
  51.         }
  52.     }
  53.  
  54.     /**
  55.      * Differ binary.
  56.      *
  57.      * @param firstMinterm the first minterm in a binary string representation.
  58.      * @param secondMinterm the second minterm in a binary string representations.
  59.      * @return a string in a binary representation with difference represented as dashes. returns the number of ones in the end of the string.
  60.      */
  61.     private static String differBinary(String firstMinterm, String secondMinterm) {
  62.         String result = "";
  63.         int ones = 0;
  64.         for (int i = 0; i < firstMinterm.length(); i++) {
  65.             if (firstMinterm.charAt(i) != secondMinterm.charAt(i))
  66.                 result += "-";
  67.             else
  68.                 result += firstMinterm.charAt(i);
  69.             if (firstMinterm.charAt(i) == '1')
  70.                 ones++;
  71.         }
  72.         return result + " " + String.valueOf(ones);
  73.     }
  74.  
  75.     /**
  76.      * Converter from decimal to binary (needed to count ones, adds result immediately in the first comparison --> comparisons[0]).
  77.      */
  78.     private static void decimalToBinary() {
  79.  
  80.         for (int i = 0; i < minterms.size(); i++) {
  81.             int div = minterms.get(i), ones = 0;
  82.             String res = "";
  83.             while (div != 0) {
  84.                 if (div % 2 == 1) {
  85.                     ones++;
  86.                     res = "1" + res;
  87.                 } else
  88.                     res = "0" + res;
  89.                 div /= 2;
  90.             }
  91.             for (int j = 0, len = res.length(); j < numberOfBits - len; j++)
  92.                 res = "0" + res;
  93.             comparisons.get(0).get(ones).add(res + " " + Integer.parseInt(res, 2));
  94.         }
  95.         for (int i = 0; i < dontcares.size(); i++) {
  96.             int div = dontcares.get(i), ones = 0;
  97.             String res = "";
  98.             while (div != 0) {
  99.                 if (div % 2 == 1) {
  100.                     ones++;
  101.                     res = "1" + res;
  102.                 } else
  103.                     res = "0" + res;
  104.                 div /= 2;
  105.             }
  106.             for (int j = 0, len = res.length(); j < numberOfBits - len; j++)
  107.                 res = "0" + res;
  108.             comparisons.get(0).get(ones).add(res + " " + Integer.parseInt(res, 2));
  109.         }
  110.         for (int i = 0; i < comparisons.get(0).size(); i++)
  111.             Collections.sort(comparisons.get(0).get(i));
  112.     }
  113.  
  114.     /**
  115.      * Do comparisons.
  116.      */
  117.     private static void doComparisons() {
  118.         int k;
  119.         for (k = 0; k < comparisons.size() - 1; k++) { // Loop through comparisons
  120.             boolean[][] takenToNextComparison = new boolean[10][100];
  121.             for (int l = 0; l < comparisons.get(k).size(); l++) { // Loop through groups
  122.                 if (comparisons.get(k).get(l).isEmpty()) //continue if group is empty.
  123.                     continue;
  124.                 int m = l + 1;
  125.  
  126.                 while (m < comparisons.get(k).size() && comparisons.get(k).get(m).isEmpty()) //find a next group that isn't empty.
  127.                     m++;
  128.                 if (m == comparisons.get(k).size()) { //if this is the last group, add terms that were not taken before into the prime implicants.
  129.                     for (int i = 0; i < comparisons.get(k).get(l).size(); i++) {
  130.                         if (!takenToNextComparison[l][i]) {
  131.                             ArrayList<String> iData = new ArrayList<String>();
  132.                             for (String retval : comparisons.get(k).get(l).get(i).split(" "))
  133.                                 iData.add(retval);
  134.                             String info = iData.get(0);
  135.                             for (int x = 1; x < iData.size(); x++)
  136.                                 info += " " + iData.get(x);
  137.                             primeImplicants.add(info);
  138.                         }
  139.                     }
  140.                     break;
  141.                 }
  142.                 for (int i = 0; i < comparisons.get(k).get(l).size(); i++) {
  143.                     boolean fPrime = true;
  144.                     ArrayList<String> iData = new ArrayList<String>();
  145.                     for (String retval : comparisons.get(k).get(l).get(i).split(" ")) //get data inside comparisons arraylist for the 1st term.
  146.                         iData.add(retval);
  147.                     for (int j = 0; j < comparisons.get(k).get(m).size(); j++) {
  148.                         ArrayList<String> jData = new ArrayList<String>();
  149.                         for (String retval : comparisons.get(k).get(m).get(j).split(" "))
  150.                             jData.add(retval);
  151.                         float exponent = 0;
  152.                         int difference = 0;
  153.                         boolean fAccept = true;
  154.                         for (int x = 1; x < iData.size(); x++) {
  155.                             int iDifference = Integer.parseInt(iData.get(x));
  156.                             int jDifference = Integer.parseInt(jData.get(x));
  157.                             int tempDifference = jDifference - iDifference;
  158.                             float tempExponent = (float) (Math.log(tempDifference) / Math.log(2)); //difference between the two is 2^n.
  159.                             if (x == 1) {
  160.                                 difference = tempDifference;
  161.                                 exponent = tempExponent;
  162.                                 if (difference < 0 || exponent - (int) exponent != 0) {
  163.                                     fAccept = false;
  164.                                     break;
  165.                                 }
  166.                             } else {
  167.                                 if (tempDifference != difference || tempExponent != exponent) {
  168.                                     fAccept = false;
  169.                                     break;
  170.                                 }
  171.                             }
  172.                         }
  173.                         if (fAccept) {
  174.                             fPrime = false;
  175.                             String iBinary = iData.get(0);
  176.                             String jBinary = jData.get(0);
  177.                             takenToNextComparison[l][i] = true; //the implicant is taken.
  178.                             takenToNextComparison[m][j] = true;
  179.                             ArrayList<String> dashesAndOnes = new ArrayList<String>();
  180.                             for (String retval : differBinary(iBinary, jBinary).split(" "))
  181.                                 dashesAndOnes.add(retval);
  182.                             String differenceBinary = dashesAndOnes.get(0);
  183.                             int ones = Integer.parseInt(dashesAndOnes.get(1));
  184.                             boolean fDuplicate = false;
  185.                             for (int x = 0; x < comparisons.get(k + 1).size(); x++) { //checks for duplicates.
  186.                                 for (int y = 0; y < comparisons.get(k + 1).get(x).size(); y++) {
  187.                                     String duplicate = comparisons.get(k + 1).get(x).get(y).split(" ")[0];
  188.                                     if (duplicate.equals(differenceBinary)) {
  189.                                         fDuplicate = true;
  190.                                         break;
  191.                                     }
  192.                                 }
  193.                             }
  194.                             if (!fDuplicate) {
  195.                                 String info = differenceBinary; //assign data for the next comparison.
  196.                                 for (int x = 1; x < iData.size(); x++) {
  197.                                     info += " " + iData.get(x);
  198.                                 }
  199.                                 for (int x = 1; x < jData.size(); x++) {
  200.                                     info += " " + jData.get(x);
  201.                                 }
  202.                                 comparisons.get(k + 1).get(ones).add(info);
  203.                             } else
  204.                                 continue;
  205.  
  206.                         }
  207.                     }
  208.                     if (fPrime && !takenToNextComparison[l][i]) { //add to prime implicants.
  209.                         String info = iData.get(0);
  210.                         for (int x = 1; x < iData.size(); x++)
  211.                             info += " " + iData.get(x);
  212.                         primeImplicants.add(info);
  213.                     }
  214.  
  215.                 }
  216.             }
  217.         }
  218.         for (int i = 0; i < comparisons.get(k).size(); i++) // add all the implicants in the last comparison to prime implicants.
  219.             for (int j = 0; j < comparisons.get(k).get(i).size(); j++) {
  220.                 ArrayList<String> data = new ArrayList<String>();
  221.                 for (String retval : comparisons.get(k).get(i).get(j).split(" "))
  222.                     data.add(retval);
  223.                 String info = data.get(0);
  224.                 for (int x = 1; x < data.size(); x++)
  225.                     info += " " + data.get(x);
  226.                 primeImplicants.add(info);
  227.             }
  228.     }
  229.  
  230.     /**
  231.      * Returns an alphabetical representation of a binary number with dashes.
  232.      *
  233.      * @param arrayList required
  234.      * @return string expression
  235.      */
  236.     private static String findExpression(ArrayList required) {
  237.         String expression = new String();
  238.         ;
  239.         StringBuilder dashesExpression = null;
  240.         StringBuilder expressionBuilder = new StringBuilder();
  241.  
  242.         for (int i = 0; i < required.size(); i++) {
  243.             for (String retval : ((String) required.get(i)).split(" ")) {
  244.                 dashesExpression = new StringBuilder();
  245.                 dashesExpression.append(retval);
  246.                 break;
  247.             }
  248.  
  249.             for (int j = 0; j < dashesExpression.length(); j++) {
  250.                 if (dashesExpression.charAt(j) == '1') {
  251.                     char character = (char) ((int) ('A') + j);
  252.                     expressionBuilder.append(character);
  253.                 } else if (dashesExpression.charAt(j) == '0') {
  254.                     char character = (char) ((int) ('A') + j);
  255.                     String str = new String();
  256.                     str += character + "'";
  257.                     expressionBuilder.append(str);
  258.  
  259.                 }
  260.  
  261.             }
  262.             if (i != (required.size() - 1))
  263.                 expressionBuilder.append(" + ");
  264.         }
  265.  
  266.         expression = expressionBuilder.toString();
  267.         return expression;
  268.     }
  269.    
  270.     /**
  271.      * Checks whether shifting to getting reduced prime implicants entering the combinations generating process is needed or not.
  272.      *
  273.      * @return true, if successful
  274.      */
  275.     private static boolean containsOne() {
  276.         for (int i = 0; i < mintermsApperancescount.length; i++) {
  277.             if ((mintermsApperancescount[i][1]) == 1)
  278.                 return true;
  279.         }
  280.         return false;
  281.     }
  282.  
  283.     /**
  284.      * Counts the appearances of each minterm in each combined group.
  285.      * NOTE:  Combined groups arise from the method doComparisons()
  286.      */
  287.     private static void countAppearances() {
  288.         StringBuilder str2;
  289.         int foundFlag = 0;
  290.         mintermsApperancescount = new int[minterms.size()][2];
  291.         for (int i = 0; i < minterms.size(); i++) {
  292.             mintermsApperancescount[i][0] = minterms.get(i);
  293.  
  294.         }
  295.         for (int i = 0; i < primeImplicants.size(); i++) {
  296.             String str = primeImplicants.get(i).split(" ", 2)[1];
  297.             str2 = new StringBuilder();
  298.             for (int j = 0; j <= str.length(); j++) {
  299.                 foundFlag = 0;
  300.                 if ((j != str.length()) && (str.charAt(j) != ' ')) {
  301.                     str2.append(str.charAt(j));
  302.  
  303.                 } else {
  304.                     int vaL = Integer.parseInt(str2.toString());
  305.                     for (int k = 0; k < mintermsApperancescount.length; k++) {
  306.                         if (vaL == mintermsApperancescount[k][0]) {
  307.                             foundFlag = 1;
  308.                             mintermsApperancescount[k][1]++;
  309.                             str2 = new StringBuilder();
  310.                             break;
  311.  
  312.                         }
  313.                     }
  314.                     if (foundFlag == 0)
  315.                         str2 = new StringBuilder();
  316.  
  317.                 }
  318.             }
  319.         }
  320.  
  321.     }
  322.  
  323.  
  324.  
  325.     /**
  326.      * Finds minterms that appeared only once in a certain column and gets a corresponding expreesion using an array.
  327.      * Removes each minterm taken from consideration as they're not needed in the next step in the combination generating.
  328.      */
  329.     private static void getReducedEssentialImplicants() {
  330.         int uniqueMinterm, foundFlag = 0;
  331.         StringBuilder str2;
  332.  
  333.         for (int i = 0; i < mintermsApperancescount.length; i++) {
  334.             if (mintermsApperancescount[i][1] == 1) {
  335.                 uniqueMinterm = mintermsApperancescount[i][0];
  336.                 for (int j = 0; j < primeImplicants.size(); j++) {
  337.                     String str = primeImplicants.get(j).split(" ", 2)[1];
  338.                     str2 = new StringBuilder();
  339.                     for (int k = 0; k <= str.length(); k++) {
  340.                         if ((k != str.length()) && (str.charAt(k) != ' ')) {
  341.                             str2.append(str.charAt(k));
  342.  
  343.                         } else if (((k != str.length()) && (str.charAt(k) == ' ')) || (k == (str.length()))) {
  344.                             int value = Integer.parseInt(str2.toString());
  345.                             if (value == uniqueMinterm) {
  346.                                 essentialPrimeImplicantsContainingOne.add(primeImplicants.get(j));
  347.                                 /*
  348.                                  * the implicant that matches certain conditions should be
  349.                                  * promoted to be essential and removed from the prime implicants arraylist.
  350.                                  */
  351.                                 primeImplicants.remove(j);
  352.                                 str2 = new StringBuilder();
  353.                                 for (int u = 0; u <= str.length(); u++) {
  354.                                     foundFlag = 0;
  355.                                     if ((u != str.length()) && (str.charAt(u) != ' ')) {
  356.                                         str2.append(str.charAt(u));
  357.  
  358.                                     } else {
  359.                                         int vaL = Integer.parseInt(str2.toString());
  360.                                         for (int m = 0; m < mintermsApperancescount.length; m++) {
  361.                                             if (vaL == mintermsApperancescount[m][0]) {
  362.                                                 foundFlag = 1;
  363.                                                 mintermsApperancescount[m][1] = 0;
  364.                                                 /*
  365.                                                  * Cancels out all the minterms in the row and the columns
  366.                                                  * that matches the taken row "expression".
  367.                                                  */
  368.                                                 str2 = new StringBuilder();
  369.                                                 ;
  370.                                                 break;
  371.  
  372.                                             }
  373.                                         }
  374.                                         if (foundFlag == 0)
  375.                                             str2 = new StringBuilder();
  376.  
  377.                                     }
  378.  
  379.                                 }
  380.                             } else {
  381.                                 str2 = new StringBuilder();
  382.                             }
  383.                         }
  384.                     }
  385.                 }
  386.             }
  387.         }
  388.  
  389.     }
  390.    
  391.     /**
  392.      * Checks whether the essential prime implicants already covered all the minterms before trying to generate combinations.
  393.      *
  394.      * @return true, if successful
  395.      */
  396.     private static boolean needsCombinations() {
  397.         int countZeros = 0;
  398.  
  399.         for (int i = 0; i < mintermsApperancescount.length; i++) {
  400.             if (mintermsApperancescount[i][1] == 0) {
  401.                 for (int j = 0; j < minterms.size(); j++) {
  402.                     if (mintermsApperancescount[i][0] == minterms.get(j)) {
  403.                         minterms.remove(j);
  404.                         break;
  405.                     }
  406.  
  407.                 }
  408.                 countZeros++;
  409.             }
  410.         }
  411.         if (countZeros == mintermsApperancescount.length) {  
  412.             /*
  413.             if all the terms have the zero value in appearance cell therefore
  414.             it's not needed to proceed to another level of computations using the combinations generator
  415.             as it's already done.
  416.            */
  417.             return true;
  418.         } else
  419.             return false;
  420.     }
  421.  
  422.     /**
  423.      * Check combination.
  424.      *
  425.      * @param len length of the combination.
  426.      * @return true, if combination covered all the remaining minterms.
  427.      */
  428.     private static boolean checkCombination(int len) {
  429.         ArrayList<Integer> checkedMinterms = new ArrayList<Integer>();
  430.  
  431.         for (int i = 0; i < len; i++) {
  432.             ArrayList<String> data = new ArrayList<String>();
  433.             for (String retval : combination[i].split(" "))
  434.                 data.add(retval);
  435.             for (int j = 1; j < data.size(); j++)
  436.                 checkedMinterms.add(Integer.parseInt(data.get(j)));
  437.         }
  438.         if (checkedMinterms.containsAll(minterms))
  439.             return true;
  440.         else
  441.             return false;
  442.     }
  443.    
  444.     /**
  445.      * Generate combinations.
  446.      *
  447.      * @param element the element
  448.      * @param m the m
  449.      * @param len the len
  450.      */
  451.     private static void generateCombinations(int element, int m, int len) { // (1,0,size)
  452.         if (m == len) {
  453.             if (checkCombination(len)) {
  454.                 foundCombination = true;
  455.                 fillEssentialPrime(len);
  456.                 Arrays.fill(combination, "");
  457.             }
  458.             return;
  459.         }
  460.         if (element == primeImplicants.size() + 1)
  461.             return;
  462.         combination[m] = primeImplicants.get(element - 1);
  463.         generateCombinations(element + 1, m + 1, len);
  464.         generateCombinations(element + 1, m, len);
  465.     }
  466.  
  467.     /**
  468.      * Takes the combination and adds it to a local list (since a global one won't be needed taken into consideration the probability of
  469.      * getting more than one minimal expression). prints the implicants immediately.
  470.      * Prints the essential prime implicants immediately.
  471.      * Generates an alphabetical expression and prints it.
  472.      * NOTE: (if needed to separate the printing process, a new 2D array list can be added globally and with a proper string representation
  473.      *        minimal expressions can be added, ex: ( 1 >> [BC' + AB' + ABC', 1 2, 4 5, 3 5 6, ...etc] ) and dealt with later with split()  
  474.      * @param combinationLength the number of essential prime implicants inside combination.
  475.      */
  476.     private static void fillEssentialPrime(int combinationLength) {
  477.         ArrayList<String> combinationEssential = new ArrayList<String>();
  478.         for (int i = 0; i < combinationLength; i++) {
  479.             System.out.println(combination[i]);
  480.             combinationEssential.add(combination[i]);
  481.         }
  482.         for (int i = 0; i < essentialPrimeImplicantsContainingOne.size(); i++)
  483.             System.out.println(essentialPrimeImplicantsContainingOne.get(i));
  484.         System.out.println();
  485.         String expression = findExpression(essentialPrimeImplicantsContainingOne);
  486.         if(!expression.equals(""))
  487.             expression+= " + ";
  488.         expression += findExpression(combinationEssential);
  489.         System.out.println(expression);
  490.     }
  491.  
  492.     /**
  493.      * The main method.
  494.      *
  495.      * @param args the arguments
  496.      */
  497.     public static void main(String[] args) {
  498.         System.out.println("Enter the number of variables you want");
  499.         numberOfBits = in.nextInt();
  500.         System.out.println("Enter the minterms in decimal <-1 to finish>:");
  501.         while (true) {
  502.             int input;
  503.             input = in.nextInt();
  504.             if (input == -1)
  505.                 break;
  506.             minterms.add(input);
  507.         }
  508.         System.out.println("Enter the dontcares in decimal <-1 to finish>:");
  509.         while (true) {
  510.             int input;
  511.             input = in.nextInt();
  512.             if (input == -1)
  513.                 break;
  514.             dontcares.add(input);
  515.         }
  516.  
  517.         fillArrayList();
  518.         decimalToBinary();
  519.         doComparisons();
  520.        
  521.         System.out.println();
  522.         System.out.println();
  523.         System.out.println("Grouping");
  524.         System.out.println();
  525.         for (int k = 0; k < comparisons.size(); k++) {
  526.             boolean comparisonHasElements = false;
  527.  
  528.             for (int i = 0; i < comparisons.get(k).size(); i++) {
  529.                 if (comparisons.get(k).get(i).isEmpty())
  530.                     continue;
  531.                 for (int j = 0; j < comparisons.get(k).get(i).size(); j++) {
  532.                     System.out.println(comparisons.get(k).get(i).get(j));
  533.                 }
  534.                 comparisonHasElements = true;
  535.                 System.out.println("-----------------");
  536.             }
  537.             if (comparisonHasElements) {
  538.                 System.out.println("______________________________________________________");
  539.                 System.out.println();
  540.             }
  541.         }
  542.         if (minterms.isEmpty()==true)
  543.         {
  544.             System.out.println("Expression = 0");
  545.             System.exit(0);
  546.         }
  547.         System.out.println("Prime Implicants:");
  548.         for (int i = 0; i < primeImplicants.size(); i++) {
  549.             System.out.println(primeImplicants.get(i));
  550.         }
  551.         System.out.println();
  552.         System.out.println(findExpression(primeImplicants));
  553.         System.out.println("______________________________________________________");
  554.         System.out.println();
  555.         System.out.println();
  556.         System.out.println("Essential Prime Implicants:");
  557.         countAppearances();
  558.         if (containsOne()) {
  559.             getReducedEssentialImplicants();
  560.             if (!needsCombinations()) {
  561.                 for (int i = 1; i <= primeImplicants.size() && !foundCombination; i++)
  562.                     generateCombinations(1, 0, i);
  563.             }
  564.             else {
  565.                 for(int i=0; i<essentialPrimeImplicantsContainingOne.size(); i++)
  566.                     System.out.println(essentialPrimeImplicantsContainingOne.get(i));
  567.                
  568.                 System.out.println();
  569.                 System.out.println(findExpression(essentialPrimeImplicantsContainingOne));
  570.                
  571.             }
  572.         }
  573.         else {
  574.             for (int i = 1; i <= primeImplicants.size() && !foundCombination; i++)
  575.                 generateCombinations(1, 0, i);
  576.         }
  577.  
  578.     }
  579.  
  580. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!