summaryrefslogtreecommitdiff
path: root/I_anno/Programmazione_2
diff options
context:
space:
mode:
authorSanto Cariotti <dcariotti24@gmail.com>2020-05-24 16:58:23 +0200
committerSanto Cariotti <dcariotti24@gmail.com>2020-05-24 16:58:23 +0200
commitbc8b5b446a6a2d37bae82e7ad20e31e1439a2f0b (patch)
tree1aa5a346a96bc9edef6b3bc109967135cde9debe /I_anno/Programmazione_2
parentf04e3a465b28b921f89695ca4743ac8b439b17f1 (diff)
feat: add more exercises
Diffstat (limited to 'I_anno/Programmazione_2')
-rw-r--r--I_anno/Programmazione_2/exercises/dequeue.cc137
-rw-r--r--I_anno/Programmazione_2/exercises/doppioni.cc77
-rw-r--r--I_anno/Programmazione_2/exercises/pop-stack.cc132
3 files changed, 346 insertions, 0 deletions
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<iostream>
+#include<fstream>
+
+using namespace std;
+
+template<class T>
+class node {
+public:
+ node(T key, node<T>* next) : _key{key}, _next{next} {}
+ node(T key) : _key{key}, _next{nullptr} {}
+ const T& key() const { return _key; }
+ T& key() { return _key; }
+ const node<T>*& next() const { return _next; }
+ node<T>*& next() { return _next; }
+private:
+ T _key;
+ node<T>* _next;
+};
+
+template<class T>
+class Coda {
+public:
+ Coda() : _head{nullptr}, _tail{nullptr} {}
+ ~Coda() {
+
+ }
+ Coda<T>* enqueue(T val) {
+ if(!_head) {
+ _head = new node<T>{val, nullptr};
+ _tail = _head;
+ } else {
+ _tail->next() = new node<T>{val, nullptr};
+ _tail = _tail->next();
+ }
+
+ return this;
+ }
+ node<T>* dequeue() {
+ if(!_head) return nullptr;
+ node<T>* elem = _head;
+ delete _head;
+ _head = elem->next();
+
+ return elem;
+ }
+
+ bool is_empty() { return _head == nullptr; }
+private:
+ node<T>* _head;
+ node<T>* _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<bool>* queue = new Coda<bool>{};
+ 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<double>* queue = new Coda<double>{};
+ 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<char>* queue = new Coda<char>{};
+ 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<int>* queue = new Coda<int>{};
+ 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<iostream>
+#include<fstream>
+
+using namespace std;
+
+template<class T>
+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<T>*& parent() { return _parent; }
+ const node<T>*& parent() const { return _parent; }
+ node<T>*& right() { return _right; }
+ const node<T>*& right() const { return _right; }
+ node<T>*& left() { return _left; }
+ const node<T>*& left() const { return _left; }
+private:
+ T _key;
+ node<T>* _parent;
+ node<T>* _right;
+ node<T>* _left;
+};
+
+class bst {
+public:
+ bst() : _duplicates{0}, _root{nullptr} {}
+ bst* add(int val) {
+ node<int>* iter = _root;
+ node<int>* 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<int>* nodus = new node<int>{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<int>* _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<iostream>
+#include<fstream>
+
+using namespace std;
+
+template<class T>
+class node {
+public:
+ node(T key, node<T>* next) : _key{key}, _next{next} {}
+ node(T key) : _key{key}, _next{nullptr} {}
+ const T& key() const { return _key; }
+ T& key() { return _key; }
+ const node<T>*& next() const { return _next; }
+ node<T>*& next() { return _next; }
+private:
+ T _key;
+ node<T>* _next;
+};
+
+template<class T>
+class Pila {
+public:
+ Pila() : _head{nullptr}{}
+ ~Pila() {
+
+ }
+ Pila<T>* push(T val) {
+ if(!_head) {
+ _head = new node<T>{val, nullptr};
+ } else {
+ _head = new node<T>{val, _head};
+ }
+
+ return this;
+ }
+ node<T>* pop() {
+ if(!_head) return nullptr;
+ node<T>* elem = _head;
+ delete _head;
+ _head = elem->next();
+
+ return elem;
+ }
+
+ bool is_empty() { return _head == nullptr; }
+private:
+ node<T>* _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<bool>* stack = new Pila<bool>{};
+ 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<double>* stack = new Pila<double>{};
+ 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<char>* stack = new Pila<char>{};
+ 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<int>* stack = new Pila<int>{};
+ 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;
+}