[PHP] Creeren waarheidstabel

[-W0kk3L-]

Weet iemand hoe ik in PHP een waarheidstabel moet opzetten?
Ik zou graag iets willen fabriceren, waarbij dit:

code:

A OF (B EN C) OF D

Dit oplevert:

code:

A   B   C   D   T/F
0   0   0   0   0
1   0   0   0   1
0   1   0   0   0
1   1   0   0   1
0   0   1   0   0
1   0   1   0   1
0   1   1   0   1
1   1   1   0   1
0   0   0   1   1
1   0   0   1   1
0   1   0   1   1
1   1   0   1   1
0   0   1   1   1
1   0   1   1   1
0   1   1   1   1
1   1   1   1   1

Alleen ik heb geen flauw idee hoe ik moet beginnen. Kan iemand mij op weg helpen?

[Verwijderd]

code:

$tf = $a | ($b & $c) | $d

Zo? Of wil je de waarheidstabel uitprinten? Dan zou ik simpel een counter doen van 0 tot 15 en vervolgens zo de waarden uitlezen bij elke iteratie:

code:

$a = $counter & 1;
$b = $counter & 2;
$c = $counter & 4;
$d = $counter & 8;

En vervolgens de getallen + uitkomst weergeven.

[ Voor 83% gewijzigd door Verwijderd op 13-06-2009 15:36 ]

[-W0kk3L-]

In de uiteindelijke situatie wil ik iedere conditie een keer beslissend laten maken, dus ik heb de waarden iuit de tabel inderdaad wel nodig voor vergelijking.

Deze site toont al waar ik uiteindelijk naartoe wil:
http://stuff.marc-hoersken.de/work/btt/index.php?lang=en
Op basis van dit resultaat wil ik per beslissende conditie de overige situaties identificeren.

[ Voor 40% gewijzigd door -W0kk3L- op 13-06-2009 15:42 ]

[muksie]

Om te beginnen zul je de input moeten parsen, dus waarbij je je input-string omzet in bijv. objecten, zodat je de waarde kunt bepalen. Jou voorbeeld is dan een disjunctie* van 3 subexpressies, namelijk A, B EN C en D. De eerste en derde kunnen eenvoudig bepaald worden, terwijl de tweede dan een conjunctie* van twee subexpressies is.

Vervolgens tel je het aantal verschillende variabelen die er in de expressie voorkomen, en dan loop je alle mogelijke combinaties van invoer bij langs en evalueer je de expressie.

* Een disjunctie betekent dat de subexpressies met OF aan elkaar gekoppeld worden. Als het met EN aan elkaar gekoppeld moet worden, heet het een conjunctie.

[drm]

Wat is nou concreet je probleem?

[NMe]

De meest eenvoudig te bedenken manier is nog een vierdubbel geneste for-loop waarin je in de binnenste loop het zaakje afdrukt. Maar ik zou me graag aansluiten bij drm en willen vragen wat er eigenlijk concreet het probleem is. Wat lukt je niet?

[-W0kk3L-]

Het is meer dat ik niet weet hoe ik moet beginnen. Het aantal condities in een beslissing kan verschillen, dus ik weet dat ik met iteraties moet gaan werken. Waar ik naartoe wil:

- identificeer het beslispunt (dus de hele A OF (B EN C) OF D... of welke string dan ook).
- als ik het aantal condities weet (en dat is volgens mij niet zo moeilijk), dan hiervoor een waarheidstabel maken.
- vanuit deze waarheidstabel wil ik iedere conditie een keer beslissend maken. als A true is, dan moeten B, C en D false zijn (of B of C true kan ook) om A beslissend te maken. En als B beslissend is, dan moet A false zijn, B en C true en D false. Op deze manier wil ik alle condities aflopen.

Deze handelingen zijn is een techniek, genaamd Elementaire Vergelijkingentest, die ik gebruik in mijn vak (testvak). Deze techniek probeer ik te automatiseren. Zie voor mijn handmatige uitleg: http://www.testconsultant...ontwerptechnieken_EVT.pdf. Ik ben dus nu met de stap in de derde kolom van het eerste blad bezig. De voorgaande stappen heb ik. Ook de blanco tabellen zoals in kolom 3, heb ik al. Alleen de eentjes en nulletjes moet ik nog gaan invullen. En daar ben ik dus nog niet uit hoe ik dat moet gaan doen.

[T-MOB]

Ik zou proberen om je input om te zetten naar een PHP-conditie en vervolgens met eval de verschillende opties testen. Het omzetten kan vrij eenvoudig:

