Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Ciao a tutti , innanzitutto complimenti per il forum veramente ben fatto, vi pongo subito il mio problema...
dovrei fare un progetto per l uni e questa è la richiesta:
Scrivere un programma ANSI C che acquisisce da tastiera due formule di logica proposizionale
e stabilisce se esse sono equivalenti. Per semplicita, ciascuna formula puo contenere al piu tre
occorrenze di connettivi logici (negazione, disgiunzione, congiunzione, implicazione, doppia im-
plicazione), i quali possono essere rappresentati come singole cifre decimali. Di conseguenza, la
formula puo contenere al piu quattro occorrenze di proposizioni, le quali possono essere rappresen-
tate come singole lettere. Ciascuna formula non deve contenere parentesi, quindi bisogna applicare
le regole di precedenza e associativita.
io ho delle varie idee per risolverlo ma sono molto confuso ....sapreste indicarmi la via giusta da prendere???
Le linee guida sono piuttosto generiche, quindi alcune scelte ti aiuteranno a fare un'implementazione piu' semplice. Una di queste scelte e' probabilmente di usare la notazione prefix per rappresentare la formula (invece di usare la notazione infix piu' comune). Controllerei con il tuo professore se questo e' accettabile. http://en.wikipedia.org/wiki/Polish_notation
Usare la notazione prefix ti permettera' di sviluppare un parser piu' facilmente. Per il parsing il tuo obiettivo e' di prendere una formula e trasformarla in un abstract syntax tree. Ad esempio, AND OR A B C:
AND
/ \
OR C
/ \
A B
Ogni brancia ha come radice il suo operatore (negazione, congiunzione, ecc.) e ha come foglie gli operandi. Ogni brancia dovrebbe avere una funzione che permette di calcolare il valore dell'operazione (ad esempio AND usa &&, OR usa ||, NOT usa ! ecc.).
Per stabilire se due alberi (quindi due formule) X, Y sono equivalenti, se per ogni permutazione nel valori degli operandi di X e Y, X == Y. Se hai due parametri, A e B, dovrai provare le permutazioni per:
X(A, B)
Y(A, B)
X(true, true), X(true, false), X(false, true), X(false, false) e Y(true, true), Y(true, false), Y(false, true), Y(false, false). Se X e Y ritornano lo stesso valore per ogni permutazione, allora sono equivalenti.
Buon divertimento!
Ultima modifica effettuata da pierotofy il 22/12/2013 alle 21:36
Io sto scrivendo lo stesso progetto e volevo aprire un altro post, poi ho visto questo e mi sono accodato. Ho finito quasi tutti gli altri aspetti (acquisizione, validazione, creazione della tabella di verità), il problema rimane come semplificare la formula: purtroppo noi gli alberi li abbiamo appena iniziati in algoritmi e strutture dati (siamo del primo anno), e quindi ne sappiamo poco o niente.
Credo che però utilizzando la notazione polacca, sia essa prefissa o postfissa (inversa), potremmo cavarcela più facilmente: il problema è scrivere un algoritmo che possa convertire la infissa senza parentesi in polacca! Per esempio, data la formula:
a4f2a1b
che nel mio programma corrisponde a:
a <-> f AND a OR b
convertirle in notazione post/prefissa
Potete darci un consiglio? (niente codice pronto chiaramente, solo qualche idea). Grazie e buone feste a tutti!
Ultima modifica effettuata da Kron_Os il 27/12/2013 alle 21:58
No no, il punto di usare la notazione polacca e' che permette di scrivere un parser piu' facilmente! Non devi scrivere un traduttore, semplicemente cambia la tua formula di input (che come utente, digiti tu!).
Invece di dare in input a4f2a1b, gli dai afab124 (postfix), supponendo che l'ordine di precedenza sia: a <-> (f AND (a OR b))
Mannaggia, purtroppo questo non credo ci sia permesso, dobbiamo inserirla per forza in infissa (da qui l'esigenza di "tradurla" per poi agire su di essa)...
OT. è un problema del mio computer / sto impazzendo oppure l'ora di immissione delle risposte nel forum e sballata?
Ultima modifica effettuata da Kron_Os il 27/12/2013 alle 22:52
Sto chiedendo ora al professore, la risposta dovrebbe giungermi in tempi brevi Per ora, grazie della pagina linkatami, forse difficile, ma se mi applico dovrei arrivarci a tradurre l'algoritmo
Ha risposto che se si sceglie di fare così, occorre documentare e motivare la propria decisione nella relazione, quindi credo di essere a posto! Grazie di avermi fatto dubitare!
l'ora e' quella americana ed e' un bug, risolvero' prossima settimana. 
