zápočet 01.02.2007

Uživatelský avatar
gofry
Matfyz(ák|ačka) level I
Příspěvky: 49
Registrován: 13. 1. 2006 23:41

zápočet 01.02.2007

Příspěvek od gofry »

Dnešný zápočet bol triviálny. Niečo ako interpret veľmi jednoduchého jazyka, ktorý sa skladal z nasledujúcich príkazov:

Kód: Vybrat vše

=N
//na zásobník sa vložilo číslo N

Kód: Vybrat vše

:Navestie
//označuje nejaké návestie v programe, nie je to teda skutočná inštrukcia

Kód: Vybrat vše

JZ Navestie
//vyberie jedno číslo zo zásobníka a ak je to nula, tak skočí na dané návestie, inak nerobí nič (tj. pokračuje sa vo vykonávaní kódu)

Kód: Vybrat vše

J Navestie
//skočí na Navestie a odtiaľ pokračuje vo vykonávaní kódu

Kód: Vybrat vše

-
//Vyberie dva prvky zo zásobníka, od druhého prvku odčíta prvý a výsledok vloží na zásobník. Podobne boli definované ešte násobenie a sčítanie.

Kód: Vybrat vše

KILL
//odstráni hodnotu zo zásobníka.

Kód: Vybrat vše

DUP
//duplikuje hodnotu na zásobníku

Kód: Vybrat vše

SWAP N
//vymení vymení vrchný prvok na zásobníku s N-tým prvkom na zásobníku (počíta sa od nuly, takže prvok s "indexom" N-1)
Po vykonaní všetkých inštrukcií mal program vypísať stav zásobníka.

Testovací kód bol nasledovný:

Kód: Vybrat vše

=10
=1
:LOOP
SWAP 1
DUP
JZ DONE
DUP
=1
-
SWAP 2
*
J LOOP
:DONE
KILL
Konkrétne tento kód počítal faktoriál 10, takže odkontrolovať správnosť si môžete jednoducho.
Ako ďalší testovací súbor Bednárek skúšal zmeniť SWAP 2 (tj. SWAP za mínusom) na SWAP 1 a SWAP 3. Pri SWAP 1 to hodilo nejaké číslo 3010 alebo tak niečo a pri SWAP 3 to malo hodiť chybu, že nedostatok čísel na zásobníku.

Samozrejmosťou je ošetrenie nedostatku počtu čísel na zásobníku. Vstupný súbor sme však mohli považovať za validný.
banan
Matfyz(ák|ačka) level I
Příspěvky: 40
Registrován: 14. 6. 2005 14:50
Typ studia: Informatika Bc.
Bydliště: Troja

Příspěvek od banan »

Este dodam, ze okrem operatora '-' bolo mozne vyuzit i
'*' a '+'. Cisla v prikaze '= N' mohli byt i zaporne
(aspon tak testoval pan Bednarek moj zdrojak).

Na efektivite interpreta nezalezalo - mal vsak vypocitat
10! v rozumnom case (tj tak, aby sa vysledku pan Bednarek
"dockal").

Okrem toho nam pan Bednarek nacrtol mozne sposoby riesenia:
1) nacitat cele do pamate a neustale parsovat a
interpretovat riadky
2) cely program naparseovat do vnutornej pamatovej
reprezentacie a potom vykonat
3) vyuzit nejaku formu inteligentnych instrukcii - nech
sa kazda instrukcia vykona sama

Ja som si zvolil alternativu spolocneho predka pre kazdu
instrukciu s virtualnou metodou exec, ktora instrukciu
vykonala. Priebeh mojho algoritmu:
- presiel som cely skript a nacital som jednotlive navestia
- este raz som presiel cely skript a naparseoval som kazdy
riadok/instrukciu (pri jumpoch som rovno prekonvertoval
nazov navestia na cislo vysledneho riadku)
- spustil som skript a to asi takto:

Kód: Vybrat vše

int ip = 0;

while(ip < instrukcie.size())
	instrukcie[ip]->exec(stack, ip);
Na moje prekvapenie program fungoval bez chyby hned na
prvy pokus.
banan
Matfyz(ák|ačka) level I
Příspěvky: 40
Registrován: 14. 6. 2005 14:50
Typ studia: Informatika Bc.
Bydliště: Troja

Mozne riesenie ulohy

Příspěvek od banan »

Moje riesenie je sice trochu dlhsie, dalo sa vsak napisat za hodku a 40 minut a hned na prvykrat fungovalo (na bugy bitte upozornite):

Kód: Vybrat vše

#include <iostream>
#include <sstream>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>
#include <map>

using namespace std;

struct DbgPrint
{
	template<typename T>
	DbgPrint& operator<<(T& data)
	{
		//cout << data;
		return *this;
	}
} dbg;



class Instrukcia
{
public:
	virtual ~Instrukcia()
	{ }
	virtual bool exec(vector<int> &stack, int &ip) = 0;
};


