สตริงวงเล็บที่ถูกต้องใน C++

สมมติว่าเรามีนิพจน์ นิพจน์มีวงเล็บบางส่วน เราต้องตรวจสอบวงเล็บว่าสมดุลหรือไม่ ลำดับของวงเล็บคือ (), {} และ [] สมมติว่ามีสองสตริง “()[(){()}]” สิ่งนี้ถูกต้อง แต่ “{[}]” ไม่ถูกต้อง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ข้ามผ่านนิพจน์จนหมด
  • ถ้าอักขระปัจจุบันกำลังเปิดวงเล็บเช่น (, { หรือ [ ให้กดเข้าไปในสแต็ก
  • หากอักขระปัจจุบันเป็นวงเล็บปิด เช่น ) } หรือ ] ให้ป๊อปอัปจากสแต็ก และ
  • ตรวจสอบว่าวงเล็บเปิดตรงกับวงเล็บเริ่มต้นของ
  • ตัวละครปัจจุบันก็ใช้ได้ ไม่งั้นไม่บาลานซ์
• หลังจากสตริงหมด หากมีวงเล็บเริ่มต้นเหลืออยู่ในสแต็ก สตริงจะไม่สมดุล

ตัวอย่าง(C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น −

#include <iostream>
#include <stack>
using namespace std;
bool isBalancedExp(string exp) {
   stack<char> stk;
   char x;
   for (int i=0; i<exp.length(); i++) {
      if (exp[i]=='('||exp[i]=='['||exp[i]=='{') {
         stk.push(exp[i]);
         continue;
      }
      if (stk.empty())
         return false;
      switch (exp[i]) {
      case ')':
         x = stk.top();
         stk.pop();
         if (x=='{' || x=='[')
            return false;
         break;
      case '}':
         x = stk.top();
         stk.pop();
         if (x=='(' || x=='[')
            return false;
         break;
      case ']':
         x = stk.top();
         stk.pop();
         if (x =='(' || x == '{')
            return false;
         break;
      }
   }
   return (stk.empty());
}
int main() {
   string expresion = "()[(){()}]";
   if (isBalancedExp(expresion))
      cout << "This is Balanced Expression";
   else
      cout << "This is Not Balanced Expression";
}

อินพุต

"()[(){()}]"

ผลลัพธ์

This is Balanced Expression