Cho một biểu thức exp, cần kiểm tra xem exp có chứa tập dấu ngoặc trùng lặp hay không. Biểu thức có dấu ngoặc trùng lặp nếu một biểu thức con bị bao quanh bởi nhiều hơn một cặp dấu ngoặc. Ví dụ biểu thức (5+((7-3))) thì biểu thức con (7-3) bị bao quanh bởi hai cặp dấu ngoặc, đây là dấu ngoặc trùng lặp.
Để giải quyết, sử dụng stack. Duyệt từng ký tự trong exp, nếu ký tự là dấu ngoặc mở '(' hoặc toán tử/ toán hạng thì đẩy vào stack. Khi gặp dấu ngoặc đóng, lặp lại lấy ký tự từ stack cho đến khi tìm thấy dấu ngoặc mở tương ứng, dùng biến đếm tăng cho mỗi ký tự giữa cặp ngoặc. Nếu giá trị đếm nhỏ hơn 1 thì tìm thấy cặp dấu ngoặc trùng lặp.
Ví dụ
#include<iostream> #include<stack> using namespace std; bool hasDuplicateParentheses(string str) { stack<char> stk; for (int i = 0; i<str.length(); i++) { char ch = str[i]; if (ch == ')') { char top = stk.top(); stk.pop(); int count = 0; while (top != '(') { count++; top = stk.top(); stk.pop(); } if(count < 1) { return true; } } else stk.push(ch); } return false; } int main() { string str = "(5+((7-3)))"; if (hasDuplicateParentheses(str)) cout << "Duplicate parentheses has Found"; else cout << "No Duplicates parentheses has Found "; }Kết quả
Duplicate parentheses has Found