Tìm xem một biểu thức có dấu ngoặc đơn trùng lặp hay không trong C ++

Hãy xem xét chúng ta có một biểu thức exp và chúng ta phải kiểm tra xem exp có một tập hợp các dấu ngoặc đơn trùng lặp xung quanh nó hay không. Một biểu thức sẽ có các dấu ngoặc đơn trùng lặp nếu một biểu thức con sẽ được bao quanh bởi nhiều hơn một bộ dấu ngoặc đơn. Ví dụ:nếu biểu thức giống như -

(5+((7−3)))

Ở đây, biểu thức con (7 - 3) được bao quanh bởi hai cặp dấu ngoặc đơn, vì vậy đây là những cặp dấu ngoặc đơn trùng lặp.

Để giải quyết vấn đề này, chúng tôi sẽ sử dụng ngăn xếp. Chúng tôi sẽ lặp qua từng ký tự trong exp và nếu ký tự đó đang mở ngoặc '(', hoặc bất kỳ toán tử hoặc toán hạng nào, thì hãy đẩy nó vào ngăn xếp. Khi ký tự đóng ngoặc, sau đó liên tục bật các ký tự từ ngăn xếp cho đến khi tìm thấy cặp dấu ngoặc mở phù hợp và bộ đếm được sử dụng, giá trị của nó sẽ được tăng lên cho mọi ký tự gặp giữa cặp dấu ngoặc đơn mở và đóng. Giá trị nào bằng giá trị của bộ đếm, nhỏ hơn 1, thì cặp dấu ngoặc đơn trùng lặp được tìm thấy, nếu không thì không tìm thấy.

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 ";
}

Đầu ra

Duplicate parentheses has Found