C++에서 주어진 여는 괄호에 대응하는 닫는 괄호의 인덱스 찾기

괄호가 포함된 표현식이 있을 때, 특정 여는 괄호의 인덱스가 주어지면 그 괄호에 대응하는 닫는 괄호의 위치를 찾아야 하는 경우가 있습니다. 예를 들어 표현식이 (25*6+(88-32+(50/10)+20))이고 여는 괄호의 인덱스가 6이라면, 그에 대응하는 닫는 괄호는 인덱스 23에 위치합니다.

해결 접근 방법: 스택 활용

이 문제는 스택(Stack) 자료구조를 사용하면 효율적으로 해결할 수 있습니다. 알고리즘의 동작 과정은 다음과 같습니다.

1. 주어진 인덱스부터 표현식을 순회하며 시작합니다.
2. 여는 괄호 '('를 만나면 스택에 push 합니다.
3. 닫는 괄호 ')'를 만나면 스택에서 pop 합니다.
4. pop 이후 스택이 비어 있다면, 그 지점이 바로 찾고자 하는 닫는 괄호의 인덱스입니다.

만약 주어진 인덱스의 문자가 여는 괄호가 아니거나, 순회가 끝날 때까지 스택이 비어지지 않으면 짝이 되는 닫는 괄호가 존재하지 않으므로 -1을 반환합니다.

C++ 구현 예제

#include<iostream>
#include<stack>
using namespace std;
void getEndingBracketIndex(string exp, int index){
    int i;
    if(exp[index]!='('){
        cout << exp << "Closing bracket of parentheses started at " << index << " present at index -1\n";
        return;
    }
    stack <int> stk;
    for(i = index; i < exp.length(); i++){
        if(exp[i] == '(')
            stk.push(exp[i]);
        else if(exp[i] == ')'){
            stk.pop();
            if(stk.empty()){
                cout << exp << ", Closing bracket of parentheses started at " << index << " present at index " << i << "";
                return;
            }
        }
    }
    cout << exp << ", Closing bracket of parentheses started at " << index << " present at index -1";
}
int main() {
    getEndingBracketIndex("(25*6+(88-32+(50/10)+20))", 6);
}

실행 결과

(25*6+(88-32+(50/10)+20)), Closing bracket of parentheses started at 6 present at index 23

시간 복잡도 분석

이 알고리즘은 최악의 경우 문자열 전체를 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 여기서 n은 표현식의 길이입니다. 공간 복잡도 역시 중첩된 괄호의 깊이에 따라 스택을 사용하므로 최악의 경우 O(n)입니다.