Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.File;
- import java.util.Formatter;
- import java.util.LinkedList;
- import java.util.Scanner;
- import java.util.Stack;
- public class Classy {
- static int nOfBits = 0;
- static int noRemain = 0;
- static StringBuilder inputstr = new StringBuilder();
- static StringBuilder dontcarestr = new StringBuilder();
- static LinkedList<Nody> array[];
- static LinkedList<Nody> remain;
- static LinkedList<Nody> finall_array;
- static int arraysize = 0;
- static int minterms[];
- static boolean file = false;
- static Formatter writefile ;
- static void printDebug(String s) {
- if (file) {
- writefile.format("%s\n",s);
- }
- else {
- System.out.println(s);
- }
- }
- static void binary(int decimal) {
- StringBuilder conc = new StringBuilder();
- String bin = Integer.toBinaryString(decimal);
- int count = 0;
- for (int i = 0; i < bin.length(); i++) {
- if (bin.charAt(i) == '1') {
- count++;
- }
- }
- for (int i = 0; i < nOfBits - bin.length(); i++) {
- conc.append("0");
- }
- conc.append(bin);
- printDebug(conc.toString());
- int de = (int) Math.pow(2, nOfBits) - 1;
- printDebug("" + de);
- Nody new_node = new Nody((int) Math.pow(2, nOfBits) - 1);
- new_node.minterm = conc.toString();
- printDebug(new_node.minterm);
- // new_node.min[decimal] = true;
- String s = Integer.toString(decimal);
- if (new_node.symbol == null) {
- new_node.symbol = s;
- } else {
- new_node.symbol += s;
- }
- // new_node.symbol += s ;
- new_node.symbol += ",";
- // new_node.symbol.append(Integer.toString(decimal)).append(',');
- printDebug(new_node.symbol);
- int nOfOnes = 0;
- for (int i = 0; i < new_node.minterm.length(); i++) {
- if (new_node.minterm.charAt(i) == '1') {
- nOfOnes++;
- }
- }
- if (array[nOfOnes] == null) {
- array[nOfOnes] = new LinkedList();
- }
- array[nOfOnes].add(new_node);
- }
- public static void solve(LinkedList<Nody> tmp[]) {
- LinkedList<Nody> tmpnext = new LinkedList<Nody>();
- int i = 0;
- while (i < nOfBits) {
- LinkedList<Nody> no = tmp[i];
- LinkedList<Nody> no2 = tmp[i + 1];
- if (no == null || no2 == null) {
- i++;
- continue;
- }
- int n = no.size();
- int n2 = no2.size();
- int del1 = 0;
- int del2 = 0;
- for (int j = 0; j < n; j++) {
- int take = 0;
- for (int k = 0; k < tmp[i + 1].size(); k++) {
- if (tmp[i + 1].get(k) == null) {
- continue;
- }
- if (tmp[i].get(j) == null) {
- continue;
- }
- int count = 0;
- String newminterm = new String();
- for (int l = 0; l < nOfBits; l++) {
- printDebug(tmp[i].get(j).minterm);
- printDebug(tmp[i + 1].get(k).minterm);
- printDebug("" + tmp[i].get(j).minterm.charAt(l));
- printDebug("" + tmp[i + 1].get(k).minterm.charAt(l));
- if (tmp[i].get(j).minterm.charAt(l) == tmp[i + 1].get(k).minterm.charAt(l)) {
- if (newminterm == null) {
- newminterm = "" + tmp[i].get(j).minterm.charAt(l);
- } else {
- newminterm += "" + tmp[i].get(j).minterm.charAt(l);
- }
- // newminterm.append(tmp[i].get(j).minterm.charAt(l));
- printDebug(newminterm);
- continue;
- } else {
- count++;
- if (newminterm == null) {
- newminterm = "-";
- } else {
- newminterm += "-";
- }
- printDebug(newminterm);
- // newminterm.append('-');
- if (count > 1)
- break;
- }
- }
- if (count == 1) {
- Nody new_node = new Nody(nOfBits);
- new_node.minterm = newminterm;
- new_node.min[i] = true;
- if (new_node.symbol == null) {
- new_node.symbol = tmp[i].get(j).symbol;
- // new_node.symbol += ",";
- new_node.symbol += tmp[i + 1].get(k).symbol;
- // new_node.symbol += ",";
- } else {
- new_node.symbol += tmp[i].get(j).symbol;
- // new_node.symbol += ",";
- new_node.symbol += tmp[i + 1].get(k).symbol;
- // new_node.symbol += ",";
- }
- printDebug(new_node.minterm);
- printDebug(new_node.symbol);
- // new_node.symbol.append(Integer.toString(i)).append(',').append(Integer.toString(i
- // + 1))
- // .append(',');
- tmpnext.add(new_node);
- take = 1;
- }
- }
- if (take == 0) {
- Nody new_node = new Nody(nOfBits);
- new_node.minterm = tmp[i].get(j).minterm;
- if (new_node.symbol == null) {
- new_node.symbol = tmp[i].get(j).symbol;
- } else {
- new_node.symbol += tmp[i].get(j).symbol;
- }
- // new_node.symbol.append(Integer.toString(i)).append(',');
- if (remain == null) {
- remain = new LinkedList<Nody>();
- }
- remain.add(new_node);
- for (int l = 0; l < remain.size(); l++) {
- // printDebug("remain ya yoyo");
- printDebug(remain.get(l).minterm);
- printDebug(remain.get(l).symbol);
- }
- //
- noRemain++;
- }
- }
- i++;
- }
- getdashes(tmpnext);
- }
- public static void getdashes(LinkedList<Nody> dash) {
- LinkedList<Nody> tmpdash = new LinkedList<Nody>();
- boolean check_ind[] = new boolean[dash.size()];
- printDebug(Integer.toString(dash.size()));
- for (int i = 0; i < dash.size(); i++) {
- int take = 0;
- if (check_ind[i] == true) {
- continue;
- }
- for (int j = 0; j < dash.size(); j++) {
- if (i == j) {
- continue;
- }
- printDebug(dash.get(i).minterm);
- printDebug(dash.get(i).symbol);
- printDebug(dash.get(j).minterm);
- printDebug(dash.get(j).symbol);
- int count = 0;
- String newminterm = new String();
- for (int l = 0; l < nOfBits; l++) {
- if (dash.get(j).minterm.charAt(l) == dash.get(i).minterm.charAt(l)) {
- if (newminterm == null) {
- newminterm = "" + dash.get(j).minterm.charAt(l);
- } else {
- newminterm += "" + dash.get(j).minterm.charAt(l);
- }
- // newminterm.append(dash.get(j).minterm.charAt(l));
- printDebug(newminterm);
- continue;
- } else {
- count++;
- if (newminterm == null) {
- newminterm = "-";
- } else {
- newminterm += "-";
- }
- printDebug(newminterm);
- // newminterm.append('-');
- if (count > 1)
- break;
- }
- }
- if (count == 1) {
- int add = 1;
- Nody new_node = new Nody(nOfBits);
- new_node.minterm = newminterm;
- if (new_node.symbol == null) {
- new_node.symbol = dash.get(i).symbol;
- new_node.symbol += dash.get(j).symbol;
- // new_node.symbol += ",";
- } else {
- new_node.symbol += dash.get(i).symbol;
- new_node.symbol += dash.get(j).symbol;
- // new_node.symbol += ",";
- }
- printDebug(new_node.symbol);
- printDebug(new_node.minterm);
- // new_node.symbol.append(dash.get(i).symbol).append(dash.get(j).symbol).append(',');
- if (check_ind[j] == true) {
- if (new_node.minterm == dash.get(j).minterm)
- add = 0;
- }
- if (add == 1) {
- check_ind[j] = true;
- tmpdash.add(new_node);
- }
- take = 1;
- }
- }
- if (take == 0) {
- Nody new_node = new Nody(nOfBits);
- new_node.minterm = dash.get(i).minterm;
- new_node.symbol = dash.get(i).symbol;
- printDebug(new_node.minterm);
- printDebug(new_node.symbol);
- if (remain == null) {
- remain = new LinkedList<Nody>();
- }
- // remain.add(new_node);
- remain.add(new_node);
- noRemain++;
- }
- }
- finall_array = tmpdash;
- // printDebug("tempy");
- for (int i = 0; i < tmpdash.size(); i++) {
- printDebug(tmpdash.get(i).symbol);
- printDebug(tmpdash.get(i).minterm);
- }
- if (tmpdash.size() != 0) {
- getdashes(tmpdash);
- } else {
- int del = 0;
- // printDebug("final ya yOyo");
- for (int i = 0; i < remain.size(); i++) {
- if (remain.get(i).equals(null)) {
- remain.remove(i);
- // del++;
- // i--;
- }
- }
- // for (int i = 0; i < remain.size(); i++) {
- // for (int k = 0; k < remain.size(); k++) {
- // if (i == k) {
- // continue;
- // }
- // if (remain.get(k).minterm.equals(remain.get(i).minterm)) {
- // remain.remove(k);
- // }
- // }
- //
- // }
- // printDebug("rem bef");
- printDebug("First final terms.");
- for (int i = 0; i < remain.size(); i++) {
- printDebug(remain.get(i).symbol);
- printDebug(remain.get(i).minterm);
- }
- // printDebug("rem af");
- // for (int i = 0; i < finall_array.size(); i++) {
- // printDebug(finall_array.get(i).symbol);
- // printDebug(finall_array.get(i).minterm);
- // }
- }
- }
- static int min = 4;
- static LinkedList<Nody> terms = new LinkedList<Nody>();
- public static void allPossible(int index) {
- boolean[] takenterms = new boolean[(int) Math.pow(nOfBits, 2)];
- if (index == remain.size()) {
- return;
- }
- allPossible(index + 1);
- Nody temp = remain.get(index);
- terms.add(temp);
- Nody tempnode;
- for (int i = 0; i < terms.size(); i++) {
- tempnode = terms.get(i);
- String temparray[] = tempnode.symbol.split(",");
- for (int j = 0; j < temparray.length; j++) {
- takenterms[Integer.parseInt(temparray[j])] = true;
- }
- }
- for (int i = 0; i < minterms.length; i++) {
- if (!takenterms[minterms[i]]) {
- break;
- } else if (i == minterms.length - 1) {
- //// print terms hnaaaaaaaaa
- LinkedList<Nody> tempstack = terms;
- Nody current;
- if (tempstack.size() <= min) {
- min = tempstack.size();
- for (int j = 0; j < tempstack.size(); j++) {
- current = tempstack.get(j);
- for (int k = 0; k < current.minterm.length(); k++) {
- if (current.minterm.charAt(k) == '1') {
- if (file) {
- writefile.format("%c", 'A' + k);
- }
- else {
- System.out.print((char) ('A' + k));
- }
- } else if (current.minterm.charAt(k) == '0') {
- if (file) {
- writefile.format("%c'", 'A' + k);
- }
- else {
- System.out.print((char) ('A' + k) + "'");
- }
- }
- }
- if (j != tempstack.size() - 1) {
- if(file) {
- writefile.format("+");
- }
- else {
- System.out.print("+");
- }
- }
- }
- if(file) {
- writefile.format("\n");
- }
- else {
- System.out.println();
- }
- }
- terms.remove(terms.size() - 1);
- return;
- }
- }
- allPossible(index + 1);
- terms.remove(terms.size() - 1);
- }
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- /**
- * scan from file
- */
- Scanner scan = new Scanner(System.in);
- System.out.println("please choose \n1-from file\n2-from console");
- int x;
- while (true) {
- try {
- x = scan.nextInt();
- if (x != 1 && x != 2) {
- throw new RuntimeException();
- }
- break;
- } catch (Exception e) {
- System.out.println("wrong input, please try again");
- }
- }
- switch (x) {
- case 1:
- Scanner sc;
- try {
- file = true;
- writefile = new Formatter (new File ("result.txt"));
- sc = new Scanner(new File("aia.txt"));
- LinkedList<Integer> input = new LinkedList<Integer>();
- LinkedList<Integer> dontcare = new LinkedList<Integer>();
- int num = sc.nextInt();
- if (num < 0) {
- throw new RuntimeException();
- }
- int max = num;
- input.add(num);
- while (sc.hasNext()) {
- num = sc.nextInt();
- if (num == -1) {
- break;
- }
- if (num < 0) {
- throw new RuntimeException();
- }
- input.add(num);
- if (max < num) {
- max = num;
- }
- }
- if (num == -1) {
- while (sc.hasNext()) {
- num = sc.nextInt();
- if (num == -1) {
- break;
- }
- if (num < 0) {
- throw new RuntimeException();
- }
- dontcare.add(num);
- if (max < num) {
- max = num;
- }
- }
- }
- nOfBits = (int) (Math.log(max) / Math.log(2)) + 1;
- for (int i = 0; i < input.size(); i++) {
- for (int j = 0; j < i; j++) {
- if (input.get(i).equals(input.get(j))) {
- input.remove(j);
- j--;
- break;
- }
- }
- }
- for (int i = 0; i < dontcare.size(); i++) {
- for (int j = 0; j < i; j++) {
- if (dontcare.get(i).equals(dontcare.get(j))) {
- dontcare.remove(j);
- j--;
- break;
- }
- }
- }
- for (int i = 0; i < dontcare.size(); i++) {
- for (int j = 0; j < input.size(); j++) {
- if (input.get(j).equals(dontcare.get(i))) {
- throw new RuntimeException();
- }
- }
- }
- for (int i = 0; i < input.size(); i++) {
- if (i == 0) {
- inputstr.append(input.get(i));
- } else {
- inputstr.append("," + input.get(i));
- }
- }
- for (int i = 0; i < dontcare.size(); i++) {
- if (i == 0) {
- dontcarestr.append(dontcare.get(i));
- } else {
- dontcarestr.append("," + dontcare.get(i));
- }
- }
- String inputString = inputstr.toString();
- String[] splitterInp = inputString.split(",");
- array = new LinkedList[nOfBits + 1];
- for (int i = 0; i < splitterInp.length; i++) {
- int inty = Integer.parseInt(splitterInp[i]);
- binary(inty);
- }
- String dontCareString = dontcarestr.toString();
- if (dontCareString.length() != 0) {
- String[] splitterDon = dontCareString.split(",");
- for (int i = 0; i < splitterDon.length; i++) {
- binary(Integer.parseInt(splitterDon[i]));
- }
- }
- solve(array);
- minterms = new int[input.size()];
- for (int i = 0; i < input.size(); i++) {
- minterms[i] = input.get(i);
- }
- allPossible(0);
- writefile.close();
- } catch (Exception e) {
- System.out.println("Fail to read from file OR wrong input");
- }
- break;
- /**
- * scan form console
- */
- // StringBuilder dontcarestr1 = new StringBuilder();
- // StringBuilder inputstr1 = new StringBuilder();
- case 2:
- Scanner sc1;
- System.out.println("enter the min terms");
- LinkedList<Integer> input1 = new LinkedList<Integer>();
- LinkedList<Integer> dontcare1 = new LinkedList<Integer>();
- try {
- sc1 = new Scanner(System.in);
- int num = sc1.nextInt();
- if (num < 0) {
- throw new RuntimeException();
- }
- int max = num;
- input1.add(num);
- while (true) {
- System.out.println("enter -1 to input dontcare:");
- num = sc1.nextInt();
- if (num == -1) {
- break;
- }
- if (num < 0) {
- throw new RuntimeException();
- }
- input1.add(num);
- if (max < num) {
- max = num;
- }
- }
- if (num == -1) {
- System.out.println("enter don't care");
- while (true) {
- System.out.println("enter -1 to end: ");
- num = sc1.nextInt();
- if (num == -1) {
- break;
- }
- if (num < 0) {
- throw new RuntimeException();
- }
- dontcare1.add(num);
- if (max < num) {
- max = num;
- }
- }
- }
- nOfBits = (int) (Math.log(max) / Math.log(2)) + 1;
- /// check repetition in min terms
- for (int i = 0; i < input1.size(); i++) {
- for (int j = 0; j < i; j++) {
- if (input1.get(i).equals(input1.get(j))) {
- input1.remove(j);
- j--;
- break;
- }
- }
- }
- //// check repetition in dontcare
- for (int i = 0; i < dontcare1.size(); i++) {
- for (int j = 0; j < i; j++) {
- if (dontcare1.get(i).equals(dontcare1.get(j))) {
- dontcare1.remove(j);
- j--;
- break;
- }
- }
- }
- /// check for repetition in min terms and dont care
- for (int i = 0; i < dontcare1.size(); i++) {
- for (int j = 0; j < input1.size(); j++) {
- if (input1.get(j).equals(dontcare1.get(i))) {
- throw new RuntimeException();
- }
- }
- }
- for (int i = 0; i < input1.size(); i++) {
- if (i == 0) {
- inputstr.append(input1.get(i));
- } else {
- inputstr.append("," + input1.get(i));
- }
- }
- printDebug(inputstr.toString());
- for (int i = 0; i < dontcare1.size(); i++) {
- if (i == 0) {
- dontcarestr.append(dontcare1.get(i));
- } else {
- dontcarestr.append("," + dontcare1.get(i));
- }
- }
- printDebug(dontcarestr.toString());
- } catch (Exception e1) {
- System.out.println("wrong input");
- }
- String inputString = inputstr.toString();
- String[] splitterInp = inputString.split(",");
- array = new LinkedList[nOfBits + 1];
- for (int i = 0; i < splitterInp.length; i++) {
- int inty = Integer.parseInt(splitterInp[i]);
- binary(inty);
- }
- String dontCareString = dontcarestr.toString();
- if (dontCareString.length() != 0) {
- String[] splitterDon = dontCareString.split(",");
- for (int i = 0; i < splitterDon.length; i++) {
- binary(Integer.parseInt(splitterDon[i]));
- }
- }
- solve(array);
- minterms = new int[input1.size()];
- for (int i = 0; i < input1.size(); i++) {
- minterms[i] = input1.get(i);
- }
- allPossible(0);
- break;
- }
- // printDebug("finbrra");
- // printDebug(Integer.toString(finall_array.size()));
- // for (int i = 0; i < finall_array.size(); i++) {
- // printDebug("fingwa");
- // printDebug(finall_array.get(i).symbol);
- // printDebug(finall_array.get(i).minterm);
- // }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement