[DSA] Đảo ngược chuỗi dùng Stack

Viết chương trình để đảo ngược chuỗi dùng Stack

1. Hàm main viết 10 test case

#include <stdio.h>

#include <string.h>

#define MAX_LEN 100

// Define a stack structure

struct Stack {

char data[MAX_LEN];

int top;

};

// Function to initialize the stack

void initStack(struct Stack* stack) {

stack->top = -1;

}

// Function to push an element onto the stack

void push(struct Stack* stack, char value) {

if (stack->top >= MAX_LEN - 1) {

printf("Stack overflow\n");

return;

}

stack->top++;

stack->data[stack->top] = value;

}

// Function to pop an element from the stack

char pop(struct Stack* stack) {

if (stack->top < 0) {

printf("Stack underflow\n");

return '\0';

}

char value = stack->data[stack->top];

stack->top--;

return value;

}

// Function to reverse the order of words in a sentence

void reverseWords(char sentence[]) {

// Initialize the stack and the word buffer

struct Stack stack;

initStack(&stack);

char word[MAX_LEN];

int wordIndex = 0;

// Loop through each character in the sentence

for (int i = 0; i <= strlen(sentence); i++) {

char c = sentence[i];

// If the current character is a space or null terminator, push the word onto the stack

if (c == ' ' || c == '\0') {

word[wordIndex] = '\0';

if (wordIndex > 0) {

for (int j = 0; j < wordIndex; j++) {

push(&stack, word[j]);

}

push(&stack, ' ');

}

wordIndex = 0;

}

// Otherwise, add the current character to the word buffer

else {

word[wordIndex] = c;

wordIndex++;

}

}

// Pop characters from the stack to print the reversed sentence

while (stack.top >= 0) {

printf("%c", pop(&stack));

}

}

int main() {

char sentence[MAX_LEN];

// Test cases

printf("Test case 1:\n");

strcpy(sentence, "Hello world, how are you?");

printf("- Input: %s\n- Output: ", sentence);

reverseWords(sentence);

printf("\n");

printf("Test case 2:\n");

strcpy(sentence, "The quick brown fox jumps over the lazy dog");

printf("- Input: %s\n- Output: ", sentence);

reverseWords(sentence);

printf("\n");

printf("Test case 3:\n");

strcpy(sentence, "Stacks are awesome!");

printf("- Input: %s\n- Output: ", sentence);

reverseWords(sentence);

printf("\n");

printf("Test case 4:\n");

strcpy(sentence, "Hello, there");

printf("- Input: %s\n- Output: ", sentence);

reverseWords(sentence);

printf("\n");

printf("Test case 5:\n");

strcpy(sentence, "Hello how are");

printf("- Input: %s\n- Output: ", sentence);

reverseWords(sentence);

printf("\n");

printf("Test case 6:\n");

strcpy(sentence, "123 456 789");

printf("- Input: %s\n- Output: ", sentence);

reverseWords(sentence);

printf("\n");

printf("Test case 7:\n");

strcpy(sentence, "");

printf("- Input: %s\n- Output: ", sentence);

reverseWords(sentence);

printf("\n");

printf("Test case 8:\n");

strcpy(sentence, " ");

printf("- Input: %s\n- Output: ", sentence);

reverseWords(sentence);

printf("\n");

printf("Test case 9:\n");

strcpy(sentence, "a b c");

printf("- Input: %s\n- Output: ", sentence);

reverseWords(sentence);

printf("\n");

printf("Test case 10:\n");

strcpy(sentence, "I am testing a program");

printf("- Input: %s\n- Output: ", sentence);

reverseWords(sentence);

printf("\n");

}

2. Nâng cấp hàm main cho ngắn gọn hơn 

Chú ý: các bạn có thể sửa hàm main trên thành main1 để chạy đoạn lệnh sau trong cùng 1 file với đoạn lệnh trên

int main() {

char sentences[10][100] = {

"Hello world, how are you?",

"The quick brown fox jumps over the lazy dog",

"This is a test",

"To be or not to be, that is the question",

"A man a plan a canal Panama",

"The cat in the hat",

"I am the walrus",

"The sky is blue",

"An apple a day keeps the doctor away",

"May the force be with you"

};

for (int i = 0; i < 10; i++) {

printf("Test case %d \n", (i+1));

printf("- Input: %s\n- Output: ", sentences[i]);

reverseWords(sentences[i]);

printf("\n----------------\n");

}

return 0;

}