Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 교체가 포함된 균형 괄호 표현식 판별 알고리즘

균형 잡힌 괄호 표현식(balanced expression)이란 모든 종류의 괄호 쌍이 올바른 순서로 짝을 이루고 있는 식을 의미합니다. 즉, 여는 괄호마다 그에 대응하는 닫는 괄호가 정확한 순서({ }, [ ], ( ))로 존재해야 합니다.

몇 가지 예시를 통해 개념을 더 자세히 살펴보겠습니다.

표현식 – {([][]{})({}[]{})}

출력 – 균형 잡힘(balanced)

설명 – 모든 여는 괄호에 대해 그에 맞는 닫는 괄호가 존재하며, 짝을 이루는 괄호들이 안팎으로 올바르게 중첩되어 배치되어 있습니다.

표현식 – {(})

출력 – 균형 잡히지 않음(not balanced)

설명 – 순서가 어긋난 괄호 쌍이 존재하여 표현식 전체가 균형을 이루지 못합니다.

교체가 포함된 균형 표현식 문제란?

'교체가 포함된 균형 표현식(balance expression with replacement)' 문제에서는 '{', '}', '[', ']', '(', ')' 여섯 종류의 괄호로 이루어진 문자열이 주어집니다. 문자열의 일부 위치에는 괄호가 비어 있고 그 자리에 '*' 기호가 들어 있습니다. 우리의 과제는 모든 '*' 기호를 적절한 괄호로 교체했을 때, 주어진 표현식이 유효한 균형 잡힌 표현식이 될 수 있는지 확인하는 것입니다.

예시

입력 – exp = "{[*(*)]}"

출력 – 표현식은 균형을 이룰 수 있습니다.

설명 – 두 개의 '*' 기호를 교체하면 {[(())]}가 되어 균형이 맞습니다.

입력 – exp = "[(*){}{{}}]"

출력 – 표현식은 균형을 이룰 수 없습니다.

설명 – 하나의 '*' 기호를 어떤 괄호로 교체하더라도 표현식의 균형을 맞출 수 없습니다.

해결 접근 방법

문제를 명확히 이해했다면 이제 해결책을 세워볼 차례입니다. 주어진 괄호 표현식이 균형을 이루는지 확인하기 위해 스택(stack) 자료구조를 활용합니다.

이 작업을 수행하기 위한 연산 과정은 다음과 같습니다.

  • 문자열 표현식의 모든 요소를 순회하며 아래 작업을 수행합니다.

  • 여는 괄호('{', '[', '(')를 만나면 해당 요소를 스택에 push 합니다.

  • 닫는 괄호('}', ']', ')')를 만나면 스택의 최상단(top) 요소를 pop 하여, 현재 마주친 닫는 괄호와 짝이 맞는 여는 괄호인지 확인합니다.

    • 두 괄호가 서로 짝이 맞으면 표현식의 다음 요소로 넘어갑니다(1단계).

    • 짝이 맞지 않으면 해당 표현식은 균형이 맞지 않습니다.

  • '*'를 만나면 여는 괄호일 수도 있고 닫는 괄호일 수도 있으므로 다음과 같이 처리합니다.

    • 먼저 여는 괄호로 취급하여 스택에 push 한 뒤, 재귀 호출을 통해 다음 요소부터 매칭되는 닫는 괄호를 찾습니다. 결과가 거짓(false)이라면 다음 단계로 진행합니다.

    • 닫는 괄호로 취급하여 스택의 top과 일치하는지 확인하고, 일치한다면 스택의 top을 pop 합니다.

    • '*'를 닫는 괄호로 취급했을 때 스택의 여는 괄호와 일치하지 않으면 균형이 맞지 않음을 반환합니다.

  • 최종 결과에 따라 문장을 출력합니다.

이 알고리즘은 각 '*'마다 '여는 괄호'와 '닫는 괄호' 두 가지 경우를 모두 시도해야 하므로, '*'의 개수를 k라고 할 때 최악의 경우 O(2^k)의 시간 복잡도를 가집니다.

C++ 구현 예제

위에서 설명한 해결 방법을 바탕으로 프로그램을 작성해 보겠습니다.

#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);
    }
    return 0;
}
int main(){
    string s = "{[*(*)]}";
    stack<char> ele;
    if (isBalancedexpression(s, ele, 0))
        cout << "Balanced";
    else
        cout << "Not Balanced";
    return 0;
}

출력 결과

Balanced