From bc8b5b446a6a2d37bae82e7ad20e31e1439a2f0b Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Sun, 24 May 2020 16:58:23 +0200 Subject: feat: add more exercises --- I_anno/Programmazione_2/exercises/dequeue.cc | 137 +++++++++++++++++++++++++ I_anno/Programmazione_2/exercises/doppioni.cc | 77 ++++++++++++++ I_anno/Programmazione_2/exercises/pop-stack.cc | 132 ++++++++++++++++++++++++ 3 files changed, 346 insertions(+) create mode 100644 I_anno/Programmazione_2/exercises/dequeue.cc create mode 100644 I_anno/Programmazione_2/exercises/doppioni.cc create mode 100644 I_anno/Programmazione_2/exercises/pop-stack.cc (limited to 'I_anno/Programmazione_2/exercises') diff --git a/I_anno/Programmazione_2/exercises/dequeue.cc b/I_anno/Programmazione_2/exercises/dequeue.cc new file mode 100644 index 0000000..4b012c4 --- /dev/null +++ b/I_anno/Programmazione_2/exercises/dequeue.cc @@ -0,0 +1,137 @@ + +#include +#include + +using namespace std; + +template +class node { +public: + node(T key, node* next) : _key{key}, _next{next} {} + node(T key) : _key{key}, _next{nullptr} {} + const T& key() const { return _key; } + T& key() { return _key; } + const node*& next() const { return _next; } + node*& next() { return _next; } +private: + T _key; + node* _next; +}; + +template +class Coda { +public: + Coda() : _head{nullptr}, _tail{nullptr} {} + ~Coda() { + + } + Coda* enqueue(T val) { + if(!_head) { + _head = new node{val, nullptr}; + _tail = _head; + } else { + _tail->next() = new node{val, nullptr}; + _tail = _tail->next(); + } + + return this; + } + node* dequeue() { + if(!_head) return nullptr; + node* elem = _head; + delete _head; + _head = elem->next(); + + return elem; + } + + bool is_empty() { return _head == nullptr; } +private: + node* _head; + node* _tail; +}; + +int main() { + ifstream in("input.txt"); + ofstream out("output.txt"); + + for(int ts = 0; ts < 100; ++ts) { + string t; + int n; + in >> t; + switch(t.at(0)) { + case 'b': { + Coda* queue = new Coda{}; + in >> n; + string s; + for(int i = 0; i < n; ++i) { + in >> s; + if(s.at(0) == 'i') { + queue->enqueue(s.at(1) - '0'); + } else { + queue->dequeue(); + } + } + while(!queue->is_empty()) + out << queue->dequeue()->key() << ' '; + out << endl; + break; + } + case 'd': { + Coda* queue = new Coda{}; + in >> n; + string s; + for(int i = 0; i < n; ++i) { + in >> s; + if(s.at(0) == 'i') { + queue->enqueue(stod(s.substr(1, s.length()-1))); + } else { + queue->dequeue(); + } + } + while(!queue->is_empty()) + out << queue->dequeue()->key() << ' '; + out << endl; + break; + } + case 'c': { + Coda* queue = new Coda{}; + in >> n; + string s; + for(int i = 0; i < n; ++i) { + in >> s; + if(s.at(0) == 'i') { + queue->enqueue(s.at(1)); + } else { + queue->dequeue(); + } + } + while(!queue->is_empty()) + out << queue->dequeue()->key() << ' '; + out << endl; + break; + } + case 'i': { + Coda* queue = new Coda{}; + in >> n; + string s; + for(int i = 0; i < n; ++i) { + in >> s; + if(s.at(0) == 'i') { + queue->enqueue(stoi(s.substr(1, s.length()-1))); + } else { + queue->dequeue(); + } + } + while(!queue->is_empty()) + out << queue->dequeue()->key() << ' '; + out << endl; + break; + } + } + } + in.close(); + out.close(); + return 0; +} + diff --git a/I_anno/Programmazione_2/exercises/doppioni.cc b/I_anno/Programmazione_2/exercises/doppioni.cc new file mode 100644 index 0000000..fdd3e88 --- /dev/null +++ b/I_anno/Programmazione_2/exercises/doppioni.cc @@ -0,0 +1,77 @@ +#include +#include + +using namespace std; + +template +class node { +public: + node(T key, node* parent, node* right, node* left) : _key{key}, _parent{parent}, _right{right}, _left{left} {} + T& key() { return _key; } + const T& key() const { return _key; } + node*& parent() { return _parent; } + const node*& parent() const { return _parent; } + node*& right() { return _right; } + const node*& right() const { return _right; } + node*& left() { return _left; } + const node*& left() const { return _left; } +private: + T _key; + node* _parent; + node* _right; + node* _left; +}; + +class bst { +public: + bst() : _duplicates{0}, _root{nullptr} {} + bst* add(int val) { + node* iter = _root; + node* prev = nullptr; + while(iter) { + prev = iter; + if(iter->key() == val) { + _duplicates++; + return this; + } + + if(iter->key() > val) + iter = iter->right(); + else + iter = iter->left(); + } + + node* nodus = new node{val, prev, nullptr, nullptr}; + if(!prev) + _root = nodus; + else if(prev->key() > val) + prev->right() = nodus; + else + prev->left() = nodus; + + return this; + } + const int& duplicates() const { return _duplicates; } +private: + int _duplicates; + node* _root; +}; + +int main() { + ifstream in("input.txt"); + ofstream out("output.txt"); + for(int ts = 0; ts < 100; ++ts) { + bst* b = new bst{}; + int n; + in >> n; + int e; + for(int i = 0; i < n; ++i) { + in >> e; + b->add(e); + } + out << b->duplicates() << endl; + } + in.close(); + out.close(); + return 0; +} diff --git a/I_anno/Programmazione_2/exercises/pop-stack.cc b/I_anno/Programmazione_2/exercises/pop-stack.cc new file mode 100644 index 0000000..3739450 --- /dev/null +++ b/I_anno/Programmazione_2/exercises/pop-stack.cc @@ -0,0 +1,132 @@ +#include +#include + +using namespace std; + +template +class node { +public: + node(T key, node* next) : _key{key}, _next{next} {} + node(T key) : _key{key}, _next{nullptr} {} + const T& key() const { return _key; } + T& key() { return _key; } + const node*& next() const { return _next; } + node*& next() { return _next; } +private: + T _key; + node* _next; +}; + +template +class Pila { +public: + Pila() : _head{nullptr}{} + ~Pila() { + + } + Pila* push(T val) { + if(!_head) { + _head = new node{val, nullptr}; + } else { + _head = new node{val, _head}; + } + + return this; + } + node* pop() { + if(!_head) return nullptr; + node* elem = _head; + delete _head; + _head = elem->next(); + + return elem; + } + + bool is_empty() { return _head == nullptr; } +private: + node* _head; +}; + +int main() { + ifstream in("input.txt"); + ofstream out("output.txt"); + + for(int ts = 0; ts < 100; ++ts) { + string t; + int n; + in >> t; + switch(t.at(0)) { + case 'b': { + Pila* stack = new Pila{}; + in >> n; + string s; + for(int i = 0; i < n; ++i) { + in >> s; + if(s.at(0) == 'i') { + stack->push(s.at(1) - '0'); + } else { + stack->pop(); + } + } + while(!stack->is_empty()) + out << stack->pop()->key() << ' '; + out << endl; + break; + } + case 'd': { + Pila* stack = new Pila{}; + in >> n; + string s; + for(int i = 0; i < n; ++i) { + in >> s; + if(s.at(0) == 'i') { + stack->push(stod(s.substr(1, s.length()-1))); + } else { + stack->pop(); + } + } + while(!stack->is_empty()) + out << stack->pop()->key() << ' '; + out << endl; + break; + } + case 'c': { + Pila* stack = new Pila{}; + in >> n; + string s; + for(int i = 0; i < n; ++i) { + in >> s; + if(s.at(0) == 'i') { + stack->push(s.at(1)); + } else { + stack->pop(); + } + } + while(!stack->is_empty()) + out << stack->pop()->key() << ' '; + out << endl; + break; + } + case 'i': { + Pila* stack = new Pila{}; + in >> n; + string s; + for(int i = 0; i < n; ++i) { + in >> s; + if(s.at(0) == 'i') { + stack->push(stoi(s.substr(1, s.length()-1))); + } else { + stack->pop(); + } + } + while(!stack->is_empty()) + out << stack->pop()->key() << ' '; + out << endl; + break; + } + } + } + in.close(); + out.close(); + return 0; +} -- cgit v1.2.3-18-g5258