Zápočet 18.1.2008 10:00

Pokročilé vlastnosti jazyka C++, jejich použití pro objektové programování. Dědičnost, virtuální metody, Dynamická alokace. Šablony, generické programování, kompilační polymorfismus. Výjimky. Objektové knihovny, uživatelské kontejnery a iterátory, návrhové vzory. Nízkoúrovňové implementační techniky a konstrukce.
Uživatelský avatar
Yawgmoth
Matfyz(ák|ačka) level I
Příspěvky: 24
Registrován: 17. 5. 2007 20:09
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Zápočet 18.1.2008 10:00

Příspěvek od Yawgmoth »

Příklad zadával Ondřej Šerý
Na příkazové řádce přijde jeden parametr - jméno souboru
Soubor obsahuje jednu řádku s booleovským výrazem složeným z jednopísmenkových proměnných, & , | , !, -> , <->, ( a ). Mezi každou dvojicí těchto entit byla právě jedna mezera a mohli jsme počítat s korektním vstupem -> načítání bylo velmi jednoduché

úkolem bylo převést zadaný výraz do konjunktivně normální formy (CNF) a tu vypsat na standardní výstup - nejprve nám bylo pečlivě vysvětleno co to je CNF (zjednodušeně když udělám strom výrazu tak žádný podvýraz výrazu typu OR neobsahuje AND a negace jsou jen u proměnných .. a to maximálně jedna negace, žádné !!!!!x) a napovězeno jak se toho dá dosáhnout (tj pár vzorečků na převody, šlo by je i vymyslet samostatně a pro mě by to bývalo lepší, protože jsem si je špatně opsal a pak se divil ...)

dostali jsme sadu testovacích dat (8 souborů) na kterých pak bylo potřeba program předvést. K testovacím příkladům jsme neměli řešení tj pro ověření funkčnosti programu to pomáhalo jen málo, ale aspoň něco .)

času na to bylo 3 hodiny, šlo to stihnout, skoro bych to označil za jedno z lehčích zadání, co jsem tu tak četl :)
jestli nastavoval čas netuším .. večer kdyžtak přiložím řešení
Zanatic
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 15. 1. 2007 16:16
Typ studia: Informatika Bc.
Bydliště: Prosek
Kontaktovat uživatele:

Re: Zápočet 18.1.2008 10:00

Příspěvek od Zanatic »

Nastavoval 15 minut. S nějakým řešením přišla většina.
KVÍK!
Uživatelský avatar
Yawgmoth
Matfyz(ák|ačka) level I
Příspěvky: 24
Registrován: 17. 5. 2007 20:09
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Zápočet 18.1.2008 10:00

Příspěvek od Yawgmoth »

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;
}
Odpovědět

Zpět na „PRG032 Objektově orientované programování“