撤销与恢复

	先初始化两个栈stack和redo，然后利用双栈求解。遍历词表：



	
	

		
		

			遇到普通词就压入stack，并清空redo栈，因为此时写入了一个新词，再往前的词已经找不回来了；
		

		

			遇到undo就从stack中弹栈至redo；
		

		

			遇到redo就从redo中弹栈至stack。
		

	



package com.tuling.partone;


import java.util.*;

public class Test {

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        String str=scanner.nextLine();
        Stack stack=ctrlZ(str);
        System.out.println(String.join(" ", stack));
    }

    private static Stack ctrlZ(String str) {
        Stack<String> stack = new Stack<String>();
        Stack<String> redoStack = new Stack<String>();
        List<String> list = new ArrayList<>(Arrays.asList(str.replace("\t", " ").split(" ")));
        for (int i = 0; i < list.size(); i++) {
            if ("undo".equals(list.get(i))){
                if (!stack.empty()){
                    redoStack.push(stack.pop());
                }
            }else if("redo".equals(list.get(i))){
                if(!redoStack.empty()){
                    stack.push(redoStack.pop());
                }
            }else{
                redoStack.clear();
                stack.push(list.get(i));
            }

        }
        return stack;
    }
}

function changeStr( str ) {
    // write code here
    var result = ''
    var splitStr = str.split(' ')
    var undoStr = []
    for (let i =0; i < splitStr.length; i++){
        // 发现撤销
        if (splitStr[i] === 'undo') {
                undoStr.push(splitStr[i - 1])
                splitStr.splice(i - 1, 2)
                i -= 2
        // 发现还原
        } else if (splitStr[i] === 'redo') {
            if (undoStr.length == 0) {
                splitStr.splice(i, 1)
                i -= 1
            } else {
                splitStr.splice(i, 1)
                splitStr.splice(i, 0, undoStr.pop())
            }
        // 正常字符，则清空undo
        } else {
            undoStr = []
        }
    }
    splitStr.map((item) => {
        result += ` ${item}`
    })
    return result.substr(1, result.length - 1)
}
print(changeStr(readline()))

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()){
            ctrlZ(sc.nextLine());
        }
    }

    private static void ctrlZ(String str) {

        List<String> list = new ArrayList<>(Arrays.asList(str.replace("\t", " ").split(" ")));

        Deque<String> deque = new LinkedList<>();

        for (int i=0;i<list.size();i++){
            if("undo".equals(list.get(i))){
                list.remove(i--);
                if(i>=0){
                    deque.push(list.get(i));
                    list.remove(i--);
                }
            }else if("redo".equals(list.get(i))){
                list.remove(i);
                if(!deque.isEmpty()){
                    list.add(i++,deque.pop());
                }
                i--;
            }else{
                deque.clear();
            }
        }
        System.out.println(String.join(" ",list));
    }
}

public class UndoRedo {
    public static void main(String[] args) throws InterruptedException {
        // 创建存储对外显示的字符串的栈集合 usefulWords
        Stack<String> usefulWords = new Stack<> ();
        // 创建储存删除的字符串的栈集合 uselessWords
        Stack<String> uselessWords = new Stack<> ();
        // 创建scanner对象获取用户输入的字符串
        Scanner scanner = new Scanner (System.in);
        // 创建输入的死循环,可暂用 不输入 表示结束输入
        while (true) {
            // 友好提示
            System.out.print ("请输入:");
            String input= scanner.nextLine ();
            // 不输入表示结束循环
            if (input == null || input.equals ("")) {
                System.out.println ("感谢使用,Bye");
                return;
            }
            // 切割字符串
            String[] inputWords = input.split (" ");
            for (String inputWord : inputWords) {
                // 判断输入的字符串值 undo redo  其他三种情况
                if ("undo".equals (inputWord)) {
                    // usefulWords 非空则移除 usefulWords 栈顶的元素,添加到 uselessWords 集合
                    if (!usefulWords.empty ()) {
                        uselessWords.push (usefulWords.pop ());
                    }
                } else if ("redo".equals (inputWord)) {
                    // uselessWords 非空则移除 uselessWords 栈顶的元素,添加到 usefulWords 集合
                    if (!uselessWords.empty ()) {
                        usefulWords.push (uselessWords.pop ());
                    }
                } else {
                    // 把输入的字符串添加到 usefulWords 集合中,加空格为排版~~
                    usefulWords.push (inputWord + " ");
                }
            }

            // 显示输入的数据
            System.out.print ("目前文章:");
            usefulWords.forEach (System.err::print);

            // 为显示效果,睡 0.1 秒再执行下一次循环
            Thread.sleep (100);
            // 添加空格排版~~~
            System.out.println ();
        }
    }
}

redo只有遇到undo才有意义，undo如果没被redo抵消，则会撤销在redo出现前的字符串

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] arr = scanner.nextLine().split(" ");
        Stack stack = new Stack();
        StringBuilder builder = new StringBuilder();
        for(String s:arr){
            // 遇到普通字符入栈
            // 遇到undo，暂时放入栈中
            // 遇到redo，碰到undo则抵消
            if(s.equals("redo")){
                if(stack.peek().equals("undo")){
                    stack.pop();
                }
            }else{
                stack.push(s);
            }
        }
        while(!stack.isEmpty()){
            String s = stack.pop();
            if(s.equals("undo")){
                stack.pop();
            }else{
                builder.insert(0," "+s);
            }
        }
        System.out.println(builder.substring(1).toString());
    }
}

