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>
Producción:
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