API tools faq
paste
Advertisement
Guest User

Untitled

a guest
May 24th, 2018
72
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 23.21 KB | None | 0 0
raw download clone embed print report
  1. import java.util.*;
  2. import java.util.regex.Pattern;
  3. import java.io.*;
  4. public class Pojeto {
  5.  
  6. public static void main(String[] args) {
  7. Scanner in = new Scanner(System.in);
  8. int casos = in.nextInt();
  9. in.nextLine();
  10. for(int p=0;p<casos;p++) {
  11. String cs = in.nextLine();
  12. String tipo = cs.substring(0, 2);
  13. String teste = cs.substring(3, cs.length());
  14. int problemNumber=p+1;
  15. if(tipo.equals("TT")) {
  16. System.out.println("Problema #"+problemNumber);
  17. printTT(getClauses(teste),getVariables(teste),numVariables(getVariables(teste)),numClauses(getClauses(teste)));
  18.  
  19. }else {
  20. System.out.println("Problema #" + problemNumber);
  21. if(isFNC(teste) == true) {
  22. if(isHorn(teste) == true) {
  23. /*
  24. if(isSat(teste) == true) {
  25. System.out.println("Sim, é satisfatível.");
  26. }else {
  27. System.out.println("Não, não é satisfatível.");
  28. }*/
  29. }else {
  30. System.out.println("Nem todas as cláusulas são de Horn.");
  31. }
  32. }else {
  33. System.out.println("Não está na FNC.");
  34. }
  35. }
  36. }
  37. }
  38.  
  39. static Queue<String> getClauses(String teste) {
  40. teste = teste.replaceAll(" ","");
  41. Stack<Character> parenteses = new Stack<Character>();
  42. Stack<Integer> parentesesIndex = new Stack<Integer>();
  43. Queue<String> clausulas = new LinkedList<String>();
  44. for(int x=0;x<teste.length();x++) {
  45. if(teste.charAt(x)=='(') {
  46. parenteses.push(teste.charAt(x));
  47. parentesesIndex.push(x);
  48. }else if(teste.charAt(x)==')') {
  49. parenteses.pop();
  50. String cla = teste.substring(parentesesIndex.pop()+1, x);
  51. clausulas.add(cla);
  52. }
  53. }
  54. return clausulas;
  55. }
  56.  
  57. static boolean isFNC(String teste) {
  58. boolean booleano = true;
  59. teste = teste.replaceAll(" ", "");
  60. String[] fnc = new String[teste.length()];
  61. fnc = teste.split("");
  62. for(int i = 0; i <= teste.length() - 1; i++) {
  63. if(fnc[i].equals("<")) {
  64. booleano = false;
  65. }else if(fnc[i].equals(">")) {
  66. booleano = false;
  67. }
  68. }
  69. return booleano;
  70. }
  71.  
  72. static boolean isHorn(String teste) {
  73. boolean booleano = true;
  74. teste = teste.replaceAll(" ", "");
  75. String[] horn = new String[teste.length()];
  76. horn = teste.split("");
  77. int c1 = 0;
  78. int c2 = 0;
  79. for(int i = 0; i <= teste.length() - 1; i++) {
  80. if(i == 0 && (horn[i].equals("P") || horn[i].equals("R") || horn[i].equals("Q") || horn[i].equals("S"))) {
  81. c2++;
  82. }else if(horn[i].equals("P") && !horn[i - 1].equals("~") || horn[i].equals("R") && !horn[i - 1].equals("~") || horn[i].equals("Q") && !horn[i - 1].equals("~") || horn[i].equals("S") && !horn[i - 1].equals("~")) {
  83. c2++;
  84. }
  85. }
  86. for(int i = 0; i <= teste.length() - 1; i++) {
  87. if(horn[i].equals("&")) {
  88. c1++;
  89. }
  90. }
  91. if(c2 > c1) {
  92. booleano = false;
  93. }
  94. return booleano;
  95. }
  96.  
  97. /*
  98. static boolean isSat(String teste) {
  99.  
  100. }*/
  101.  
  102. static void orderBysize(Queue<String> clauses){
  103. String array[] = new String[clauses.size()];
  104. int x=0;
  105. while(!clauses.isEmpty()) {
  106. array[x]=clauses.remove();
  107. x++;
  108. }
  109. for(int i = 0; i < array.length-1; i++){
  110. for(int k = 0; k < array.length-i-1; k++){
  111. if(array[k].length() > array[k+1].length()){
  112. String aux = array[k];
  113. array[k] = array[k+1];
  114. array[k+1] = aux;
  115. }
  116. }
  117. }
  118. for(int i=0;i<array.length;i++) {
  119. clauses.add(array[i]);
  120. }
  121.  
  122. }
  123.  
  124. static Stack<String> getVariables(String teste) {
  125. boolean p=false,q=false,r=false,s=false;
  126. Stack<String> var = new Stack<String>();
  127. for(int x=0;x<teste.length();x++) {
  128. if(teste.charAt(x)=='P'){
  129. if(p==false) {
  130. var.push("P");
  131. p=true;
  132. }
  133. }else if(teste.charAt(x)=='Q') {
  134. if(q==false) {
  135. var.push("Q");
  136. q=true;
  137. }
  138. }else if(teste.charAt(x)=='R') {
  139. if(r==false) {
  140. var.push("R");
  141. r=true;
  142. }
  143. }else if(teste.charAt(x)=='S') {
  144. if(s==false) {
  145. var.push("S");
  146. s=true;
  147. }
  148. }
  149. }
  150. return var;
  151. }
  152.  
  153. static String getOperation(String teste) {
  154. boolean p=false,q=false,r=false,s=false,t=false;
  155. String op="";
  156. for(int x=0;x<teste.length();x++) {
  157. if(teste.charAt(x)=='~'){
  158. op="~";
  159. }else if(teste.charAt(x)=='>') {
  160. op=">";
  161. }else if(teste.charAt(x)=='<') {
  162. op="<";
  163. }else if(teste.charAt(x)=='v') {
  164. op="v";
  165. }else if(teste.charAt(x)=='&') {
  166. op="&";
  167. }
  168. }
  169. return op;
  170. }
  171.  
  172. static int numVariables(Stack<String> var) {
  173. return var.size();
  174. }
  175.  
  176. static int numClauses(Queue<String> var) {
  177. return var.size();
  178. }
  179.  
  180. static String[][] printTT(Queue<String> clausulas, Stack<String> variaveis,int numVariaveis, int numClausulas) {
  181. String [][] TT= new String [(int) Math.pow(2, numVariaveis)+1][numClausulas+numVariaveis+1];
  182. orderBysize(clausulas);
  183. //coloca uma sequencia de numeros booleanos numa fila
  184. Queue <String> nums= new LinkedList();
  185. int rows = (int) Math.pow(2,numVariaveis);
  186. for (int i=0; i<rows; i++) {
  187. for (int j=numVariaveis-1; j>=0; j--) {
  188. String top=Integer.toString((i/(int) Math.pow(2, j))%2);
  189. nums.add(top);
  190. }
  191. }
  192. Stack<String>clausulinhas=new Stack();
  193. //constrói a matriz
  194. for(int x=0;x<((int) Math.pow(2, numVariaveis)+1);x++) {
  195. for(int y=0;y<(numClausulas+numVariaveis+1);y++) {
  196. if(y==numVariaveis) {
  197. TT[x][y]="|";
  198. }else if(x>0&&y<numVariaveis){
  199. TT[x][y]=nums.remove();
  200. }else if(x==0) {
  201. if(!variaveis.isEmpty()&&y<=numVariaveis) {
  202. TT[x][y]=variaveis.get(y);
  203. }else if(!clausulas.isEmpty()) {
  204. TT[x][y]=clausulas.remove();
  205. clausulinhas.push(TT[x][y]);
  206. }
  207. }else if(y>numVariaveis){
  208. String clausulaCaso=TT[0][y];
  209. int numClausulaCaso=getClauses(clausulaCaso).size();
  210. Stack<String> variavel=getVariables(clausulaCaso);
  211. //operação simples ex:~p ex2:p>q
  212. if(numClausulaCaso==0) {
  213. String op=getOperation(clausulaCaso);
  214. if(op.equals("~")) {
  215. String spl[]=clausulaCaso.split("~");
  216. int pos=variaveis.indexOf(spl[1]);
  217. if(TT[x][pos].equals("0")) {
  218. TT[x][y]="1";
  219. }else {
  220. TT[x][y]="0";
  221. }
  222. }else if(op.equals(">")){
  223. String spl[]=clausulaCaso.split(">");
  224. int pos=variaveis.indexOf(spl[0]);
  225. int pos2=variaveis.indexOf(spl[1]);
  226. if(TT[x][pos].equals("0")||TT[x][pos2].equals("1")) {
  227. TT[x][y]="1";
  228. }else {
  229. TT[x][y]="0";
  230. }
  231.  
  232. }else if(op.equals("<")) {
  233. String spl[]=clausulaCaso.split("<");
  234. int pos=variaveis.indexOf(spl[0]);
  235. int pos2=variaveis.indexOf(spl[1]);
  236. if(TT[x][pos].equals(TT[x][pos2])) {
  237. TT[x][y]="1";
  238. }else {
  239. TT[x][y]="0";
  240. }
  241.  
  242. }else if(op.equals("&")) {
  243. String spl[]=clausulaCaso.split("&");
  244. int pos=variaveis.indexOf(spl[0]);
  245. int pos2=variaveis.indexOf(spl[1]);
  246. if(TT[x][pos].equals("1")&&TT[x][pos2].equals("1")) {
  247. TT[x][y]="1";
  248. }else {
  249. TT[x][y]="0";
  250. }
  251.  
  252. }else if(op.equals("v")) {
  253. String spl[]=clausulaCaso.split("v");
  254. int pos=variaveis.indexOf(spl[0]);
  255. int pos2=variaveis.indexOf(spl[1]);
  256. if(TT[x][pos].equals("0")&&TT[x][pos2].equals("0")) {
  257. TT[x][y]="0";
  258. }else {
  259. TT[x][y]="1";
  260. }
  261. }
  262. }else {
  263. clausulaCaso=clausulaCaso+")";
  264. clausulaCaso="("+clausulaCaso;
  265. Queue<String>clausula1=getClauses(clausulaCaso);
  266. orderBysize(clausula1);
  267. Stack<String>clausula=new Stack();
  268. while(!clausula1.isEmpty()) {
  269. clausula.push(clausula1.remove());
  270. }
  271. String clau1="",clau2="";
  272. // while(clausula.size()>1) {
  273. // if(clausula.size()==3) {
  274. // clau1=clausula.remove();
  275. // }else {
  276. // clau2=clausula.remove();
  277. // }
  278. // }
  279. // clausulaCaso=clausulaCaso.replaceAll(Pattern.quote(clau2),"");
  280. // clausulaCaso=clausulaCaso.replaceAll(Pattern.quote(clau1),"");
  281. // clausulaCaso=clausulaCaso.replaceAll("\\)", "");
  282. // clausulaCaso=clausulaCaso.replaceAll("\\(", "");
  283. //
  284. // String clausulaMain=clausula.remove();
  285. int clauSize=clausula.size();
  286. String clausulaMain="";
  287. for(int f=clauSize;f>0;f--) {
  288. if(f==clauSize) {
  289. clausulaMain=clausula.pop();
  290. }else if(f==clauSize-1) {
  291. clau2=clausula.pop();
  292. clausulaCaso=clausulaCaso.replaceAll(Pattern.quote("("+clau2+")"),"");
  293. }else if(f==clauSize-2) {
  294. clau1=clausula.pop();
  295. clausulaCaso=clausulaCaso.replaceAll(Pattern.quote("("+clau1+")"),"");
  296. }else {
  297. if(!clausulaCaso.contains(clausula.peek())) {
  298. clausulaCaso=clausulaCaso.replaceAll(Pattern.quote("("+clausula.pop()+")"),"");
  299. }
  300. }
  301. }
  302. clausulaCaso=clausulaCaso.substring(1,clausulaCaso.length()-1);
  303. //apos a retirada sobrar apenas a operação:
  304. if(clausulaCaso.length()==1) {
  305. String op=getOperation(clausulaCaso);
  306. if(op.equals("~")) {
  307. int pos1=clausulinhas.indexOf(clau2)+1+variaveis.size();
  308. if(TT[x][pos1].equals("0")) {
  309. TT[x][y]="1";
  310. }else {
  311. TT[x][y]="0";
  312. }
  313. }else if(op.equals(">")){
  314. int pos2=clausulinhas.indexOf(clau1)+1+variaveis.size();
  315. int pos=clausulinhas.indexOf(clau2)+1+variaveis.size();
  316. if(TT[x][pos].equals("0")||TT[x][pos2].equals("1")) {
  317. TT[x][y]="1";
  318. }else {
  319. TT[x][y]="0";
  320. }
  321. }else if(op.equals("<")) {
  322. int pos=clausulinhas.indexOf(clau1)+1+variaveis.size();
  323. int pos2=clausulinhas.indexOf(clau2)+1+variaveis.size();
  324. if(TT[x][pos].equals(TT[x][pos2])) {
  325. TT[x][y]="1";
  326. }else {
  327. TT[x][y]="0";
  328. }
  329. }else if(op.equals("&")) {
  330. int pos=clausulinhas.indexOf(clau1)+1+variaveis.size();
  331. int pos2=clausulinhas.indexOf(clau2)+1+variaveis.size();
  332. if(TT[x][pos].equals("1")&&TT[x][pos2].equals("1")) {
  333. TT[x][y]="1";
  334. }else {
  335. TT[x][y]="0";
  336. }
  337. }else if(op.equals("v")) {
  338. int pos=clausulinhas.indexOf(clau1)+1+variaveis.size();
  339. int pos2=clausulinhas.indexOf(clau2)+1+variaveis.size();
  340. if(TT[x][pos].equals("0")&&TT[x][pos2].equals("0")) {
  341. TT[x][y]="0";
  342. }else {
  343. TT[x][y]="1";
  344. }
  345. }
  346. //após a retirada sobrar variavel+operação ex: p>
  347. }else if(clausulaCaso.length()==2) {
  348. Stack<String> var=getVariables(clausulaCaso);
  349. String op=getOperation(clausulaCaso);
  350. int casoPos=1;
  351. if(clausulaCaso.charAt(0)=='P'||clausulaCaso.charAt(0)=='Q'||clausulaCaso.charAt(0)=='R'||clausulaCaso.charAt(0)=='S'||clausulaCaso.charAt(0)=='~') {
  352. casoPos=0;
  353. }
  354. if(op.equals("~")) {
  355. int pos1=clausulinhas.indexOf(clausulaMain)+1+variaveis.size();
  356. if(TT[x][pos1].equals("0")) {
  357. TT[x][y]="1";
  358. }else {
  359. TT[x][y]="0";
  360. }
  361. }else if(op.equals(">")){
  362. if(casoPos==0) {
  363. int pos=variaveis.indexOf(var.pop());
  364. int pos2=clausulinhas.indexOf(clau2)+1+variaveis.size();
  365. if(TT[x][pos].equals("0")||TT[x][pos2].equals("1")) {
  366. TT[x][y]="1";
  367. }else {
  368. TT[x][y]="0";
  369. }
  370. }else {
  371. int pos2=variaveis.indexOf(var.pop());
  372. int pos=clausulinhas.indexOf(clau2)+1+variaveis.size();
  373. if(TT[x][pos].equals("0")||TT[x][pos2].equals("1")) {
  374. TT[x][y]="1";
  375. }else {
  376. TT[x][y]="0";
  377. }
  378. }
  379. }else if(op.equals("<")) {
  380. int pos=variaveis.indexOf(var.pop());
  381. int pos2=clausulinhas.indexOf(clau2)+1+variaveis.size();
  382. if(TT[x][pos].equals(TT[x][pos2])) {
  383. TT[x][y]="1";
  384. }else {
  385. TT[x][y]="0";
  386. }
  387. }else if(op.equals("&")) {
  388. int pos=variaveis.indexOf(var.pop());
  389. int pos2=clausulinhas.indexOf(clau2)+1+variaveis.size();
  390. if(TT[x][pos].equals("1")&&TT[x][pos2].equals("1")) {
  391. TT[x][y]="1";
  392. }else {
  393. TT[x][y]="0";
  394. }
  395. }else if(op.equals("v")) {
  396. int pos=variaveis.indexOf(var.pop());
  397. int pos2=clausulinhas.indexOf(clau2)+1+variaveis.size();
  398. if(TT[x][pos].equals("0")&&TT[x][pos2].equals("0")) {
  399. TT[x][y]="0";
  400. }else {
  401. TT[x][y]="1";
  402. }
  403. }
  404. //após a retirada sobrar clausula+operação ex: p>q >
  405. }else {
  406. String var="";
  407. int casoPos=0;
  408. int l=clausulaCaso.length();
  409. if(clausulaCaso.charAt(l-1)=='<'||clausulaCaso.charAt(l-1)=='>'||clausulaCaso.charAt(l-1)=='&'||clausulaCaso.charAt(l-1)=='v'||clausulaCaso.charAt(l-1)=='~') {
  410. var=clausulaCaso.substring(1, clausulaCaso.length()-2);
  411. }else {
  412. var=clausulaCaso.substring(2, clausulaCaso.length()-1);
  413. casoPos=1;
  414. }
  415. clausulaCaso=clausulaCaso.replaceAll(Pattern.quote(var),"");
  416. String op=getOperation(clausulaCaso);
  417. if(op.equals("~")) {
  418. int pos1=clausulinhas.indexOf(clausulaMain)+1+variaveis.size();
  419. if(TT[x][pos1].equals("0")) {
  420. TT[x][y]="1";
  421. }else {
  422. TT[x][y]="0";
  423. }
  424. }else if(op.equals(">")){
  425. if(casoPos==0) {
  426. int pos=clausulinhas.indexOf(var)+1+variaveis.size();
  427. int pos2=clausulinhas.indexOf(clau2)+1+variaveis.size();
  428. if(TT[x][pos].equals("0")||TT[x][pos2].equals("1")) {
  429. TT[x][y]="1";
  430. }else {
  431. TT[x][y]="0";
  432. }
  433. }else {
  434. int pos2=clausulinhas.indexOf(var)+1+variaveis.size();
  435. int pos=clausulinhas.indexOf(clau2)+1+variaveis.size();
  436. if(TT[x][pos].equals("0")||TT[x][pos2].equals("1")) {
  437. TT[x][y]="1";
  438. }else {
  439. TT[x][y]="0";
  440. }
  441. }
  442. }else if(op.equals("<")) {
  443. int pos=clausulinhas.indexOf(var)+1+variaveis.size();
  444. int pos2=clausulinhas.indexOf(clau2)+1+variaveis.size();
  445. if(TT[x][pos].equals(TT[x][pos2])) {
  446. TT[x][y]="1";
  447. }else {
  448. TT[x][y]="0";
  449. }
  450. }else if(op.equals("&")) {
  451. int pos=clausulinhas.indexOf(var)+1+variaveis.size();
  452. int pos2=clausulinhas.indexOf(clau2)+1+variaveis.size();
  453. if(TT[x][pos].equals("1")&&TT[x][pos2].equals("1")) {
  454. TT[x][y]="1";
  455. }else {
  456. TT[x][y]="0";
  457. }
  458. }else if(op.equals("v")) {
  459. int pos=clausulinhas.indexOf(var)+1+variaveis.size();
  460. int pos2=clausulinhas.indexOf(clau2)+1+variaveis.size();
  461. if(TT[x][pos].equals("0")&&TT[x][pos2].equals("0")) {
  462. TT[x][y]="0";
  463. }else {
  464. TT[x][y]="1";
  465. }
  466. }
  467. }
  468. }
  469. }
  470. }
  471. }
  472. //printa a matriz
  473. for(int x=0;x<((int) Math.pow(2, numVariaveis)+1);x++) {
  474. for(int y=0;y<(numClausulas+numVariaveis+1);y++) {
  475. if((y>numVariaveis)&&(x>0)) {
  476. for(int i=1;i<TT[0][y].length();i++) {
  477. System.out.print(" ");
  478. }
  479. System.out.print(TT[x][y]+" ");
  480. }else {
  481. System.out.print(TT[x][y]+" ");
  482. }
  483. }
  484. System.out.println();
  485. }
  486. //checa se é satisfatível
  487. boolean sat=false;
  488. for(int x=0;x<((int) Math.pow(2, numVariaveis)+1);x++) {
  489. int j=0;
  490. for(int y=0;y<(numClausulas+numVariaveis+1);y++) {
  491. if(TT[x][numClausulas+numVariaveis]=="1") {
  492. sat=true;
  493. }
  494. if(numClausulas==0) {
  495. sat=true;
  496. }
  497. }
  498. }
  499. if(sat==true) {
  500. System.out.println("Sim, é satisfatível.");
  501. }else {
  502. System.out.println("Não, não é satisfatível.-----------------------------------------------------------------------------------------------------");
  503. }
  504. return TT;
  505. }
  506. }
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!