class SWAP : public Instrukcia
{
	int hlbka;

public:
	SWAP(int operand) : hlbka(operand)
	{ }

	virtual bool exec(vector<int> &stack, int &ip)
	{
		dbg << "exec SWAP at " << ip << "
";

		if(hlbka >= stack.size()){
			cerr << "SWAP: prazdny stack!" << endl;
			return false;
		}

		swap(stack[stack.size() - 1], stack[stack.size() - 1 - hlbka]);
		++ip;

		return true;
	}
};


class DUP : public Instrukcia
{
public:
	virtual bool exec(vector<int> &stack, int &ip)
	{
		dbg << "exec DUP at " << ip << "
";

		if(!stack.size()){
			cerr << "DUP: prazdny stack!" << endl;
			return false;
		}

		stack.push_back(stack.back());
		++ip;

		return true;
	}
};


class J : public Instrukcia
{
	int nextip; // riadok, na kt ma skocit
public:
	J(int nextip) : nextip(nextip)
	{ }

	virtual bool exec(vector<int> &stack, int &ip)
	{
		dbg << "exec J at " << ip << "
";

		ip = nextip;

		return true;
	}
};


class JZ : public Instrukcia
{
	int nextip; // riadok, na kt ma skocit
public:
	JZ(int nextip) : nextip(nextip)
	{ }

	virtual bool exec(vector<int> &stack, int &ip)
	{
		dbg << "exec JZ at " << ip << "
";

		if(!stack.size()){
			cerr << "JZ: prazdny stack!" << endl;
			return false;
		}

		int num = stack.back();
		stack.pop_back();

		if(num == 0)
			ip = nextip;
		else
			++ip;

		return true;
	}
};


class KILL : public Instrukcia
{
public:
	virtual bool exec(vector<int> &stack, int &ip)
	{	
		dbg << "exec KILL at " << ip << "
";

		if(!stack.size()){
			cerr << "KILL: prazdny stack!" << endl;
			return false;
		}

		stack.pop_back();
		++ip;
		return true;
	}
};

class NOP : public Instrukcia
{
public:
	virtual bool exec(vector<int> &stack, int &ip)
	{
		dbg << "exec NOP at " << ip << "
";

		++ip; 
		return true;
	}
};


class PUSH : public Instrukcia
{
	int num;
public:	
	PUSH(int num) : num(num)
	{ }

	virtual bool exec(vector<int> &stack, int &ip)
	{  
		dbg << "exec PUSH at " << ip << "
";

		stack.push_back(num); 
		++ip; 

		return true;	
	}
};

class MATHOP : public Instrukcia
{
public:
	enum Typ {
		plus = '+',
		minus = '-',
		krat = '*'
	};

	MATHOP(Typ operacia): operacia(operacia)
	{ }

	virtual bool exec(vector<int> &stack, int &ip)
	{
		dbg << "exec MATHOP at " << ip << "
";

		if(stack.size() < 2){
			cerr << "MATHOP: malo operandov!" << endl;
			return false;
		}

		int right = stack.back();	
		stack.pop_back();

		int left = stack.back(); 
		stack.pop_back();

		int result;

		if(operacia == plus)
			result = left + right;
		if(operacia == minus)
			result = left - right;
		if(operacia == krat)
			result = left * right;

		stack.push_back(result);

		++ip;

		return true;
	}

private:
	Typ operacia;
};

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------


class CProgram
{
public:
	typedef map<string, int> TypeNavestia;
	typedef vector<Instrukcia *> TypeSkript;

	CProgram() : bInitialized(false)
	{ }

	~CProgram()
	{
		deinit();
	}

	bool load(istream &in)
	{
		deinit();

		TypeNavestia navestia;

		if(!parsenavestia(in, navestia))
			return false;

		in.clear();
		in.seekg(0, ios::beg);

		if(parsecommands(in, navestia)){
			bInitialized = true;
			return true;
		}

		// cleanup:
		deinit();

		return false;
	}

	bool run()
	{
		vector<int> stack;
		int ip = 0; // instruction pointer

		if(!bInitialized)
			return false;

		dbg << "Spustam program ...
";

		// vykonaj program
		while(ip < prog.size()){
			if(!prog[ip]->exec(stack, ip)){
				cerr << "Program vykonal nepovolenu operaciu at 0x" 
					<< hex << setw(8) << setfill('0') << ip << dec << " (" << ip << ")!" << endl;
				return false;
			}
		}

		if(!stack.size()){
			cerr << "Run: Prazdny stack!" << endl;
			return false;
		}

		cout << "Stack: (top) ";

		// zobraz stack
		copy(stack.rbegin(), stack.rend(), ostream_iterator<int>(cout, " "));

		cout << "(bottom)" <<endl;

		return true;
	}


private:

