Work out what is left on the screen after someone types text and presses undo.
What to build
A stack of characters that follows a line of typing.
Requirements
- An ordinary character is typed: it is added to the text.
- The character
#means undo: it removes the last character still on the screen, and does nothing when the screen is empty. - Print the final text, or
emptyif nothing is left.
Input
One line of 1 to 100 characters, with no spaces.
Output
The final text, or empty.
Constraints
The line has only lowercase letters and #.
Example
Input:
abc#d
Output:
abd
Why it works
Undo always removes the most recent character that has not been removed yet. Last in, first out is exactly what a stack does.
Examples
Example 1 · Input
abc#d
Expected output
abd
Example 2 · Input
ab##
Expected output
empty
Hints
Hint 1
Push each ordinary character onto a stack of chars.
Hint 2
For a #, pop one character, but only if the stack is not empty.
Hint 3
The stack from bottom to top is the final text.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
char text[101], stack[101];
int top = -1;
scanf("%100s", text);
for (int i = 0; text[i] != '\0'; i++) {
if (text[i] == '#') {
if (top >= 0) top--;
} else {
stack[++top] = text[i];
}
}
if (top == -1) printf("empty");
for (int i = 0; i <= top; i++) printf("%c", stack[i]);
printf("\n");
return 0;
}