Dada una array de strings Q[] , que consta de consultas de los siguientes tipos:
- “ESCRIBIR X”: Escriba un carácter X en el documento.
- “UNDO”: Borra el último cambio realizado en el documento.
- “REDO”: Restaura la operación UNDO más reciente realizada en el documento.
- “LEER”: Lee e imprime el contenido de los documentos.
Ejemplos:
Entrada: Q = {“ESCRIBIR A”, “ESCRIBIR B”, “ESCRIBIR C”, “DESHACER”, “LEER”, “REHACER”, “LEER”}
Salida: AB ABC
Explicación:
Ejecutar “ESCRIBIR A” en el documento . Por lo tanto, el documento contiene solo «A».
Realice “ESCRIBIR B” en el documento. Por lo tanto, el documento contiene «AB».
Realice “ESCRIBIR C” en el documento. Por lo tanto, el documento contiene «ABC».
Realice «DESHACER» en el documento. Por lo tanto, el documento contiene «AB».
Imprime el contenido del documento, es decir, “AB”
Realiza “REDO” en el documento. Por lo tanto, el documento contiene «ABC».
Imprime el contenido del documento, es decir, “ABC”Entrada: Q = {“ESCRIBIR x”, “ESCRIBIR y”, “DESHACER”, “ESCRIBIR z”, “LEER”, “REHACER”, “LEER”}
Salida: xz xzy
Enfoque: El problema se puede resolver usando Stack . Siga los pasos a continuación para resolver el problema:
- Inicialice dos pilas, digamos Deshacer y Rehacer .
- Recorra la array de strings, Q , y realice las siguientes operaciones:
- Si se encuentra la string «ESCRIBIR» , empuje el carácter a la pila Deshacer
- Si se encuentra la string «UNDO» , extraiga el elemento superior de la pila Undo y empújelo a la pila Redo .
- Si se encuentra la string «REDO» , extraiga el elemento superior de la pila Redo y empújelo a la pila Undo .
- Si se encuentra la string «LEER» , imprima todos los elementos de la pila Deshacer en orden inverso .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to perform // "WRITE X" operation void WRITE(stack<char>& Undo, char X) { // Push an element to // the top of stack Undo.push(X); } // Function to perform // "UNDO" operation void UNDO(stack<char>& Undo, stack<char>& Redo) { // Stores top element // of the stack char X = Undo.top(); // Erase top element // of the stack Undo.pop(); // Push an element to // the top of stack Redo.push(X); } // Function to perform // "REDO" operation void REDO(stack<char>& Undo, stack<char>& Redo) { // Stores the top element // of the stack char X = Redo.top(); // Erase the top element // of the stack Redo.pop(); // Push an element to // the top of the stack Undo.push(X); } // Function to perform // "READ" operation void READ(stack<char> Undo) { // Store elements of stack // in reverse order stack<char> revOrder; // Traverse Undo stack while (!Undo.empty()) { // Push an element to // the top of stack revOrder.push(Undo.top()); // Erase top element // of stack Undo.pop(); } while (!revOrder.empty()) { // Print the top element // of the stack cout << revOrder.top(); Undo.push(revOrder.top()); // Erase the top element // of the stack revOrder.pop(); } cout << " "; } // Function to perform the // queries on the document void QUERY(vector<string> Q) { // Stores the history of all // the queries that have been // processed on the document stack<char> Undo; // Stores the elements // of REDO query stack<char> Redo; // Stores total count // of queries int N = Q.size(); // Traverse all the query for (int i = 0; i < N; i++) { if (Q[i] == "UNDO") { UNDO(Undo, Redo); } else if (Q[i] == "REDO") { REDO(Undo, Redo); } else if (Q[i] == "READ") { READ(Undo); } else { WRITE(Undo, Q[i][6]); } } } // Driver Code int main() { vector<string> Q = { "WRITE A", "WRITE B", "WRITE C", "UNDO", "READ", "REDO", "READ" }; QUERY(Q); return 0; }
Java
// Java Program to implement the above approach import java.util.*; public class Main { // Stores the history of all // the queries that have been // processed on the document static Stack<Character> Undo = new Stack<Character>(); // Stores the elements // of REDO query static Stack<Character> Redo = new Stack<Character>(); // Function to perform // "WRITE X" operation static void WRITE(Stack<Character> Undo, char X) { // Push an element to // the top of stack Undo.push(X); } // Function to perform // "UNDO" operation static void UNDO(Stack<Character> Undo, Stack<Character> Redo) { // Stores top element // of the stack char X = (char)Undo.peek(); // Erase top element // of the stack Undo.pop(); // Push an element to // the top of stack Redo.push(X); } // Function to perform // "REDO" operation static void REDO(Stack<Character> Undo, Stack<Character> Redo) { // Stores the top element // of the stack char X = (char)Redo.peek(); // Erase the top element // of the stack Redo.pop(); // Push an element to // the top of the stack Undo.push(X); } // Function to perform // "READ" operation static void READ(Stack<Character> Undo) { // Store elements of stack // in reverse order Stack<Character> revOrder = new Stack<Character>(); // Traverse Undo stack while (Undo.size() > 0) { // Push an element to // the top of stack revOrder.push(Undo.peek()); // Erase top element // of stack Undo.pop(); } while (revOrder.size() > 0) { // Print the top element // of the stack System.out.print(revOrder.peek()); Undo.push(revOrder.peek()); // Erase the top element // of the stack revOrder.pop(); } System.out.print(" "); } // Function to perform the // queries on the document static void QUERY(String[] Q) { // Stores total count // of queries int N = Q.length; // Traverse all the query for (int i = 0; i < N; i++) { if(Q[i] == "UNDO") { UNDO(Undo, Redo); } else if(Q[i] == "REDO") { REDO(Undo, Redo); } else if(Q[i] == "READ") { READ(Undo); } else { WRITE(Undo, Q[i].charAt(6)); } } } public static void main(String[] args) { String[] Q = { "WRITE A", "WRITE B", "WRITE C", "UNDO", "READ", "REDO", "READ" }; QUERY(Q); } } // This code is contributed by divyeshrabadiya07.
Python3
# Python Program to implement # the above approach global Undo global Redo # Stores the history of all # the queries that have been # processed on the document Undo = [] # Stores the elements # of REDO query Redo = [] # Function to perform # "WRITE X" operation def WRITE(Undo, X): # Push an element to # the top of stack Undo.append(X) # Function to perform # "UNDO" operation def UNDO(Undo, Redo): # Stores top element # of the stack X = Undo[-1] # Erase top element # of the stack Undo.pop() # Push an element to # the top of stack Redo.append(X) # Function to perform # "REDO" operation def REDO(Undo, Redo): # Stores the top element # of the stack X = Redo[-1] # Erase the top element # of the stack Redo.pop() # Push an element to # the top of the stack Undo.append(X) # Function to perform # "READ" operation def READ(Undo): print(*Undo, sep = "", end = " ") # Function to perform the # queries on the document def QUERY(Q): # Stores total count # of queries N = len(Q) # Traverse all the query for i in range(N): if(Q[i] == "UNDO"): UNDO(Undo, Redo) elif(Q[i] == "REDO"): REDO(Undo, Redo) elif(Q[i] == "READ"): READ(Undo) else: WRITE(Undo, Q[i][6]) # Driver Code Q = ["WRITE A", "WRITE B", "WRITE C", "UNDO", "READ", "REDO", "READ"] QUERY(Q) #This code is contributed by avanitrachhadiya2155
C#
// C# Program to implement the above approach using System; using System.Collections; class GFG { // Stores the history of all // the queries that have been // processed on the document static Stack Undo = new Stack(); // Stores the elements // of REDO query static Stack Redo = new Stack(); // Function to perform // "WRITE X" operation static void WRITE(Stack Undo, char X) { // Push an element to // the top of stack Undo.Push(X); } // Function to perform // "UNDO" operation static void UNDO(Stack Undo, Stack Redo) { // Stores top element // of the stack char X = (char)Undo.Peek(); // Erase top element // of the stack Undo.Pop(); // Push an element to // the top of stack Redo.Push(X); } // Function to perform // "REDO" operation static void REDO(Stack Undo, Stack Redo) { // Stores the top element // of the stack char X = (char)Redo.Peek(); // Erase the top element // of the stack Redo.Pop(); // Push an element to // the top of the stack Undo.Push(X); } // Function to perform // "READ" operation static void READ(Stack Undo) { // Store elements of stack // in reverse order Stack revOrder = new Stack(); // Traverse Undo stack while (Undo.Count > 0) { // Push an element to // the top of stack revOrder.Push(Undo.Peek()); // Erase top element // of stack Undo.Pop(); } while (revOrder.Count > 0) { // Print the top element // of the stack Console.Write(revOrder.Peek()); Undo.Push(revOrder.Peek()); // Erase the top element // of the stack revOrder.Pop(); } Console.Write(" "); } // Function to perform the // queries on the document static void QUERY(string[] Q) { // Stores total count // of queries int N = Q.Length; // Traverse all the query for (int i = 0; i < N; i++) { if(Q[i] == "UNDO") { UNDO(Undo, Redo); } else if(Q[i] == "REDO") { REDO(Undo, Redo); } else if(Q[i] == "READ") { READ(Undo); } else { WRITE(Undo, Q[i][6]); } } } static void Main() { string[] Q = { "WRITE A", "WRITE B", "WRITE C", "UNDO", "READ", "REDO", "READ" }; QUERY(Q); } } // This code is contributed by rameshtravel07
Javascript
<script> // Javascript Program to implement the above approach // Stores the history of all // the queries that have been // processed on the document let Undo = []; // Stores the elements // of REDO query let Redo = []; // Function to perform // "WRITE X" operation function WRITE(Undo, X) { // Push an element to // the top of stack Undo.push(X) } // Function to perform // "UNDO" operation function UNDO(Undo, Redo) { // Stores top element // of the stack let X = Undo[Undo.length - 1]; // Erase top element // of the stack Undo.pop(); // Push an element to // the top of stack Redo.push(X); } // Function to perform // "REDO" operation function REDO(Undo, Redo) { // Stores the top element // of the stack let X = Redo[Redo.length - 1]; // Erase the top element // of the stack Redo.pop(); // Push an element to // the top of the stack Undo.push(X); } // Function to perform // "READ" operation function READ(Undo) { // Store elements of stack // in reverse order let revOrder = []; // Traverse Undo stack while (Undo.length > 0) { // Push an element to // the top of stack revOrder.push(Undo[Undo.length - 1]); // Erase top element // of stack Undo.pop(); } while (revOrder.length > 0) { // Print the top element // of the stack document.write(revOrder[revOrder.length - 1]); Undo.push(revOrder[revOrder.length - 1]); // Erase the top element // of the stack revOrder.pop(); } document.write(" "); } // Function to perform the // queries on the document function QUERY(Q) { // Stores total count // of queries N = Q.length // Traverse all the query for (let i = 0; i < N; i++) { if(Q[i] == "UNDO") { UNDO(Undo, Redo); } else if(Q[i] == "REDO") { REDO(Undo, Redo); } else if(Q[i] == "READ") { READ(Undo); } else { WRITE(Undo, Q[i][6]); } } } let Q = [ "WRITE A", "WRITE B", "WRITE C", "UNDO", "READ", "REDO", "READ" ]; QUERY(Q); // This code is contributed by suresh07. </script>
AB ABC
Complejidad de tiempo:
DESHACER: O(1)
REHACER: O(1)
ESCRIBIR: O(1)
LEER: (N), donde N indica el tamaño de la pila Deshacer
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por promaroy20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA