Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Aiuto Programma Formula logica proposizionale
Forum - C/C++ - Aiuto Programma Formula logica proposizionale

Avatar
juanito (Normal User)
Newbie


Messaggi: 1
Iscritto: 22/12/2013

Segnala al moderatore
Postato alle 13:50
Domenica, 22/12/2013
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???

PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6116
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 21:31
Domenica, 22/12/2013
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


Seguimi su Twitter: http://www.twitter.com/pierotofy

Fai quello che ti piace, e fallo bene.
PM Quote
Avatar
Kron_Os (Normal User)
Newbie


Messaggi: 8
Iscritto: 17/12/2013

Segnala al moderatore
Postato alle 21:53
Venerdì, 27/12/2013
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


"tu che mi leggi sei sicuro di intendere la mia lingua?"
PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6116
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 22:21
Venerdì, 27/12/2013
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))



Seguimi su Twitter: http://www.twitter.com/pierotofy

Fai quello che ti piace, e fallo bene.
PM Quote
Avatar
Kron_Os (Normal User)
Newbie


Messaggi: 8
Iscritto: 17/12/2013

Segnala al moderatore
Postato alle 22:50
Venerdì, 27/12/2013
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


"tu che mi leggi sei sicuro di intendere la mia lingua?"
PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6116
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 23:24
Venerdì, 27/12/2013
Testo quotato


purtroppo questo non credo ci sia permesso



Credi oppure sai? La traccia non lo precisa, quindi non vedo perche' no.

:ot: l'ora e' quella americana ed e' un bug, risolvero' prossima settimana.


Seguimi su Twitter: http://www.twitter.com/pierotofy

Fai quello che ti piace, e fallo bene.
PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6116
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 23:57
Venerdì, 27/12/2013
Se proprio devi usare notazione infix, una buona spiegazione di come creare l'albero e' scritta qui (la prima risposta: http://stackoverflow.com/questions/13853774/infix-calculat ... )


Seguimi su Twitter: http://www.twitter.com/pierotofy

Fai quello che ti piace, e fallo bene.
PM Quote
Avatar
Kron_Os (Normal User)
Newbie


Messaggi: 8
Iscritto: 17/12/2013

Segnala al moderatore
Postato alle 10:22
Sabato, 28/12/2013
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


"tu che mi leggi sei sicuro di intendere la mia lingua?"
PM Quote
Avatar
Kron_Os (Normal User)
Newbie


Messaggi: 8
Iscritto: 17/12/2013

Segnala al moderatore
Postato alle 10:14
Domenica, 29/12/2013
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! ;)


"tu che mi leggi sei sicuro di intendere la mia lingua?"
PM Quote