	void deinit()
	{
		for(vector<Instrukcia*>::iterator it = prog.begin();
			it != prog.end(); ++it){
				delete *it;
		}

		prog.clear();

		bInitialized = false;
	}

	bool parsenavestia(istream &in, TypeNavestia &navestia)
	{
		string line;
		int ip = 0; // instruction pointer

		dbg << "Parsenavestia...
";

		while(getline(in, line)){
			size_t pos = line.find(":");

			if(pos != string::npos){
				stringstream ss(line.substr(pos  + 1));
				string str;

				ss >> str;

				navestia[str] = ip;
			}

			ip++;
		}

		return true;
	}

	bool parsecommands(istream &in, TypeNavestia &navestia)
	{
		string line;
		int ip = 0;

		dbg << "Parsecommands...
";

		while(getline(in, line)){
			if(!parsecmd(line, ip, navestia)){
				cerr << "Nepodarilo sa naparseovat riadok: " << ip << endl;
				return false;
			}

			ip++;
		}

		return true;
	}


	bool parsecmd(string line, int ip, TypeNavestia &navestia)
	{
		stringstream ss(line);
		string str;
		int num;
		Instrukcia *pinst = NULL;

		ss >> str;

		if(str.length() <= 0)
			return false;

		if(0 == str.compare("SWAP")){
			dbg << "parse SWAP
";

			stringstream s(line.substr(str.length()));

			if(!(s >> num))
				return false;

			if(num < 0){
				cerr << "Zaporny SWAP" << endl;
				return false;
			}

			pinst = new SWAP(num);
			prog.push_back(pinst);
		} 
		else if(0 == str.compare("DUP")){
			dbg << "parse DUP
";

			pinst = new DUP();
			prog.push_back(pinst);
		}
		else if(0 == str.compare("JZ") || 0 == str.compare("J")){
			dbg << "parse J/JZ
";

			stringstream s(line.substr(str.length()));
			string label;

			s >> label;

			TypeNavestia::iterator it;
			it = navestia.find(label);

			if(it == navestia.end()){
				cerr << "Nezname navestie: " << label << endl;
				return false;
			}

			if(0 == str.compare("JZ"))			
				pinst = new JZ(it->second);
			else
				pinst = new J(it->second);

			prog.push_back(pinst);
		}
		else if(0 == str.compare("KILL")){
			dbg << "parse KILL
";

			pinst = new KILL();
			prog.push_back(pinst);
		}
		// operator
		else{
			switch(str[0]){
			case '+':
			case '-':
			case '*':
				dbg << "parse MATHOP
";

				pinst = new MATHOP((MATHOP::Typ) str[0]);
				prog.push_back(pinst);
				break;

			case ':':
				pinst = new NOP();
				prog.push_back(pinst);
				break;

			case '=':
				dbg << "parse PUSH
";
				{
					stringstream s(line.substr(1));
					if(!(s >> num))
						return false;
				}
				pinst = new PUSH(num);
				prog.push_back(pinst);
				break;

			default:
				return false;
			}
		}

		return true;
	}

	bool bInitialized;
	TypeSkript prog;
};


int main(int argc, char **argv)
{
	ifstream infile;
	istream *pin;

	if(argc < 2)
		pin = &cin;
	else
	{
		infile.open(argv[1]);
//		infile.open("prog.txt");

		if(!infile){
			cerr << "Nepodarilo sa otvorit subor." << endl;
			return -1;
		}

		pin = &infile;
	}

	//// skript vypocita faktorial 10
	//stringstream ss;
	//ss << "= 10
"
	//	<<"= 1
"
	//	<<":loop
"
	//	<<"SWAP 1
"
	//	<<"DUP
"
	//	<<"JZ done
"
	//	<<"DUP
"
	//	<<"=1
"
	//	<<"-
"
	//	<<"SWAP 2
"
	//	<<"*
"
	//	<<"J loop
"
	//	<<":done
"
	//	<<"KILL
";
	//pin = &ss;

	CProgram prog;

	if(!prog.load(*pin)){
		cerr << "Parse error." << endl;
		return -1;
	}

	if(!prog.run()){
		cerr << "Runtime error." << endl;
		return -1;
	}

	return 0;
}
MIKI
Matfyz(ák|ačka) level III
Příspěvky: 186
Registrován: 10. 12. 2004 22:35
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: zápočet 01.02.2007

Příspěvek od MIKI »

gofry píše:

Kód: Vybrat vše

SWAP N
//vymení vymení vrchný prvok na zásobníku s N-tým prvkom na zásobníku (počíta sa od nuly, takže prvok s "indexom" N-1)
No skor by bolo lepsie povedat ze SWAP N vymeni [vrchol] s [vrchol-N] :twisted:
MOTTO-1: Nieje dôležité vedieť ale pochopiť!!!
MOTTO-2: Neuč sa!!! Život ťa naučí. Mňa naučil, že sa mám učiť.
Odpovědět

Zpět na „2006“