Descarga la aplicación para disfrutar aún más
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:
Compartir