Provera da li je dati logički izraz tautologija

Provera da li je dati logički izraz tautologija

offline
  • Pridružio: 30 Sep 2013
  • Poruke: 12

Pravim neki program koji treba da određuje da li je izraz tautologija, kontradikcija ili zadovoljiva.
I sada, lepo radi u nekom slučajevima kada treba redom da određuje ali kada treba da ispoštuje pravila prednosti tipa recimo u primeru
(p||q=>r)<=>(p=>r)&&(q=>r)
prvo će da radi (p||q=>r)<=>(p=>r)
pa tek ostalo a meni treba da odradi prvo (p||q=>r) pa (p=>r)&&(q=>r) i tek onda ekvivalenciju.
Recimo tako bi računalo 4+3*2 = 14
Rađeno je preko obrnute poljske notacije. Ako neko zna šta dodati kodu i gde(još sam slab sa javom a trebam da predam ovo ubrzo).

import java.util.ArrayList; import java.util.HashMap; import java.util.Stack; import java.util.regex.Matcher; import java.util.regex.Pattern; public class ReversePolishNotation {    // Spisak operatora    public static final String[] OPERATORS = { "=>", "<=>", "&&", "||", "^",          "(", ")", "^" };    public static boolean evaluate(String expression,          HashMap<String, Boolean> values) {       // Dodaje default 0 i 1 vrednosti u slucaju negacije samo jedne vrednost       values.put("0", false);       values.put("1", true);       // Uklanja sve razmake       expression = expression.replaceAll("\\s+", "");       // Pretraga karaktera za negaciju i zamenja njegovom default obrnutom       // vrednoscu       Pattern PATTERN = Pattern.compile("\\^[A-Za-z0-9]");       Matcher m = PATTERN.matcher(expression);       while (m.find()) {          String s = m.group(0).substring(1, 2);          if (values.get(s) == false)             expression = expression.replaceAll("\\^[A-Za-z0-9]", "1");          else             expression = expression.replaceAll("\\^[A-Za-z0-9]", "0");       }       // Regularni izraz za splitovanje zadatog izraza po operatorima       String regex = "((?<=\\))|(?=\\)))|((?<=\\()|(?=\\())|((?<=\\b\\w+\\b)|(?=\\b\\w+\\b))";       String[] tokens = expression.split(regex);       Stack<String> operators = new Stack<String>();       Stack<Boolean> operands = new Stack<Boolean>();       ArrayList<String> output = new ArrayList<String>();       for (String clan : tokens) {          if (!clan.equals(")")) {             if (isOperator(clan))                operators.push(clan);             else                output.add(clan);          } else {             while (operators.peek().equals("(") == false) {                output.add(operators.pop());             }             operators.pop();          }       }       // Racunanje and shit       while (operators.size() != 0) {          output.add(operators.pop());       }       for (String item : output) {          if (!isOperator(item)) {             operands.push(values.get(item));          } else if (item.equals("=>")) {             boolean item1 = operands.pop();             boolean item2 = operands.pop();             if (item2 == true && item1 == false)                operands.push(false);             else                operands.push(true);          } else if (item.equals("&&")) {             boolean item1 = operands.pop();             boolean item2 = operands.pop();             if (item1 == true && item2 == true)                operands.push(true);             else                operands.push(false);          }          else if (item.equals("||")) {             boolean item1 = operands.pop();             boolean item2 = operands.pop();             if (item1 == true || item2 == true)                operands.push(true);             else                operands.push(false);          }          else if (item.equals("^")) {             boolean item1 = operands.pop();             operands.push(!item1);          }          else if (item.equals("<=>")) {             boolean item1 = operands.pop();             boolean item2 = operands.pop();             if (item1 == item2)                operands.push(true);             else                operands.push(false);          }       }       return operands.pop();    }    private static boolean isOperator(String s) {       for (String operator : OPERATORS) {          if (s.equals(operator))             return true;       }       return false;    } }



Registruj se da bi učestvovao u diskusiji. Registrovanim korisnicima se NE prikazuju reklame unutar poruka.
offline
  • Milan
  • Pridružio: 17 Dec 2007
  • Poruke: 14809
  • Gde živiš: Niš

Po svemu sudeći, ne valja ti konverzija iz infiksne u prefiksnu notaciju. Moraš da poštuješ prioritete operatora, a ne vidim da bilo gde to radiš. Trebalo bi da negde na računaru imam primere ovakve konverzije, samo sa aritmetičkim operatorima. Pogledaću kad stignem pa javljam.

Šta misliš o korišćenju stabla za rešavanje zadatka? Mislim da bi olakšala posao.



offline
  • Pridružio: 30 Sep 2013
  • Poruke: 12

baš sam tanak sa javom, sve što nije kod mi ne znači previše Very Happy

offline
  • Milan
  • Pridružio: 17 Dec 2007
  • Poruke: 14809
  • Gde živiš: Niš

Ma, problematika je totalno nezavisna od jezika. Algoritam je maltene isti ma koji jezik da je u pitanju. Very Happy Ovo što ja imam je pisano u C++.

offline
  • Pridružio: 30 Sep 2013
  • Poruke: 12

pošalji Very Happy

offline
  • Milan
  • Pridružio: 17 Dec 2007
  • Poruke: 14809
  • Gde živiš: Niš

Tražio sam, ali ne nađoh ovo. Znam da sam radio obe konverzije, i u prefiksnu i u postfiksnu notaciju, ali ko zna gde se to zaturilo. Confused

Ko je trenutno na forumu
 

Ukupno su 1369 korisnika na forumu :: 29 registrovanih, 9 sakrivenih i 1331 gosta   ::   [ Administrator ] [ Supermoderator ] [ Moderator ] :: Detaljnije

Najviše korisnika na forumu ikad bilo je 3466 - dana 01 Jun 2021 17:07

Korisnici koji su trenutno na forumu:
Korisnici trenutno na forumu: _Rade, bladesu, debeli, DeerHunter, dragoljub11987, ekser222, Georgius, kjkszpj, Krusarac, Kubovac, lord sir giga, Lucije Kvint, marsovac 2, Mcdado, Mercury, Mihajlo, milan.vukovic, milos.cbr, nemkea71, Panter, Parker, RiV, S2M, slonic_tonic, ss10, Volkhov-M, yufighter, Zandar, 79693