Giả sử chúng ta có một biểu thức. Biểu thức có các dấu ngoặc; ta phải kiểm tra xem các dấu ngoặc có cân bằng hay không. Thứ tự ngoặc: (), {} và []. Ví dụ: "()[(){()}]" hợp lệ, nhưng "{[}]" không hợp lệ.
Để giải quyết, ta làm theo các bước:
- Duyệt biểu thức cho đến khi hết
- nếu ký tự hiện tại là ngoặc mở (, { hoặc [, đẩy vào stack
- nếu là ngoặc đóng ), } hoặc ], lấy từ stack, kiểm tra xem ngoặc lấy ra có phải ngoặc mở tương ứng không. Nếu đúng thì ổn, không thì không cân bằng.
- Sau khi duyệt xong, nếu còn ngoặc mở trong stack, chuỗi không cân bằng.
Ví dụ (C++)
Hãy xem triển khai sau:
#include <iostream> #include <stack> using namespace std; bool isBalancedExp(string exp) { stack<char> stk; char x; for (int i=0; i<exp.length(); i++) { if (exp[i]=='('||exp[i]=='['||exp[i]=='{') { stk.push(exp[i]); continue; } if (stk.empty()) return false; switch (exp[i]) { case ')': x = stk.top(); stk.pop(); if (x=='{' || x=='[') return false; break; case '}': x = stk.top(); stk.pop(); if (x=='(' || x=='[') return false; break; case ']': x = stk.top(); stk.pop(); if (x =='(' || x == '{') return false; break; } } return (stk.empty()); } int main() { string expresion = "()[(){()}]"; if (isBalancedExp(expresion)) cout << "Đây là biểu thức cân bằng"; else cout << "Đây là biểu thức không cân bằng"; }Input
"()[(){()}]"Output
Đây là biểu thức cân bằng