PHP:

<?php
$input = 'A OF (B EN C) OF D';

//operators input => PHP-native
$operators = array(
    'OF'    =>  '|',
    'EN'    =>  '&&',
);
$input = str_replace(array_keys($operators), array_values($operators), $input);


//maak PHP-native expressie van input.
$test = preg_replace('/([a-z]+)/i','$expr["$0"]', $input);

//parameters uit input string halen
preg_match_all('/[a-z]+/i', $input, $params);

print $test;
print_r($params); 
?>

Levert op:

$expr["A"] | ($expr["B"] && $expr["C"]) | $expr["D"]
Array
(
    [0] => Array
        (
            [0] => A
            [1] => B
            [2] => C
            [3] => D
        )

)

Je weet dan dus hoeveel parameters er zijn. (array_unique() op $params). Daarnaast kan je eval() gebruiken om de vergelijking op te lossen. Het inbouwen van wat checks is verder nog wel aan te raden.

[eghie]

Deze code is misschien wat handiger. Hier heb je alleen maar een formule voor nodig. Jij mag er zelf layout aan toevoegen:

PHP:

<?php
error_reporting(E_NONE);
function parseFormule($formule, $variables) {
    //validatie
    if (empty($formule) || empty($variables) || !is_array($variables) || count($variables) <= 0)
        return NULL;

    //vervang variables door waarden
    $tformule = str_replace(array_keys($variables), array_values($variables), $formule);

    // kan riskant zijn
    try {
        //risico's elimineren
        $tformule = str_replace(array("\n", "\r", ";"), '', $tformule);
        
        //variablen aan elkaar mogen toch niet, functienamen kunnen er toch niet in voor komen (als geldig php)
        $tformule = preg_replace('/[a-z]+/i', '', $tformule);

        //var_dump($tformule);

        eval('$tres = ' . $tformule . ';');

        if (!isset($tres) || $tres === 0)
            return 0;
        else
            return $tres;
    } catch (Exception $e) {
        return NULL;
    }
}

function getWaarheidstabel($formule) {
    // formule voorbereiden
    $tformule = strtolower(trim($formule));

    preg_match_all('/[a-z]/is', $tformule, $varmatches);

    //array niet geldig
    if (empty($varmatches[0]) || !is_array($varmatches[0]) || count($varmatches[0]) <= 0)
        return NULL;    

    //alleen unieke variablen
    $varmatches = array_unique($varmatches[0]);

    if (count($varmatches) <= 0)
        return NULL;

    $aantal = count($varmatches) * count($varmatches);
    $x = 1;
    for ($i = 1; $i <= $aantal; $i++) {
        $x = 1;
        $variables = array();
        foreach ($varmatches as $var) {
            $variables[$var] = (($i & $x) == 0) ? 0 : 1;
            $x = $x + $x;
        }
        
        echo parseFormule($tformule, $variables);
    }
}

echo getWaarheidstabel('A | (B & C) | D');

?>

Als je de woorden EN en OF wilt gebruiken, gebruik dan een str_replace ofzo. Zie daarvoor ook de code die gepost is door T-MOB.

[-W0kk3L-]

T-MOB schreef op zondag 14 juni 2009 @ 11:19:
Ik zou proberen om je input om te zetten naar een PHP-conditie en vervolgens met eval de verschillende opties testen.

Ik heb de afzonderlijke parameters (condities) al bepaald. Juist bepalen hoe ze onderling verhouden (door een waarheidstabel op te zetten en vervolgens te bepalen wanneer een conditie bepalend is voor de uitkomst zonder dat een andere conditie hier invloed op heeft), dat is de uitdaging waar ik nu mee zit.

[ Voor 26% gewijzigd door -W0kk3L- op 14-06-2009 11:27 ]

[eghie]

-W0kk3L- schreef op zondag 14 juni 2009 @ 11:27:
[...]

Ik heb de afzonderlijke parameters (condities) al bepaald. Juist bepalen hoe ze onderling verhouden (door een waarheidstabel op te zetten en vervolgens te bepalen wanneer een conditie bepalend is voor de uitkomst zonder dat een andere conditie hier invloed op heeft), dat is de uitdaging waar ik nu mee zit.

Lees Kage zijn post eens goed en kijk dan eens naar mijn code.

[-W0kk3L-]

Dit is inderdaad de basis waar ik mee aan de slag wil. Ik heb er al even wat echo's tussen gezet om te begrijpen wat er gebeurt:

code:

