โปรแกรม C++ ตรวจสอบนิพจน์สมดุลด้วยการแทนที่อักขระ *

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

มาดูตัวอย่างเพื่อเข้าใจแนวคิดดีขึ้น −

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

ผลลัพธ์ − balanced

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

ผลลัพธ์ − not balance

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

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

ตัวอย่าง

อินพุต − exp = "{[*(*)]}"

เอาต์พุต − the expression can be balanced

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

อินพุต − exp = "[(*){}{{}}]"

เอาต์พุต − the expression cannot be balanced

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

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

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

• วนทุกสมาชิกของสตริงนิพจน์และทำ −
• เมื่อพบวงเล็บเปิดในนิพจน์ เช่น '{', '[', '(' ให้ push เข้า stack
• เมื่อพบวงเล็บปิดในนิพจน์ เช่น '}', ']', ')' ให้ pop สมาชิกที่บนสุดของ stack และตรวจสอบว่าตรงกับวงเล็บเปิดสำหรับวงเล็บปิดที่พบหรือไม่
  • ถ้าวงเล็บทั้งคู่ตรงกัน ให้ไปสมาชิกถัดไปของนิพจน์ (ขั้นตอน 1)
  • ถ้าวงเล็บทั้งคู่ไม่ตรงกัน นิพจน์ ไม่สมดุล
• เมื่อพบ * ในนิพจน์ซึ่งอาจเป็นวงเล็บเปิดหรือปิด ก็ทำ −
  • ก่อนถือเป็นวงเล็บเปิดและ push เข้า stack และหาวงเล็บปิดที่ตรงกันด้วยการเรียกซ้ำสำหรับสมาชิกถัดไป หากผลลัพธ์เป็น false ทำขั้นตอนถัดไป
  • ถือเป็นวงเล็บปิด ต้องตรงกับบนสุดของ stack แล้ว pop บนสุดของ stack
  • ถ้าค่าปิดของ * ไม่ตรงกับค่าเปิด คืนค่า not balanced
• พิมพ์ข้อความตามผลลัพธ์

ตัวอย่าง

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

#include <bits/stdc++.h> 
using namespace std; 

int isMatching(char a, char b){ 
    if ((a == '{' && b == '}') || (a == '[' && b == ']') || (a == '(' && 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