Biểu thức cân bằng của dấu ngoặc là một biểu thức chứa các cặp của tất cả các loại dấu ngoặc đơn với nhau theo một thứ tự đúng. Điều này có nghĩa là đối với mỗi dấu ngoặc đơn mở, thì có một dấu ngoặc đóng theo thứ tự thích hợp của dấu ngoặc đơn, tức là {}.
hãy lấy một vài ví dụ để hiểu rõ hơn về khái niệm này -
Biểu thức - {([] [] {}) ({} [] {})}
Đầu ra - cân bằng
Giải thích - chúng ta có thể thấy rằng đối với mọi dấu ngoặc mở đều có một dấu ngoặc đóng. tất cả các dấu ngoặc đơn nằm giữa dấu ngoặc đơn mở và dấu ngoặc đơn đóng trong Cặp.
Đầu ra - không cân bằng
Giải thích - có một số cặp dấu ngoặc đơn không có thứ tự làm cho biểu thức không cân bằng.
Trong bài toán này được gọi là biểu thức số dư có thay thế , chúng ta được cung cấp một chuỗi có chứa biểu thức của các dấu ngoặc này ‘{’, ‘}’, ‘[’, ‘]’, ‘(’, ‘)’. có một số chỗ thiếu dấu ngoặc và “*” được đặt thay thế. Và chúng ta phải kiểm tra xem thời tiết khi thay thế tất cả các biểu tượng dấu hoa thị bằng các dấu ngoặc thích hợp thì biểu thức đã cho có thể trở thành biểu thức hợp lệ hay không.
Ví dụ
Đầu vào - exp =“{[* (*)]}”
Đầu ra - biểu thức có thể được cân bằng
Giải thích - Có hai ký hiệu cần được thay thế. Và khi thay thế sẽ trở thành {[(())]}
Đầu vào - exp =“[(*) {} {{}}]”
Đầu ra - biểu thức không thể cân bằng
Giải thích - Có một ký hiệu cần được thay thế. Và khi thay thế * bằng bất kỳ dấu ngoặc nào, biểu thức không thể được cân bằng.
Bây giờ vì chúng tôi đã hiểu rõ về vấn đề, chúng tôi có thể tạo ra giải pháp cho vấn đề này. Để kiểm tra xem một biểu thức trong dấu ngoặc đơn nhất định có được cân bằng hay không, chúng tôi sẽ sử dụng cấu trúc dữ liệu ngăn xếp để thực hiện các tác vụ của mình.
Hoạt động được thực hiện để hoàn thành nhiệm vụ này là -
-
Duyệt qua mọi phần tử của biểu thức chuỗi và thực hiện -
-
Khi gặp dấu ngoặc mở trong biểu thức, tức là ‘{’, ‘[’, ‘(’, hãy đẩy phần tử trong ngăn xếp.
-
Khi gặp dấu ngoặc đóng trong biểu thức, tức là ‘}’, ‘]’, ‘)’. Bật phần tử ở đầu ngăn xếp và kiểm tra xem đây có phải là phần mở phù hợp cho dấu ngoặc đóng gặp phải không.
-
Nếu cả hai dấu ngoặc đơn đều khớp, thì hãy chuyển sang phần tử tiếp theo của biểu thức (bước 1).
-
Nếu cả hai dấu ngoặc đơn không khớp thì biểu thức không cân bằng.
-
-
Khi bắt gặp dấu * trong biểu thức, có thể là dấu ngoặc mở cũng như đóng ngoặc. Sau đó,
-
Trước tiên, hãy coi nó như một dấu ngoặc mở và đẩy nó vào ngăn xếp và tìm một dấu ngoặc đóng phù hợp bằng cách sử dụng lệnh gọi đệ quy cho phần tử tiếp theo. Nếu điều này dẫn đến lỗi, hãy làm theo bước tiếp theo
-
Coi nó như là dấu ngoặc nhọn đóng, nó phải khớp với đỉnh của ngăn xếp rồi mới bật lên trên cùng của ngăn xếp.
-
Giá trị đóng của * không khớp với lợi tức mở không được cân bằng.
-
-
In báo cáo dựa trên kết quả.
Ví dụ
Dựa trên giải pháp này, chúng ta hãy tạo một chương trình
#include <bits/stdc++.h>
using namespace std;
int isMatching(char a, char b){
if ((a == '{' & b == '}') || (a == '[' & b == ']') || (a == '(' & b == ')') || a == '*')
return 1;
return 0;
}
int isBalancedexpression(string s, stack<char> ele, int ind){
if (ind == s.length())
return ele.empty();
char topEle;
int res;
if (s[ind] == '{' || s[ind] == '(' || s[ind] == '[') {
ele.push(s[ind]);
return isBalancedexpression(s, ele, ind + 1);
}
else if (s[ind] == '}' || s[ind] == ')' || s[ind] == ']') {
if (ele.empty())
return 0;
topEle = ele.top();
ele.pop();
if (!isMatching(topEle, s[ind]))
return 0;
return isBalancedexpression(s, ele, ind + 1);
}
else if (s[ind] == '*') {
stack<char> tmp = ele;
tmp.push(s[ind]);
res = isBalancedexpression(s, tmp, ind + 1);
if (res)
return 1;
if (ele.empty())
return 0;
ele.pop();
return isBalancedexpression(s, ele, ind + 1);
}
}
int main(){
string s = "{[*(*)]}";
stack ele;
if (isBalancedexpression(s, ele, 0))
cout << "Balanced";
else
cout << "Not Balanced";
return 0;
} Đầu ra
Balanced