od Yawgmoth » 18. 1. 2008 21:08
trochu jsem to osekal od ruzneho balastu a nechal jen to nejdulezitejsi pro funkcnost ... nicmene nebrat zrovna jako ukazku hezkeho kodu
) .. hm, nejak ted nechapu proc jsem si dal tu praci s odstranovanim veci ktere to zprehlednovaly, ale tak aspon to mate kratsi
princip slovy: klasicky prevod vyrazu na strom pomoci dvou zasobniku, tak jak jdou na vstupu hazeme do jednoho zasobniku cleny, do druheho operatory. Jelikoz jsou tu velmi jednoduche priority staci vzdy po pridani clena do zasobniku zkusit zpracovat vrchni operator. Jediny operator ktery se nemuze vykonat okamzite je zavorka, ta ceka na uzaviraci zavorku (ktera prijde v okamziku kdy je ta otviraci znovu navrchu a odstrani ji). Pri zpracovani operatoru konvertujeme -> a <-> na & a |, vsechny negace propagujeme smerem do listu grafu a pri tom stejne jako pri zpracovavani ostatnich operatoru kontrolujeme podminky konjuktivne normalni formy (pokud v aktualnim clenu je | tak v zadnem z potomku neni &)
Kód: Vybrat vše
#include <fstream>
#include <iostream>
#include <stack>
#include <string>
using namespace std;
struct clen {
bool promenna;
bool negace;
char znak;
clen * levy;
clen * pravy;
clen(char z) : promenna(true), znak(z), negace(false), levy(0), pravy(0) {};
clen(clen * cl1, clen * cl2, char z) : levy(cl1), pravy(cl2), znak(z), promenna(false), negace(false) {};
clen(clen * vzor) {
promenna = vzor->promenna;
negace = vzor->negace;
znak = vzor->znak;
levy = vzor->levy ? new clen(vzor->levy) : 0;
pravy = vzor->pravy ? new clen(vzor->pravy) : 0;
}
void neguj() {
if(promenna)negace = !negace;
else {
znak = (znak=='&') ? '|' : '&';
levy->neguj();
pravy->neguj();
if(znak=='|') normalizuj();
}
}
void normalizuj() {
if(znak!='|') return;
if( (levy->promenna || (levy->znak!='&')) && (pravy->promenna || (pravy->znak!='&')) ) return;
if(levy->promenna) {
clen * tmp = levy;
levy = pravy;
pravy = tmp;
}
// (a & b) | c == (a | c) & (b | c)
clen * kopie = new clen(pravy);
pravy = new clen(levy->pravy,pravy,'|');
levy->znak='|';
levy->pravy = kopie;
znak = '&';
levy->normalizuj();
pravy->normalizuj();
}
};
ostream & operator<<(ostream & vystup, clen * cl) {
if(!cl->promenna) vystup << "( " << cl->levy;
if(cl->negace) vystup << "!";
vystup << cl->znak << " ";
if(!cl->promenna) vystup << cl->pravy << ") ";
return vystup;
}
int main(int argc, char * argv[])
{
ifstream f;
stack<char> zasobnikOperatoru;
stack<clen*> zasobnikClenu;
string tmp;
char c;
clen * cl1, * cl2, * cl;
size_t zpracovatOperator;
f.open(argv[1]);
while(f >> tmp) {
c = tmp[0];
if(strchr("&|!-<(",c)) {
zasobnikOperatoru.push(c);
continue;
} else if(c==')')zasobnikOperatoru.pop();
else zasobnikClenu.push(new clen(c));
zpracovatOperator = zasobnikOperatoru.size();
while(zpracovatOperator--) {
char c = zasobnikOperatoru.top();
if(c=='!') {
zasobnikClenu.top()->neguj();
zasobnikOperatoru.pop();
} else if(strchr("&|-<",c)) {
cl2 = zasobnikClenu.top();
zasobnikClenu.pop();
cl1 = zasobnikClenu.top();
zasobnikClenu.pop();
if(c=='-') { //x -> y == !x | y
cl1->neguj();
c='|';
}
if(c=='<') { // x<->y == (!x |y) & (!y |x)
cl = new clen(new clen(cl1),cl2,'|');
cl->levy->neguj();
cl->normalizuj();
cl2 = new clen(new clen(cl2),cl1,'|');
cl2->levy->neguj();
cl2->normalizuj();
cl1 = cl;
c = '&';
}
cl = new clen(cl1,cl2,c);
cl->normalizuj();
zasobnikClenu.push(cl);
zasobnikOperatoru.pop();
} else zpracovatOperator = 0;
}
}
cout << zasobnikClenu.top();
return 0;
}
trochu jsem to osekal od ruzneho balastu a nechal jen to nejdulezitejsi pro funkcnost ... nicmene nebrat zrovna jako ukazku hezkeho kodu :-)) .. hm, nejak ted nechapu proc jsem si dal tu praci s odstranovanim veci ktere to zprehlednovaly, ale tak aspon to mate kratsi :-)
princip slovy: klasicky prevod vyrazu na strom pomoci dvou zasobniku, tak jak jdou na vstupu hazeme do jednoho zasobniku cleny, do druheho operatory. Jelikoz jsou tu velmi jednoduche priority staci vzdy po pridani clena do zasobniku zkusit zpracovat vrchni operator. Jediny operator ktery se nemuze vykonat okamzite je zavorka, ta ceka na uzaviraci zavorku (ktera prijde v okamziku kdy je ta otviraci znovu navrchu a odstrani ji). Pri zpracovani operatoru konvertujeme -> a <-> na & a |, vsechny negace propagujeme smerem do listu grafu a pri tom stejne jako pri zpracovavani ostatnich operatoru kontrolujeme podminky konjuktivne normalni formy (pokud v aktualnim clenu je | tak v zadnem z potomku neni &)
[code]
#include <fstream>
#include <iostream>
#include <stack>
#include <string>
using namespace std;
struct clen {
bool promenna;
bool negace;
char znak;
clen * levy;
clen * pravy;
clen(char z) : promenna(true), znak(z), negace(false), levy(0), pravy(0) {};
clen(clen * cl1, clen * cl2, char z) : levy(cl1), pravy(cl2), znak(z), promenna(false), negace(false) {};
clen(clen * vzor) {
promenna = vzor->promenna;
negace = vzor->negace;
znak = vzor->znak;
levy = vzor->levy ? new clen(vzor->levy) : 0;
pravy = vzor->pravy ? new clen(vzor->pravy) : 0;
}
void neguj() {
if(promenna)negace = !negace;
else {
znak = (znak=='&') ? '|' : '&';
levy->neguj();
pravy->neguj();
if(znak=='|') normalizuj();
}
}
void normalizuj() {
if(znak!='|') return;
if( (levy->promenna || (levy->znak!='&')) && (pravy->promenna || (pravy->znak!='&')) ) return;
if(levy->promenna) {
clen * tmp = levy;
levy = pravy;
pravy = tmp;
}
// (a & b) | c == (a | c) & (b | c)
clen * kopie = new clen(pravy);
pravy = new clen(levy->pravy,pravy,'|');
levy->znak='|';
levy->pravy = kopie;
znak = '&';
levy->normalizuj();
pravy->normalizuj();
}
};
ostream & operator<<(ostream & vystup, clen * cl) {
if(!cl->promenna) vystup << "( " << cl->levy;
if(cl->negace) vystup << "!";
vystup << cl->znak << " ";
if(!cl->promenna) vystup << cl->pravy << ") ";
return vystup;
}
int main(int argc, char * argv[])
{
ifstream f;
stack<char> zasobnikOperatoru;
stack<clen*> zasobnikClenu;
string tmp;
char c;
clen * cl1, * cl2, * cl;
size_t zpracovatOperator;
f.open(argv[1]);
while(f >> tmp) {
c = tmp[0];
if(strchr("&|!-<(",c)) {
zasobnikOperatoru.push(c);
continue;
} else if(c==')')zasobnikOperatoru.pop();
else zasobnikClenu.push(new clen(c));
zpracovatOperator = zasobnikOperatoru.size();
while(zpracovatOperator--) {
char c = zasobnikOperatoru.top();
if(c=='!') {
zasobnikClenu.top()->neguj();
zasobnikOperatoru.pop();
} else if(strchr("&|-<",c)) {
cl2 = zasobnikClenu.top();
zasobnikClenu.pop();
cl1 = zasobnikClenu.top();
zasobnikClenu.pop();
if(c=='-') { //x -> y == !x | y
cl1->neguj();
c='|';
}
if(c=='<') { // x<->y == (!x |y) & (!y |x)
cl = new clen(new clen(cl1),cl2,'|');
cl->levy->neguj();
cl->normalizuj();
cl2 = new clen(new clen(cl2),cl1,'|');
cl2->levy->neguj();
cl2->normalizuj();
cl1 = cl;
c = '&';
}
cl = new clen(cl1,cl2,c);
cl->normalizuj();
zasobnikClenu.push(cl);
zasobnikOperatoru.pop();
} else zpracovatOperator = 0;
}
}
cout << zasobnikClenu.top();
return 0;
}
[/code]