1000 true(1)/false(0): 1
0100 true(1)/false(0): 0
1100 true(1)/false(0): 1
0010 true(1)/false(0): 0
1010 true(1)/false(0): 1
0110 true(1)/false(0): 1
1110 true(1)/false(0): 1
0001 true(1)/false(0): 1
1001 true(1)/false(0): 1
0101 true(1)/false(0): 1
1101 true(1)/false(0): 1
0011 true(1)/false(0): 1
1011 true(1)/false(0): 1
0111 true(1)/false(0): 1
1111 true(1)/false(0): 1
0000 true(1)/false(0): 0

Ik snap het stukje vanaf regel 50 t/m 55 nog niet helemaal. Daar zit volgens mij de essentie van het hele verhaal. Toch?

Edit:
Sterker nog, volgens mij is dit het statement wat ik nog niet snap (de rest is volgens mij enkel het vullen van de array met alle mogelijkheden). Kun je deze toelichten?:

code:

$variables[$var] = (($i & $x) == 0) ? 0 : 1;

[ Voor 14% gewijzigd door -W0kk3L- op 14-06-2009 12:48 ]

[NMe]

Je krijgt talloze reacties en gaat alleen aan de slag met die reactie die kant en klare code geeft...

Leg nou eens uit wat je zelf al geprobeerd hebt en waar je tegenaan gelopen bent. Wat is het precies dat je niet lukt? We kunnen wel kant en klare antwoorden geven maar daar leer je niks van.

Voor die ene statement die je denkt niet te snappen: http://nl.php.net/ternary

[-W0kk3L-]

Er zijn twee stappen die ik wil doen:
- het neerzetten van de waarheidstabel
- het beoordelen van een ingevulde waarheidstabel (naar true of false).

De formule zelf, teruggebracht naar losse condities, dat had ik (zoals aangegeven in een reactie) al gerealiseerd. De uitgangssituatie had ik dus al gecreeerd. Bij de eerste vervolgstap liep ik echter vast, omdat ik niet wist hoe ik het aan moest pakken. In dat laatste stukje code staat volgens mij in de genoemde regels hetgeen ik niet wist aan te pakken. En dat is denk ik waar mijn laatste vraag over gaat. Wat gebeurt er in deze stap, waarom en waarom op deze manier. Ik probeer dus te begrijpen waarom iets gebeurt.

Voor die ene statement die je denkt niet te snappen: http://nl.php.net/ternary

Daar ga ik nu naar kijken of ik het snap.

[eghie]

-W0kk3L- schreef op zondag 14 juni 2009 @ 12:40:
Dit is inderdaad de basis waar ik mee aan de slag wil. Ik heb er al even wat echo's tussen gezet om te begrijpen wat er gebeurt:

code:

1000 true(1)/false(0): 1
0100 true(1)/false(0): 0
1100 true(1)/false(0): 1
0010 true(1)/false(0): 0
1010 true(1)/false(0): 1
0110 true(1)/false(0): 1
1110 true(1)/false(0): 1
0001 true(1)/false(0): 1
1001 true(1)/false(0): 1
0101 true(1)/false(0): 1
1101 true(1)/false(0): 1
0011 true(1)/false(0): 1
1011 true(1)/false(0): 1
0111 true(1)/false(0): 1
1111 true(1)/false(0): 1
0000 true(1)/false(0): 0

Ik snap het stukje vanaf regel 50 t/m 55 nog niet helemaal. Daar zit volgens mij de essentie van het hele verhaal. Toch?

Edit:
Sterker nog, volgens mij is dit het statement wat ik nog niet snap (de rest is volgens mij enkel het vullen van de array met alle mogelijkheden). Kun je deze toelichten?:

code:

$variables[$var] = (($i & $x) == 0) ? 0 : 1;

Dat laatste is inderdaad het cruciale stuk, om de variablen te setten op 0 of 1. Ik ga je niet uitleggen wat er gebeurd. Dit mag je zelf uitvogelen.

Die code die ik gepost heb, is 1 van de vele manieren om dit op te lossen. Hier laat ik PHP het uitvogelen, over de structuur van de vergelijking. Je zou het ook anders kunnen oplossen. Je zou ook, zoals je zelf in gedachte had, de structuur van de vergelijking zelf kunnen parsen.

Gebruik de volgende links als referentie om te kijken wat die code doet:
http://nl.php.net/manual/en/language.operators.bitwise.php
http://nl.php.net/decbin

[-W0kk3L-]

eghie schreef op zondag 14 juni 2009 @ 13:23:
[...]
Dat laatste is inderdaad het cruciale stuk, om de variablen te setten op 0 of 1. Ik ga je niet uitleggen wat er gebeurd. Dit mag je zelf uitvogelen.

