Giả sử chúng ta có một biểu thức. Biểu thức có một số dấu ngoặc đơn; chúng ta phải kiểm tra xem các dấu ngoặc có cân đối hay không. Thứ tự của các dấu ngoặc đơn là (), {} và []. Giả sử có hai chuỗi. “() [() {()}]” Điều này hợp lệ, nhưng “{[}]” không hợp lệ.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Duyệt qua biểu thức cho đến khi hết biểu thức
- nếu ký tự hiện tại đang mở ngoặc như (, {hoặc [, thì đẩy vào ngăn xếp
- nếu ký tự hiện tại đang đóng dấu ngoặc vuông như),} hoặc], thì xuất hiện từ ngăn xếp và
- kiểm tra xem dấu ngoặc nhọn có phải là dấu ngoặc nhọn bắt đầu tương ứng của dấu ngoặc nhọn hay không
- ký tự hiện tại thì ổn, ngược lại thì không cân bằng.
- Sau khi hết chuỗi, nếu vẫn còn một số dấu ngoặc bắt đầu trong ngăn xếp, thì chuỗi đó không được cân bằng.
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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 << "This is Balanced Expression";
else
cout << "This is Not Balanced Expression";
} Đầu vào
"()[(){()}]" Đầu ra
This is Balanced Expression