C ++ นิพจน์ที่สมดุลพร้อมการแทนที่

นิพจน์ที่สมดุลของวงเล็บคือนิพจน์ที่มีคู่ของวงเล็บทั้งหมดเข้าด้วยกันในลำดับที่ถูกต้อง ซึ่งหมายความว่าสำหรับวงเล็บเปิดทุกอัน จะมีวงเล็บปิดในลำดับที่เหมาะสมของวงเล็บ เช่น { }.

มาดูตัวอย่างเพื่อทำความเข้าใจแนวคิดกันดีกว่า -

นิพจน์ − {([][]{})({}[]{})}

ผลผลิต − สมดุล

คำอธิบาย − เราจะเห็นได้ว่าวงเล็บเปิดทุกอันจะมีวงเล็บปิด วงเล็บทั้งหมดอยู่ระหว่างวงเล็บเปิดและวงเล็บปิดเป็นคู่

ผลผลิต - ไม่สมดุล

คำอธิบาย − มีวงเล็บคู่ที่ไม่เรียงลำดับซึ่งทำให้นิพจน์ไม่สมดุล

ในปัญหานี้เรียกว่า แสดงความสมดุลด้วยการแทนที่ เราได้รับสตริงที่มีนิพจน์ของวงเล็บเหล่านี้ '{' , '}' , '[' , ']' , '(' , ')' มีบางตำแหน่งที่วงเล็บหายไปและใส่ "*" แทนวงเล็บ และเราต้องตรวจสอบสภาพอากาศในการแทนที่สัญลักษณ์ดอกจันทั้งหมดด้วยวงเล็บที่เหมาะสม นิพจน์ที่กำหนดสามารถกลายเป็นนิพจน์ที่ถูกต้องได้

ตัวอย่าง

ป้อนข้อมูล − exp =“{[*(*)]}”

ผลผลิต − การแสดงออกสามารถสมดุลได้

คำอธิบาย − มีสองสัญลักษณ์ที่ต้องเปลี่ยน และการแทนที่จะกลายเป็น {[(())]}

ป้อนข้อมูล − exp =“[(*){}{{}}]”

ผลผลิต − นิพจน์ไม่สามารถสมดุลได้

คำอธิบาย − มีหนึ่งสัญลักษณ์ที่ต้องเปลี่ยน และเมื่อแทนที่ * ด้วยวงเล็บปีกกาใดๆ นิพจน์จะไม่สามารถปรับสมดุลได้

เนื่องจากเราเข้าใจปัญหาอย่างชัดเจนแล้ว เราจึงสามารถสร้างวิธีแก้ปัญหาสำหรับปัญหานี้ได้ ในการตรวจสอบว่านิพจน์วงเล็บที่กำหนดจะสมดุลหรือไม่ เราจะใช้โครงสร้างข้อมูลสแต็กเพื่อทำงานของเรา

การดำเนินการที่ดำเนินการเพื่อให้บรรลุภารกิจนี้คือ −

• สำรวจทุกองค์ประกอบของนิพจน์สตริงและทำ -

• เมื่อพบวงเล็บเปิดในนิพจน์เช่น '{' , '[' , '(' ให้ดันองค์ประกอบในสแต็ก

• เมื่อพบวงเล็บปิดในนิพจน์เช่น '}' , ']' , ')' เปิดองค์ประกอบที่ด้านบนของสแต็กและตรวจสอบว่านี่เป็นช่องเปิดที่ตรงกันสำหรับวงเล็บปิดที่พบหรือไม่

  • หากวงเล็บทั้งสองตรงกัน ให้ย้ายไปยังองค์ประกอบถัดไปของนิพจน์ (ขั้นตอนที่ 1)

  • หากวงเล็บทั้งสองไม่ตรงกัน แสดงว่านิพจน์ ไม่สมดุล

• เมื่อพบ * ในนิพจน์ซึ่งสามารถเป็นวงเล็บเปิดและปิดได้ จากนั้น

  • ขั้นแรกให้ถือว่าเป็นวงเล็บเปิดและดันเข้าไปในสแต็กและค้นหาวงเล็บปิดที่ตรงกันโดยใช้การเรียกซ้ำสำหรับองค์ประกอบถัดไป หากผลลัพธ์เป็น fasle ให้ทำตามขั้นตอนต่อไป

  • ถือว่าเป็นวงเล็บปิด โดยจะต้องตรงกับส่วนบนของสแต็ก จากนั้นจึงเปิดส่วนบนของสแต็ก

  • เป็นค่าปิดของ * ไม่ตรงกับการเปิดผลตอบแทนไม่สมดุล

• พิมพ์ข้อความตามผลลัพธ์

ตัวอย่าง

จากโซลูชันนี้ มาสร้างโปรแกรมกันเถอะ

#include <bits/stdc++.h>
using namespace std;
int isMatching(char a, char b){
   if ((a == '{' &amp; b == '}') || (a == '[' &amp; b == ']') || (a == '(' &amp; 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;
}

ผลลัพธ์

Balanced