Klopt mijn uitleg?:
Je gebruikt 4 waarden omdat de beslissing bestaat uit 4 variabelen (bestaande uit 1, 2¹, 2² en 2³ omdat we met het binaire stelsel bezig zijn). Vervolgens match je iedere waarde van 1 t/m 16 (2⁴... correcter zou volgens mij zijn $i = 0, toch?) met die 4. Als ze matchen (!= 0), dan is het true. Zo niet (==0), dan false. Klopt mijn beredenering enigszins? (Misschien is de woordkeuze niet geheel juist, maar de logica volgens mij wel)

Verwijderd schreef op zaterdag 13 juni 2009 @ 15:34:

code:

$a = $counter & 1;
$b = $counter & 2;
$c = $counter & 4;
$d = $counter & 8;

Nu snap ik dit ook eindelijk.

[PrisonerOfPain]

eghie schreef op zondag 14 juni 2009 @ 11:24:
Deze code is misschien wat handiger. Hier heb je alleen maar een formule voor nodig. Jij mag er zelf layout aan toevoegen:

Als je de woorden EN en OF wilt gebruiken, gebruik dan een str_replace ofzo. Zie daarvoor ook de code die gepost is door T-MOB.

Moet je voor $aantal niet 1 << count($varmatches) hebben? Er zijn namelijk 2ⁿ combinaties mogelijk, niet n².

[-W0kk3L-]

Correct. Dat verschil zie je toevallig niet bij 4 condities, aangezien ze beiden 16 situaties opleveren. Ik liep er al tegenaan bij de 5e conditie.

[eghie]

PrisonerOfPain schreef op zondag 14 juni 2009 @ 14:42:
[...]


Moet je voor $aantal niet 1 << count($varmatches) hebben? Er zijn namelijk 2ⁿ combinaties mogelijk, niet n².

DOH! Thnx voor de oplettendheid.

-W0kk3L- schreef op zondag 14 juni 2009 @ 13:52:
[...]


Klopt mijn uitleg?:
Je gebruikt 4 waarden omdat de beslissing bestaat uit 4 variabelen (bestaande uit 1, 2¹, 2² en 2³ omdat we met het binaire stelsel bezig zijn). Vervolgens match je iedere waarde van 1 t/m 16 (2⁴... correcter zou volgens mij zijn $i = 0, toch?) met die 4. Als ze matchen (!= 0), dan is het true. Zo niet (==0), dan false. Klopt mijn beredenering enigszins? (Misschien is de woordkeuze niet geheel juist, maar de logica volgens mij wel)


[...]

Nu snap ik dit ook eindelijk.

$i=0; klopt. Was niet echt aan het nadenken. Maar opzich heb je dat goed gevonden. Maar houdt er rekening mee dat de functie parseFormule() de vergelijking uiteindelijk uitvoert. Die loop vult eigenlijk de variablen met 0 of 1. Die ternary (verkorte if statement), zorgt ervoor dat hij de bits matched van $i en $x. Wanneer er geen bit matched of wanneer beide bits 0 zijn, komt er 0 uit. Gebruik het voorbeeld stukje om die bitwise and te testen, op deze pagina: http://nl.php.net/manual/en/language.operators.bitwise.php Dan zie je zelf wat er eigenlijk gebeurd met die vergelijking.

$x = $x + $x;, kan ook $x = $x << 1; of $x *= 2; zijn.

[ Voor 69% gewijzigd door eghie op 14-06-2009 15:50 ]

[-W0kk3L-]

Ik kan weer verder. Mijn dank is groot voor deze toelichtingen!

[PrisonerOfPain]

eghie schreef op zondag 14 juni 2009 @ 15:14:
[...]

DOH! Thnx voor de oplettendheid.

Oh, ik liep er zelf ook tegen aan met het maken van een C++ implementatie

[NMe]

De makkelijkste manier is trouwens nog altijd deze:

PHP:

echo 'A   B   C   D   (A || (B && C) || D)';
for ($a = 0; $a <= 1; $a++)
  for ($b = 0; $b <= 1; $b++)
    for ($c = 0; $c <= 1; $c++)
      for ($d = 0; $d <= 1; $d++)
      {
        $tmp = $a || ($b && $c) || $d;
        echo "$a   $b   $c   $d         $tmp";
      }

Microoptimalisaties zijn leuk om over na te denken maar voor zoiets als dit is een genest loopje net zo eenvoudig.