Logo Studenta

Actividad de Aprendizaje 11 La Pila y la Cola, implementación dinámica - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

UNIVERSIDAD DE GUADALAJARA
Centro Universitario de Ciencias Exactas e Ingenierías
Estructura de datos I
Actividad de Aprendizaje 11. La Pila y la Cola, implementación dinámica
Alumno: Sandoval Padilla Fernando Cesar
Docente: Gutiérrez Hernández Alfredo
Código: 215685409
Sección: D12
	
			
 10 de Noviembre de 2019
Resumen personal:
La realización de esta actividad no tuvo mayor dificultad que intercambiar los arreglos utilizados en la actividad anterior para hacer una implementación dinámica. Por otra parte, se utilizaron los mismos 3 ejemplos del documento 06_B_Pila_aplicacion que se extrajo de los apuntes de estructuras de datos en la pagina 5 del documento, los cuales están presentes en las capturas de pantalla.
Código fuente:
Main.cpp
1 #include <iostream>
2 #include <windows.h>
3 #include <string.h>
4
5 #include "stack.h"
6 #include "queue.h"
7 #include "E.h"
8
9 using namespace std;
10
11 int main() {
12 char e;
13 E elem;
14 E sum,rest,mul,div,pot,para,parc;
15 e = '+';
16 sum.setElement(e);
17 e = '-';
18 rest.setElement(e);
19 e = '*';
20 mul.setElement(e);
21 e = '/';
22 div.setElement(e);
23 e = '^';
24 pot.setElement(e);
25 e = '(';
26 para.setElement(e);
27 e = ')';
28 parc.setElement(e);
29 Stack<E> myStack;
30 Queue<E> myQueue;
31 char mychar[1024];
32 int lon;
33 cout << "Ingrese la cadena a comvertir a posfija" << endl;
34 cin >> mychar;
35 lon = strlen(mychar);
36 for(int i(0) ; i <= lon ; i++) {
37 elem.setElement(mychar[i]);
38 switch(mychar[i]) {
39 case '(':
40 try {
41 myStack.push(elem);
42 } catch(Stack<E>::Exception ex) {
43 cout << ex.what() << endl;
44 }
45 break;
46 case ')':
47 try {
48 while(!myStack.isEmpty()){
49 if(myStack.getTop() == para ) {
50 myStack.pop();
51 break;
52 } else {
53 myQueue.enqueue(myStack.getTop());
54 myStack.pop();
55 }
56 }
57 } catch(Stack<E>::Exception ex) {
58 cout << ex.what() << endl;
59 }
60 break;
61 case '+':
62 try {
63 if(myStack.isEmpty() == true) {
64 myStack.push(elem);
65 break;
66 }
67 if(myStack.getTop() == para ) {
68 myStack.push(elem);
69 break;
70 }
71 while(!myStack.isEmpty()) {
72 if(myStack.getTop() == para ) {
73 myStack.pop();
74 break;
75 } else {
76 myQueue.enqueue(myStack.getTop());
77 myStack.pop();
78 }
79 }
80 } catch(Stack<E>::Exception ex) {
81 cout << ex.what() << endl;
82 }
83 case '-':
84 try {
85 if(myStack.isEmpty() == true) {
86 myStack.push(elem);
87 break;
88 }
89 if(myStack.getTop() == para) {
90 myStack.push(elem);
91 break;
92 }
93 while(!myStack.isEmpty()) {
94 if(myStack.getTop() == para) {
95 myStack.pop();
96 break;
97 } else {
98 myQueue.enqueue(myStack.getTop());
99 myStack.pop();
100 }
101 }
102 } catch(Stack<E>::Exception ex) {
103 cout << ex.what() << endl;
104 }
105 case '*':
106 try {
107 if(myStack.isEmpty() == true) {
108 myStack.push(elem);
109 break;
110 }
111 if(myStack.getTop() == para) {
112 myStack.push(elem);
113 break;
114 }
115 if( myStack.getTop() == pot or myStack.getTop() == mul or myStack.getTop() == div ) {
116 myQueue.enqueue(myStack.getTop());
117 myStack.pop();
118 myStack.push(elem);
119 } else {
120 myStack.push(elem);
121 }
122
123 } catch(Stack<E>::Exception ex) {
124 cout << ex.what() << endl;
125 }
126 break;
127 case '/':
128 try {
129 if(myStack.isEmpty() == true) {
130 myStack.push(elem);
131 break;
132 }
133 if(myStack.getTop() == para) {
134 myStack.push(elem);
135 break;
136 }
137 if( myStack.getTop() == pot or myStack.getTop() == mul or myStack.getTop() == div ) {
138 myQueue.enqueue(myStack.getTop());
139 myStack.pop();
140 myStack.push(elem);
141 } else {
142 myStack.push(elem);
143 }
144 } catch(Stack<E>::Exception ex) {
145 cout << ex.what() << endl;
146 }
147 break;
148 case '^':
149
150 try {
151 if(myStack.isEmpty() == true) {
152 myStack.push(elem);
153 break;
154 }
155 if(myStack.getTop() == para) {
156 myStack.push(elem);
157 break;
158 }
159 if( myStack.getTop() == pot ) {
160 myQueue.enqueue(myStack.getTop());
161 myStack.pop();
162 myStack.push(elem);
163 } else {
164 myStack.push(elem);
165 }
166 } catch(Stack<E>::Exception ex) {
167 cout << ex.what() << endl;
168 }
169 break;
170 default:
171 try {
172 myQueue.enqueue(elem);
173 } catch(Stack<E>::Exception ex) {
174 cout << ex.what() << endl;
175 }
176 break;
177 }
178 }
179 try {
180 while(!myStack.isEmpty()) {
181 myQueue.enqueue(myStack.getTop());
182 myStack.pop();
183 }
184 } catch(Stack<E>::Exception ex) {
185 cout << ex.what() << endl;
186 }
187 cout << "El resultado es: ";
188 while( !myQueue.isEmpty() ){
189 cout << myQueue.getFront();
190 myQueue.dequeue();
191 }
192 cout << endl << endl;
193 gets(mychar);
194 return 0;
195 }
196
E.h
1 #ifndef E_H_INCLUDED
2 #define E_H_INCLUDED
3
4 class E {
5 private:
6 char element;
7 public:
8 void setElement(const char&);
9 char getElement();
10 bool operator == (const E&) const;
11 bool operator != (const E&) const;
12 bool operator <= (const E&) const;
13 bool operator >= (const E&) const;
14 bool operator > (const E&) const;
15 bool operator < (const E&) const;
16 friend std::ostream& operator << (std::ostream&, E&);
17 };
18
19 void E::setElement(const char& e){
20 element = e;
21 }
22
23 char E::getElement(){
24 return element;
25 }
26
27 bool E::operator == (const E& e) const {
28 return element == e.element;
29 }
30
31 bool E::operator != (const E& e) const {
32 return element != e.element;
33 }
34
35 bool E::operator >= (const E& e) const {
36 return element >= e.element;
37 }
38
39 bool E::operator > (const E& e) const {
40 return element > e.element;
41 }
42
43 bool E::operator <= (const E& e) const {
44 return element <= e.element;
45 }
46
47 bool E::operator < (const E& e) const {
48 return element < e.element;
49 }
50
51 std::ostream& operator << (std::ostream& os, E& s){
52 std::string aux;
53 aux = s.element;
54 os << aux;
55 return os;
56 }
57
58
59 #endif // E_H_INCLUDED
queue.h
1 #ifndef QUEUE_H_INCLUDED
2 #define QUEUE_H_INCLUDED
3
4 #include <string>
5 #include <exception>
6
7 ///Definicion
8
9 template <class T>
10 class Queue {
11 public:
12 class Exception: public std::exception
13 {
14 private:
15 std::string msg;
16
17 public:
18 explicit Exception(const char* message) : msg(message) { }
19
20 explicit Exception(const std::string& message) : msg(message) { }
21
22 virtual ~Exception() throw () { }
23
24 virtual const char* what() const throw () {
25 return msg.c_str();
26 }
27 };
28
29 private:
30 class Node
31 {
32 private:
33 T* dataPtr;
34 Node* prev;
35 Node* next;
36
37 public:
38 class Exception: public std::exception
39 {
40 private:
41 std::string msg;
42
43 public:
44 explicit Exception(const char* message) : msg(message) { }
45
46 explicit Exception(const std::string& message) : msg(message) { }
47
48 virtual ~Exception() throw () { }
49
50 virtual const char* what() const throw () {
51 return msg.c_str();
52 }
53 };
54 Node();
55 Node(const T&);
56
57 ~Node();
58
59 T* getDataPtr();
60 T& getData();
61 Node* getPrev() const;
62 Node* getNext() const;
63
64 void setDataPtr(T*);
65 void setData(const T&);
66 void setPrev(Node*);
67 void setNext(Node*);
68 };
69
70 Node* headerPtr;
71
72 void copyAll(const Queue&);
73
74 void deleteAll();
75
76 public:
77
78 Queue();
79 Queue(const Queue&);
80
81 ~Queue();
82
83 bool isEmpty() const;
84
85 void enqueue(const T&);
86 T dequeue();
87
88 T& getFront();
89
90 Queue& operator = (const Queue&);
91 };
92
93 ///Implementacion
94
95 using namespace std;
96
97 ///Node
98
99 template <class T>
100 Queue<T>::Node::Node() : dataPtr(nullptr), prev(nullptr), next(nullptr) { }
101
102 template <class T>
103 Queue<T>::Node::Node(const T& e) : dataPtr(new T(e)), prev(nullptr), next(nullptr)
104 {
105 if(dataPtr == nullptr)
106 {
107 throw Exception(" Memoria no disponible, creando nodo");
108 }
109 }
110
111 template <class T>
112 Queue<T>::Node::~Node()
113 {
114 dataPtr = nullptr;
115 }
116
117 template <class T>
118 T* Queue<T>::Node::getDataPtr()
119 {
120 return dataPtr;
121 }
122
123 template <class T>
124 T& Queue<T>::Node::getData()
125 {
126 return *dataPtr;127 }
128
129 template <class T>
130 typename Queue<T>::Node* Queue<T>::Node::getPrev() const
131 {
132 return prev;
133 }
134
135 template <class T>
136 typename Queue<T>::Node* Queue<T>::Node::getNext() const
137 {
138 return next;
139 }
140
141 template <class T>
142 void Queue<T>::Node::setDataPtr(T* p)
143 {
144 dataPtr = p;
145 }
146
147 template <class T>
148 void Queue<T>::Node::setData(const T& e)
149 {
150 if(dataPtr == nullptr and (dataPtr = new T(e)) == nullptr)
151 {
152 throw Exception(" Memoria no disponible, Node::setData.");
153 }
154
155 else
156 {
157 *dataPtr = e;
158 }
159
160 }
161
162 template <class T>
163 void Queue<T>::Node::setPrev(Queue<T>::Node* p)
164 {
165 prev = p;
166 }
167
168 template <class T>
169 void Queue<T>::Node::setNext(Queue<T>::Node* p)
170 {
171 next = p;
172 }
173
174 ///Queue
175
176 ///private
177
178 template <class T>
179 void Queue<T>::copyAll(const Queue<T>& l)
180 {
181 if(!l.isEmpty()){
182 Node* aux(l.headerPtr->getNext());
183 Node* newNode;
184 while(aux != l.headerPtr)
185 {
186 try {
187 if(newNode = new Node(aux->getData()) == nullptr)
188 {
189 throw Exception(" Memoria no disponible, copyAll");
190 }
191 } catch (typename Queue<T>::Node::Exception ex)
192 {
193 throw Exception(ex.what());
194 }
195 }
196
197 }
198 }
199
200 template <class T>
201 void Queue<T>::deleteAll()
202 {
203 Node* aux;
204
205 while(headerPtr->getNext() != headerPtr);
206 {
207 aux = headerPtr->getNext();
208
209 headerPtr->setNext(aux->getNext());
210
211 delete aux;
212 }
213
214 headerPtr->setPrev(headerPtr);
215 }
216
217 ///public
218
219 template <class T>
220 Queue<T>::Queue() : headerPtr(new Node)
221 {
222 if(headerPtr == nullptr)
223 {
224 throw Exception(" La memoria no esta disponible, creando la Queue.");
225 }
226
227 headerPtr->setPrev(headerPtr);
228 headerPtr->setNext(headerPtr);
229 }
230
231 template <class T>
232 Queue<T>::Queue(const Queue<T>& l) : Queue()
233 {
234 copyAll(l);
235 }
236
237 template <class T>
238 Queue<T>::~Queue()
239 {
240 deleteAll();
241
242 delete headerPtr;
243 }
244
245 template <class T>
246 Queue<T>& Queue<T>::operator = (const Queue<T>& l)
247 {
248 deleteAll();
249
250 copyAll(l);
251
252 return *this;
253 }
254
255 template <class T>
256 bool Queue<T>::isEmpty() const
257 {
258 return headerPtr->getNext() == nullptr;
259 }
260
261 template <class T>
262 void Queue<T>::enqueue(const T& e)
263 {
264 Node* aux;
265
266 try {
267 aux = new Node(e);
268 } catch(typename Queue<T>::Node::Exception ex) {
269 throw Exception(ex.what());
270 }
271
272 if(aux == nullptr)
273 {
274 throw Exception(" Memoria no disponible, enqueue.");
275 }
276
277 aux->setPrev(headerPtr->getPrev());
278 aux->setNext(headerPtr);
279
280 headerPtr->getPrev()->setNext(aux);
281 headerPtr->setPrev(aux);
282 }
283
284 template <class T>
285 T Queue<T>::dequeue()
286 {
287 if(isEmpty())
288 {
289 throw Exception(" Insuficiencia de datos, dequeue.");
290 }
291
292 T result(headerPtr->getNext()->getData());
293
294 Node* aux(headerPtr->getNext());
295
296 aux->getPrev()->setNext(aux->getNext());
297 aux->getNext()->setPrev(aux->getPrev());
298
299 delete aux;
300
301 return result;
302 }
303
304 template <class T>
305 T& Queue<T>::getFront()
306 {
307 if(isEmpty())
308 {
309 throw Exception(" Insuficiencia de dato, getFront");
310 }
311
312 return headerPtr->getNext()->getData();
313 }
314
315 #endif // QUEUE_H_INCLUDED
316
stack.h
1 #ifndef STACK_H_INCLUDED
2 #define STACK_H_INCLUDED
3
4 #include <string>
5 #include <exception>
6
7 ///Definicion
8
9 template <class T>
10 class Stack
11 {
12 public:
13 class Exception: public std::exception
14 {
15 private:
16 std::string msg;
17
18 public:
19 explicit Exception(const char* message) : msg(message) { }
20
21 explicit Exception(const std::string& message) : msg(message) { }
22
23 virtual ~Exception() throw () { }
24
25 virtual const char* what() const throw () {
26 return msg.c_str();
27 }
28 };
29
30 private:
31 class Node
32 {
33 private:
34 T data;
35 Node* next;
36
37 public:
38 Node();
39 Node(const T&);
40
41 T& getData();
42 Node* getNext() const;
43
44 void setData(const T&);
45 void setNext(Node*);
46 };
47
48 Node* anchor;
49
50 void copyAll(const Stack&);
51
52 void deleteAll();
53
54 public:
55
56 Stack();
57 Stack(const Stack&);
58
59 ~Stack();
60
61 bool isEmpty() const;
62
63 void push(const T&);
64 T pop();
65
66 T& getTop();
67
68 Stack& operator = (const Stack&);
69 };
70
71 ///Implementacion
72
73 using namespace std;
74
75 ///Node
76
77 template <class T>
78 Stack<T>::Node::Node() : next(nullptr) { }
79
80 template <class T>
81 Stack<T>::Node::Node(const T& e) : data(e), next(nullptr) { }
82
83 template <class T>
84 T& Stack<T>::Node::getData()
85 {
86 return data;
87 }
88
89 template <class T>
90 typename Stack<T>::Node* Stack<T>::Node::getNext() const
91 {
92 return next;
93 }
94
95 template <class T>
96 void Stack<T>::Node::setData(const T& e)
97 {
98 data = e;
99 }
100
101 template <class T>
102 void Stack<T>::Node::setNext(Stack<T>::Node* p)
103 {
104 next = p;
105 }
106
107 ///Stack
108
109 ///private
110
111 template <class T>///Copiar Stack
112 void Stack<T>::copyAll(const Stack<T>& l)
113 {
114 Node* aux(l.anchor);
115 Node* lastInserted(nullptr);
116 Node* newNode;
117
118 while(aux != nullptr)
119 {
120 newNode = new Node(aux->getData());
121
122 if(newNode == nullptr)
123 {
124 throw Exception("Memoria no disponible, copyAll");
125 }
126
127 if(lastInserted == nullptr)
128 {
129 anchor = newNode;
130 }
131 else
132 {
133 lastInserted->setNext(newNode);
134 }
135
136 lastInserted = newNode;
137
138 aux = aux->getNext();
139 }
140 }
141
142 template <class T>///Borrar todo
143 void Stack<T>::deleteAll()
144 {
145 Node* aux;
146
147 while(anchor != nullptr)
148 {
149 aux = anchor;
150
151 anchor = anchor->getNext();
152
153 delete aux;
154 }
155 }
156
157 ///public
158
159 template <class T>///Constructor
160 Stack<T>::Stack() : anchor(nullptr) { }
161
162 template <class T>///Constructor copia
163 Stack<T>::Stack(const Stack<T>& l) : anchor(nullptr)
164 {
165 copyAll(l);
166 }
167
168 template <class T>///Desconstructor
169 Stack<T>::~Stack()
170 {
171 deleteAll();
172 }
173
174 template <class T>///Operador de igual
175 Stack<T>& Stack<T>::operator = (const Stack<T>& l)
176 {
177 deleteAll();
178
179 copyAll(l);
180
181 return *this;
182 }
183
184 template <class T>///Si esta vacia la lista
185 bool Stack<T>::isEmpty() const
186 {
187 return anchor == nullptr;
188 }
189
190 template <class T>///Insertar Dato
191 void Stack<T>::push(const T& e)
192 {
193 Node* aux(new Node(e));
194
195 if(aux == nullptr)
196 {
197 throw Exception(" Memoria no disponible, push");
198 }
199
200 aux->setNext(anchor);
201
202 anchor = aux;
203 }
204
205 template <class T>///Eliminar Dato
206 T Stack<T>::pop()
207 {
208 if(isEmpty())
209 {
210 throw Exception(" Insuficiencia de datos, pop");
211 }
212
213 T result(anchor->getData());
214
215 Node* aux(anchor);
216
217 anchor = anchor->getNext();
218
219 delete aux;
220
221 return result;
222
223 }
224
225 template <class T>///Recuperar posicion
226 T& Stack<T>::getTop()
227 {
228 if(isEmpty())
229 {
230 throw Exception(" Insuficiencia de datos, getTop");
231 }
232
233 return anchor->getData();
234 }
235
236 #endif // STACK_H_INCLUDED
Capturas de pantalla:

Otros materiales