ค้นหาว่านิพจน์มีวงเล็บซ้ำหรือไม่ใน C++

พิจารณาว่าเรามีนิพจน์ exp และเราต้องตรวจสอบว่า exp มีชุดวงเล็บที่ซ้ำกันล้อมรอบหรือไม่ นิพจน์จะมีวงเล็บที่ซ้ำกัน ถ้านิพจน์ย่อยหนึ่งรายการจะถูกล้อมรอบด้วยชุดวงเล็บมากกว่าหนึ่งชุด ตัวอย่างเช่น ถ้านิพจน์เป็นเหมือน −

(5+((7−3)))

ในที่นี้ นิพจน์ย่อย (7 – 3) ล้อมรอบด้วยวงเล็บสองคู่ ดังนั้นวงเล็บเหล่านี้จึงเป็นวงเล็บที่ซ้ำกัน

เพื่อแก้ปัญหานี้ เราจะใช้ stack เราจะวนซ้ำอักขระแต่ละตัวใน exp และถ้าตัวละครเปิดวงเล็บ '(' หรือโอเปอเรเตอร์หรือตัวถูกดำเนินการใดๆ ก็ตาม ให้ดันมันเข้าไปในสแต็ก เมื่อตัวละครปิดวงเล็บแล้ว ให้ป๊อปอักขระจากสแต็กซ้ำๆ จนกว่าจะพบวงเล็บเปิดที่ตรงกันและใช้ตัวนับซึ่งค่าจะเพิ่มขึ้นสำหรับอักขระทุกตัวที่พบระหว่างวงเล็บเปิดและวงเล็บปิดซึ่งเท่ากับค่าของตัวนับมีค่าน้อยกว่า 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