मान लें कि हमारे पास क्स्प एक्सप्रेशन है, और हमें यह जांचना होगा कि क्स्प के चारों ओर कोष्ठकों का डुप्लिकेट सेट है या नहीं। एक व्यंजक में डुप्लिकेट कोष्ठक होंगे यदि एक उप-अभिव्यक्ति एक से अधिक कोष्ठकों के सेट से घिरी होगी। उदाहरण के लिए, यदि व्यंजक −
. जैसा है(5+((7−3)))
यहाँ उप-अभिव्यक्ति (7 - 3) दो कोष्ठक युग्मों से घिरी हुई है, इसलिए ये डुप्लिकेट कोष्ठक हैं।
इस समस्या को हल करने के लिए, हम ढेर का उपयोग करेंगे। हम क्स्प में प्रत्येक चरित्र के माध्यम से पुनरावृति करेंगे, और यदि चरित्र कोष्ठक '(', या किसी भी ऑपरेटर या ऑपरेंड को खोल रहा है, तो इसे स्टैक में धकेलें। जब चरित्र कोष्ठक बंद कर रहा हो, तो स्टैक से वर्णों को बार-बार पॉप करें जब तक मिलते-जुलते शुरुआती कोष्ठक नहीं मिल जाते हैं, और एक काउंटर का उपयोग किया जाता है, जिसका मूल्य कोष्ठकों के खुलने और बंद होने के बीच सामने आने वाले प्रत्येक वर्ण के लिए बढ़ाया जाएगा। जो काउंटर के मूल्य के बराबर है, 1 से कम है, फिर डुप्लिकेट कोष्ठक की जोड़ी पाया जाता है, अन्यथा नहीं मिला।
उदाहरण
#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 ";
} आउटपुट
Duplicate parentheses has Found