Time limit: 2000ms
Memory limit: 256mb
Description:
In this exercise, we use stacks to implement a struct text, which support add, delete, undo and redo:
1. add: add a character at the end of the text;
2. delete: delete a character at the end of the text;
3. undo: undo the previous add or delete action;
4. redo: redo what was undone.
Note the followings:
1. The redo actions available resets once the user add or delete a character. (See step 14 below);
2. The user cannot delete if the text is empty.
Here is an example:
1. add 'a' ----> a [add]
2. add 'b' ----> ab [add]
3. add 'c' ----> abc [add]
4. delete ----> ab [delete]
5. undo ----> abc (undo step 4)
6. undo ----> ab (undo step 3)
7. redo ----> abc (redo step 3)
8. redo ----> ab (redo step 4)
9. redo ----> Show error message "Cannot redo."
10. undo ----> abc (undo step 4)
11. undo ----> ab (undo step 3)
12. undo ----> a (undo step 2)
13. add 'd' ----> ad [add]
14. redo ----> Show error message "Cannot redo."
15. undo ----> a (undo step 13)
16. undo ----> (undo step 1)
In this example, note that step 1, 2, 3, 4 and 13 are add and delete steps, while others are undo or redo.
We have provided the code template that accomplishes the task required. In the alogithm, we make use of two stacks, undo_stack and redo_stack, to track the possible undo and redo actions respectively. Please study the code for the implementation.
In this problem, tou are required to complete two functions to support undo and redo for struct text.
void delete(text* t);
In this function, you will output the error message "Cannot delete.\n" if the text is already empty; otherwise, you will delete the last character of the text, and record this change accordingly in your undo_stack.
- Hint: refer to the code of void add(text* t, char c).
void redo(text* t);
In this function, you will output the error message "Cannot redo.\n" if there are no redo actions possible; otherwise, you will redo what was undone according to the redo_stack, and record this change accordingly in your undo_stack and redo_stack.
- Hint: refer to the code of void undo(text* t).
Input format:
First line: an integer n, denoting the number of operations;
Second line: n characters separated by (n-1) spaces, chosen from the following characters:
- a character from a to z (lowercase): add this character to the text;
- D: delete;
- U: undo;
- R: redo.
Output format:
Output the error messages (if any) sequentially, and the final text.
Sample Input 1:
8
U D a b U R D R
Sample Output 1:
Cannot undo.
Cannot delete.
Cannot redo.
a
Sample Input 2:
16
a b c D U U R R R U U U d R U U
Sample Output 2:
Cannot redo.
Cannot redo.
-------------------------Copy the following code, complete it and submit-------------------------
/*
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100000
typedef enum{FALSE = 0, TRUE = 1} Boolean;
typedef enum{ADD = 0, DELETE = 1, ERR = 2} Action;
typedef struct{
Action action; // ADD or DELETE
char character;
}command;
typedef struct{
int size;
int top;
command* stacklist;
}stack;
typedef struct{
stack* undo_stack;
stack* redo_stack;
char* text_str;
}text;
stack *createStack(int size){
stack *s;
s = (stack*)malloc(sizeof(stack));
s->size =size;
s->stacklist = (command*)malloc(size * sizeof(command));
s->top = -1;
return s;
}
Boolean IsFull(stack *s){
if (s->top == s->size -1)
return TRUE;
else return FALSE;
}
Boolean IsEmpty(stack *s){
if (s->top == -1)
return TRUE;
else return FALSE;
}
void push(stack *s, Action action, char character){
if (!IsFull(s)){
s->top++;
s->stacklist[s->top].action = action;
s->stacklist[s->top].character = character;
}
}
command pop(stack *s){
command cmd;
if (!IsEmpty(s)){
cmd = s-> stacklist[s->top];
s->top--;
return cmd;
}else{printf("error\n"); return cmd;}
}
command top(stack *s){ return s->stacklist[s->top];}
void add(text* t, char c){
push(t->undo_stack, DELETE, c);
while(!IsEmpty(t->redo_stack)){
pop(t->redo_stack);
}
char c_str[2];
c_str[1] = '\0';
c_str[0] = c;
strcat(t->text_str, c_str);
}
void delete(text* t){
// code here
}
void undo(text* t)
{
if (IsEmpty(t->undo_stack)){
printf("Cannot undo.\n");
return;
}
command cmd = pop(t->undo_stack);
push(t->redo_stack, 1 - cmd.action, cmd.character);
if (cmd.action == DELETE){
int len_str = strlen(t->text_str);
if (len_str == 0){
printf("Cannot delete.\n");
return;
}
t->text_str[len_str-1] = '\0';
}
else if (cmd.action == ADD){
char c_str[2];
c_str[1] = '\0';
c_str[0] = cmd.character;
strcat(t->text_str, c_str);
}
}
void redo(text* t){
// code here
}
text* createText(char* raw_text, int size){
text *t;
t = (text*)malloc(sizeof(text));
t->redo_stack = createStack(20000);
t->undo_stack = createStack(20000);
t->text_str = malloc(MAX);
strcpy(t->text_str, "");
return t;
}
void printText(text* t)
{
printf("%s\n", t->text_str);
}
int main()
{
char cmd;
int n;
int i;
text* t = createText("", n);
scanf("%d\n", &n);
for (i=0; i<n; i++){
scanf("%c", &cmd);
if (i == n - 1) scanf("\n");
else scanf(" ");
if (cmd == 'D'){
delete(t);
}
else if (cmd == 'U'){
undo(t);
}
else if (cmd == 'R'){
redo(t);
}
else if (cmd >= 'a' && cmd <= 'z'){
add(t, cmd);
}
}
printText(t);
return 0;
}
-------------------------------------------End of Code-------------------------------------------