โปรแกรม C++ ตรวจสอบว่านิพจน์มีวงเล็บซ้ำหรือไม่

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

(5+((7-3)))

ที่นี่ sub-expression (7 - 3) ถูกล้อมรอบด้วยสองคู่วงเล็บ ดังนั้นนี่คือวงเล็บซ้ำ

เพื่อแก้ปัญหานี้ เราจะใช้ stack เราจะวนลูปผ่านแต่ละตัวอักษรใน exp และหากตัวอักษรเป็นวงเล็บเปิด '(' หรือตัวดำเนินการหรือตัวถูกดำเนินการ ให้ push เข้า stack เมื่อตัวอักษรเป็นวงเล็บปิด ให้ pop ตัวอักษรจาก stack จนกว่าจะพบวงเล็บเปิดที่ตรงกัน และตัวนับถูกใช้ ซึ่งค่าจะเพิ่มขึ้นสำหรับทุกตัวอักษรที่พบระหว่างคู่วงเล็บเปิดและปิด ซึ่งถ้าค่าของตัวนับน้อยกว่า 1 แสดงว่าพบคู่วงเล็บซ้ำ มิฉะนั้นไม่พบ

ตัวอย่างโค้ด C++

#include <iostream>
#include <stack>
using namespace std;

bool hasDuplicateParentheses(string str) {
    stack 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