- Giới thiệu về giải thuật
Stack là một cấu trúc dữ liệu phổ biến, hoạt động theo nguyên tắc Last-In-First-Out (LIFO). Có thể sử dụng stack từ thư viện STL hoặc mô phỏng bằng mảng . Khó khăn khi giải các bài toán liên quan đến stack thường nằm ở việc có nhận ra được rằng bài toán có thể giải quyết bằng stack hay không. Thực chất, các bài toán này thường yêu cầu mô phỏng quy trình xử lý với sự hỗ trợ của stack. Sau đây chúng ta sẽ phân tích một số bài toán để hiểu rõ hơn cách stack được áp dụng trong giải thuật.
- Nguyên lý và thực hiện mã nguồn
Bài toán 1: Xóa tất cả các cặp ký tự lặp lại kề nhau
Nguyên lý giải thuật:
Qua phân tích, đây là một ứng dụng điển hình của stack. Ta duyệt qua chuỗi gốc, thêm từng ký tự s[i] vào stack. Khi thêm, cần kiểm tra nếu phần tử trên đỉnh stack giống với ký tự hiện tại thì loại bỏ phần tử đó khỏi stack, ngược lại thì thêm ký tự vào stack.
Chi tiết cần lưu ý:
Không nhất thiết phải tạo stack thật, vì nếu dùng stack thì sau cùng vẫn phải trích xuất các phần tử từ stack và đảo ngược chúng, khá phức tạp. Do đó, có thể dùng mảng string để mô phỏng stack. Nếu ký tự cuối cùng trong mảng trùng với ký tự muốn thêm vào, ta xóa ký tự cuối cùng; ngược lại thì thêm vào cuối mảng.
Thực thi mã nguồn:
class Solution {
public:
string removeDuplicates(string s) {
string result;
for(char c : s) {
if(!result.empty() && result.back() == c) {
result.pop_back();
} else {
result += c;
}
}
return result;
}
};
Bài toán 2: So sánh hai chuỗi chứa ký tự backspace
Nguyên lý giải thuật:
Bài toán tương tự như bài trước, cũng áp dụng stack để xử lý. Có thể dùng mảng để mô phỏng stack.
Thực thi mã nguồn:
class Solution {
public:
bool backspaceCompare(string s, string t) {
return processString(s) == processString(t);
}
private:
string processString(const string& str) {
string result;
for(char c : str) {
if(c == '#' && !result.empty()) {
result.pop_back();
} else if(c != '#') {
result += c;
}
}
return result;
}
};
Bài toán 3: Máy tính cơ bản II
Nguyên lý giải thuật:
Đây là dạng bài toán "đánh giá biểu thức", phương pháp thông dụng là sử dụng stack (có thể là một stack hoặc hai stack) để mô phỏng quá trình tính toán.
Quy trình giải thuật: (1) Gặp toán tử, cập nhật toán tử op (2) Gặp số, làm hai bước: a. Trích xuất số tmp b. Dựa vào op để xử lý: - op == '+' : Thêm tmp vào stack - op == '-' : Thêm -tmp vào stack - op == '*' : Nhân số trên đỉnh stack với tmp - op == '/' : Chia số trên đỉnh stack cho tmp
Thực thi mã nguồn 1: Sử dụng stack từ STL
class Solution {
public:
int calculate(string s) {
char op = '+';
stack<int> cal;
int i = 0;
while(i < s.size()) {
// Bỏ qua khoảng trắng
while(i < s.size() && s[i] == ' ') i++;
if(i >= s.size()) break;
// Trích xuất số
int num = 0;
while(i < s.size() && isdigit(s[i])) {
num = num * 10 + (s[i++] - '0');
}
if(op == '+') cal.push(num);
else if(op == '-') cal.push(-num);
else if(op == '*') {
int temp = cal.top(); cal.pop();
cal.push(temp * num);
}
else if(op == '/') {
int temp = cal.top(); cal.pop();
cal.push(temp / num);
}
// Cập nhật toán tử mới
if(i < s.size()) op = s[i++];
}
int res = 0;
while(!cal.empty()) {
res += cal.top();
cal.pop();
}
return res;
}
};
Thực thi mã nguồn 2: Sử dụng vector để mô phỏng stack
class Solution {
public:
int calculate(string s) {
vector<int> st;
char op = '+';
int i = 0;
while(i < s.size()) {
if(s[i] == ' ') { i++; continue; }
if(isdigit(s[i])) {
int num = 0;
while(i < s.size() && isdigit(s[i])) {
num = num * 10 + (s[i++] - '0');
}
if(op == '+') st.push_back(num);
else if(op == '-') st.push_back(-num);
else if(op == '*') st.back() *= num;
else if(op == '/') st.back() /= num;
} else {
op = s[i++];
}
}
int res = 0;
for(auto val : st) res += val;
return res;
}
};
Bài toán 4: Giải mã chuỗi
Nguyên lý giải thuật:
Từ trái sang phải khi duyệt chuỗi, gặp số hoặc ký tự cần lưu trữ tạm thời, khi gặp dấu đóng ngoặc vuông thì lấy số và chuỗi gần nhất để giải mã. Điều này phù hợp với đặc điểm LIFO của stack.
Quy trình giải thuật: Sử dụng hai stack: "Stack chuỗi": Lưu chuỗi. "Stack số": Lưu số đã gặp. (1) Gặp số, trích xuất và đẩy vào stack số. (2) Gặp '[': Trích xuất chuỗi sau đó đẩy vào stack chuỗi. (3) Gặp ']': Dùng số từ stack số để nhân chuỗi từ stack chuỗi, sau đó nối kết quả vào chuỗi đang đứng đầu stack chuỗi. (4) Gặp ký tự đơn lẻ: Nối nó vào chuỗi đang đứng đầu stack chuỗi.
Chi tiết cần lưu ý: Trong stack chuỗi, nên khởi tạo với một chuỗi rỗng để tránh lỗi khi truy cập phần tử trên đỉnh stack khi stack trống.
Thực thi mã nguồn:
class Solution {
public:
string decodeString(string s) {
stack<string> strStack;
stack<int> numStack;
strStack.push("");
for(int i = 0; i < s.size(); ++i) {
if(isdigit(s[i])) {
int num = 0;
while(i < s.size() && isdigit(s[i])) {
num = num * 10 + (s[i++] - '0');
}
numStack.push(num);
--i;
} else if(s[i] == '[') {
strStack.push("");
} else if(s[i] == ']') {
int repeat = numStack.top(); numStack.pop();
string tmp = strStack.top(); strStack.pop();
string decoded = "";
for(int j = 0; j < repeat; ++j) {
decoded += tmp;
}
strStack.top() += decoded;
} else {
strStack.top() += s[i];
}
}
return strStack.top();
}
};
Bài toán 5: Kiểm tra thứ tự stack
Nguyên lý giải thuật:
Kiểm tra thứ tự stack bằng cách mô phỏng quá trình push/pop. Push lần lượt các phần tử từ dãy push vào stack, đồng thời duyệt qua dãy pop, mỗi lần push kiểm tra nếu phần tử trên đỉnh stack trùng với phần tử hiện tại trong dãy pop thì pop ra khỏi stack. Sau khi hoàn thành, kiểm tra xem dãy pop đã duyệt hết chưa (hoặc stack có còn rỗng không).
Thực thi mã nguồn:
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> stk;
int j = 0;
for(auto x : pushed) {
stk.push(x);
while(!stk.empty() && j < popped.size() && stk.top() == popped[j]) {
stk.pop();
j++;
}
}
return stk.empty();
}
};
- Tổng kết giải thuật
Từ các bài toán trên, dễ thấy rằng các bài toán liên quan đến stack đều thuộc dạng mô phỏng. Có thể chọn giữa việc sử dụng stack từ thư viện STL hoặc mô phỏng bằng mảng dựa trên yêu cầu cụ thể của bài toán. Quan trọng là cần phân tích kỹ quá trình xử lý và chuyển hóa thành mã nguồn chính xác.