Ứng dụng Stack để đảo từ trong chuỗi

#1

Chào mọi người, hiện tại em học về Stack. Giáo viên có giao một bài tập ứng dụng về Stack cho em là dùng stack để đảo chuỗi ạ.
Input : Toi di hoc
Output: hoc di Toi

Em có ý tưởng thế này, đầu tiên mình chia mỗi từ thành từ stack riêng biệt sau đó nối lại với nhau, nhưng vẫn không thấy khả thi mấy. Nhưng theo em biết thì Stack nó theo mô hình First In, Last Out, thế nên chuỗi ouput chỉ có thể ra: coh id ioT chứ không thể nào xuất ra ouput như đề bài được. Anh chị nào có ý tưởng hay cách giải như nào xin em tham khảo với ạ. Em xin cảm ơn.

#2

Thay vì bạn dùng stack cho cả chuỗi thì dùng stack cho 1 word, các word ngăn cách nhau bởi space " ".

8 Likes
#3

Vậy theo ý anh, là đầu tiên cho input vào rồi cắt chuỗi thành từ word riêng biệt, mỗi word là một stack đúng không nhỉ ?

#4 
#include <iostream>
#include <string.h>

using namespace std;


struct Node
{
	string data;
	Node* pNext;
};
struct Stack
{
	Node* pTop;
};


Node* CreateNode(string x)
{
	Node* p = new Node;
	if (p == NULL)
		exit(1);
	else
	{
		p->data = x;
		p->pNext = NULL;
	}
	return p;
}


void CreateStack(Stack& s)
{
	s.pTop = NULL;
}


bool isEmpty(Stack s)
{
	if (s.pTop == NULL)
		return true;
	else
		return false;
}


void Push(Stack& s,Node*p)
{
	if (isEmpty(s) == true)
		s.pTop = p;
	else
	{
		p->pNext = s.pTop;
		s.pTop = p;
	}
}


void Pop(Stack& s,string &x)
{
   if(s.pTop == NULL)
      cout<<"Stack Underflow"<<endl;
   else 
   {
      cout<<s.pTop->data <<endl;
      s.pTop = s.pTop->pNext;
   }
}

void reverseString(Stack &s,Node *p,string str)
{
	int i = str.length(),j;
	p = s.pTop;
	while(p != NULL)
    {
        if(p->data[i] == ' ' && i != 0)
        { 
        	j = i + 1;
        	while(p->data[j] != ' ' && p->data[j] != '\0') 
            {
                    cout << p->data[j];
                    j++;
            }
            cout << " ";
        }
       	else if(i == 0)
        {
            j = i;
            while(p->data[j] != ' ')
            {
                cout << p->data[j];
                j++;
            }
        }
        i--;
    }
}


int main()
{	
	Stack s;
	CreateStack(s);
	string str;
	getline(cin, str);
	Node *p = CreateNode(str);
	Push(s,p);
	reverseString(s,p,str);
	Pop(s,str);
	return 0;
}

Code em đây ạ, nhưng mà khi chạy ra ouput thì nó báo lỗi gì ấy ạ :frowning:

#5

Lỗi gì là lỗi gì :rage: Hoặc là bạn tự copy lỗi vô google translate, hoặc post lỗi lên chứ :rage:

6 Likes
#6

Bạn đưa ra idea là mỗi từ mà lại implement là mỗi chữ cái.

2 Likes
#7

step1 : cho câu đó thành mảng các từ.
step2 : cho mảng này vào một stack.
step3 : xuất stack này ra là có câu đảo ngược rồi.

( java có sẵn method tách chuỗi split, addAll(…) để lưu vào stack,… )

2 Likes
#8

Đảo chuỗi trước, đảo từ sau hoặc ngược lại đều đúng.

3 Likes
#9

Em thấy không khả thi nên chuyển qua mỗi chữ cái xem thế nào ạ

#10

Ấy quên mất, xin lỗi ạ @@, hình như vòng lặp em để cho nó chạy vô tận nên nó báo String Subscript Out of Range ạ

#11

Em làm được rồi ạ, cảm ơn mọi người đã góp ý.

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?