测试用例通不过的问题在于undo与redo一定要在一起才能生效，且有可能出现叠加状态。通过l类似于栈的用法，连续undo时++,遇到redo--,遇到普通字符清零。然后就是基本的栈用法了

#include <bits/stdc++.h>
using namespace std;
int main(){
    string tmp;
    stack<string> undoer;
    vector<string> anss;
    int l=0;
    while(cin>>tmp){
        if(tmp=="undo"){
            if(anss.size()){             
                undoer.push(anss.back());
                anss.pop_back();
                l++;
            }
        }else
        if(tmp=="redo"){
            if(l>0&&undoer.size()){
                anss.push_back(undoer.top());
                undoer.pop();
                l--;
            }
        }else{
            anss.push_back(tmp);
            l=0;
        }
    }
    for(int i=0;i<anss.size();i++){
        if(i!=anss.size()-1){
            cout<<anss[i]<<" ";
        }else
            cout<<anss[i]<<endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(" ");
        Deque<String> stack = new LinkedList<>();
        Deque<String> res = new LinkedList<>();
        for (String value : s) {
            if (value.equals("undo")) {
                if (!res.isEmpty()) {
                    stack.push(res.pop());
                }
                continue;
            }
            if (value.equals("redo")) {
                if (!stack.isEmpty()) {
                    res.push(stack.pop());
                }
                continue;
            }
            res.push(value);
            stack.clear();
        }
        StringBuilder sb = new StringBuilder();
        while (!res.isEmpty()) {
            sb.insert(0, res.pop() + " ");
        }
        System.out.println(sb);
        sc.close();
    }
}

package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	str, _ := reader.ReadString('\n')
	str = str[:len(str)-1]
	strs := strings.Split(str, " ")
	ans := []string{}
	start, end := 0, 0
	m := map[string]int{}
	for i := 0; i < len(strs); i++ {
		if strs[i] == "redo" || strs[i] == "undo" {
			end = i
			for strs[i] == "redo" || strs[i] == "undo" {
				if strs[i] == "redo" && m["undo"] > 0 {
					m["undo"]--
				}
				if strs[i] == "undo" {
					m["undo"]++
				}
				i++
			}
			end -= m["undo"]
			ans = append(ans, strs[start:end]...)
			start = i
			end = i
		}
		if i == len(strs)-1 {
			ans = append(ans, strs[start:]...)
		}
	}
	s := ""
	for i := 0; i < len(ans); i++ {
		s += ans[i] + " "
	}
	fmt.Println(s)
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String seg;
        String line = sc.nextLine();
        if (line.contains(" ")) {
            seg = " ";
        } else {
            seg = "\t";
        }
        String[] ss = line.split(seg);
        sc.close();
        Stack<String> stack = new Stack<>();
        Stack<String> undo = new Stack<>();
        
        for (String s : ss) {
            if ("redo".equals(s)) {
                if (!undo.isEmpty()) {
                    stack.push(undo.pop());
                }
            } else if ("undo".equals(s)) {
                if (!stack.isEmpty()) {
                    undo.push(stack.pop());
                }
            } else {
                undo.clear();
                stack.push(s);
            }
        }
        
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.insert(0, stack.pop()).insert(0, " ");
        }
        if (sb.length() > 0) 
            System.out.println(sb.substring(1));
    }
}

#include<bits/stdc++.h>
using namespace std;

int main() {
    vector<string> undo_queue, words;
    string s;
    while (cin >> s) {
        char ch = getchar();
//遇到undo时，将words的最后一个单词放进undo_queue中，然后弹出这个单词
        if (s == "undo") {
            if (!words.empty()) {
                undo_queue.push_back(words.back());
                words.pop_back();
            }
        }
//遇到redo时，将undo_queue中的最后一个词取出放回到words中，并弹出这个词
        else if (s == "redo") {
            if (!undo_queue.empty()) {
                words.push_back(undo_queue.back());
                undo_queue.pop_back();
            }
        }
//遇到普通词直接放进words中，并且要清空undo_queue，因为插入的新的词以后undo_queue里的数据已经不是最新的了
        else {
            words.push_back(s);
            undo_queue = vector<string>();
        }
        if (ch == '\n')
            break;
    }
    for (auto word : words) {
        cout << word << " ";
    }
    return 0;
}

package main
import(
    "os"  
    "bufio"
    "fmt"
    "strings"
)

func RedoUndoStr(str string) string{
    strList := strings.Split(str," ")
    stack := make([]string,0)
    redo := make([]string,0)
    for _,val:=range strList{
        if val=="redo"{
            if len(redo)>0{
                stack=append(stack, redo[len(redo)-1])
                redo=redo[:len(redo)-1]
            }
        }else if val=="undo"{
            if len(stack)>0{
                redo=append(redo, stack[len(stack)-1])
                stack=stack[:len(stack)-1]
            }
        }else{
            redo=redo[:0]
            stack=append(stack, val)
        }
    }
    return strings.Join(stack," ")
}
func main(){
    reader:=bufio.NewReader(os.Stdin)
    str,_:=reader.ReadString('\n')
    fmt.Println(RedoUndoStr(str))
}