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 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ệ.
Nhiệm vụ rất đơn giản; chúng tôi sẽ sử dụng ngăn xếp để làm điều này. Chúng ta nên làm theo các bước sau để có được giải pháp -
- 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], sau đó bật ra từ ngăn xếp và kiểm tra xem dấu ngoặc nhọn có phải là dấu ngoặc bắt đầu tương ứng của ký tự hiện tại hay không, nếu không 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ụ
#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 ra
This is Balanced Expression