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

C++에서 괄호 없는 산술 표현식의 모든 가능한 결과 구하기

문제 소개

괄호가 포함되지 않은 산술 표현식이 하나 주어져 있을 때, 연산 순서를 임의로 바꿔 해석했을 때 나올 수 있는 모든 가능한 결과값을 구하는 것이 이번 글의 목표입니다. 즉, 보이지 않는 괄호를 여러 위치에 넣어보면서 만들어지는 모든 값을 찾는 문제라고 이해하면 됩니다.

예를 들어 표현식이 1+2*3-4라면, 괄호의 위치에 따라 아래와 같이 다양하게 해석될 수 있습니다.

  • 1+(2*(3-4)) = 1 + (2 × -1) = -1
  • (1+2)*(3-4) = 3 × -1 = -3
  • 1+((2*3)-4) = 1 + (6 - 4) = 3
  • ((1+2)*3)-4 = (3 × 3) - 4 = 5
  • 1+(2*3)-4 = 1 + 6 - 4 = 3

같은 식이라도 어떻게 묶느냐에 따라 전혀 다른 값이 나오며, 서로 다른 해석이 같은 값으로 수렴하는 경우(위 예시의 3)도 있습니다.

해결 접근 방식

이 문제는 분할 정복(divide and conquer) 기법과 재귀 호출로 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 "각 연산자를 차례대로 마지막에 수행되는 연산자로 가정하고, 그 양옆 부분 표현식의 모든 가능한 값을 재귀적으로 구한 뒤 조합하는 것"입니다.

  1. 결과를 담을 리스트 res를 빈 상태로 초기화합니다.
  2. 범위 안의 모든 연산자 x에 대해 다음을 수행합니다.
    • x 기준 왼쪽 부분 표현식에서 나올 수 있는 모든 값을 재귀적으로 구해 목록 L에 저장합니다.
    • 마찬가지로 오른쪽 부분 표현식의 모든 가능한 값을 재귀적으로 구해 목록 R에 저장합니다.
    • L의 모든 원소와 R의 모든 원소를 이중 루프로 짝지어, 현재 연산자 x를 적용한 결과를 res에 추가합니다.
  3. 모든 연산자에 대한 처리가 끝나면 res를 반환합니다.

C++ 구현 예제

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

// 연산자에 따라 실제 계산을 수행하는 함수
int solve(int a, char op, int b) {
    if (op == '+')
        return a + b;
    if (op == '-')
        return a - b;
    if (op == '*')
        return a * b;
}

// expr[low..high] 범위에서 나올 수 있는 모든 결과를 반환
vector<int> getAllResults(string expr, int low, int high) {
    vector<int> res;

    // 범위에 숫자 하나만 남은 경우
    if (low == high) {
        res.push_back(expr[low] - '0');
        return res;
    }

    // "숫자 연산자 숫자" 형태(길이 3)만 남은 경우
    if (low == (high - 2)) {
        int num = solve(expr[low] - '0', expr[low + 1], expr[low + 2] - '0');
        res.push_back(num);
        return res;
    }

    // 연산자 위치(홀수 인덱스)마다 분할 지점을 잡아 재귀 처리
    for (int i = low + 1; i <= high; i += 2) {
        vector<int> L = getAllResults(expr, low, i - 1);   // 왼쪽 부분의 모든 값
        vector<int> R = getAllResults(expr, i + 1, high);  // 오른쪽 부분의 모든 값

        // 왼쪽 값과 오른쪽 값의 모든 조합에 연산자 적용
        for (int s1 = 0; s1 < L.size(); s1++) {
            for (int s2 = 0; s2 < R.size(); s2++) {
                int val = solve(L[s1], expr[i], R[s2]);
                res.push_back(val);
            }
        }
    }
    return res;
}

int main() {
    string expr = "1+2*3-4";
    vector<int> ans = getAllResults(expr, 0, expr.length() - 1);

    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << endl;

    return 0;
}

실행 결과

-1
3
-3
3
5

출력 결과는 앞서 손으로 계산한 해석 목록의 값들(-1, -3, 3, 5, 3)과 정확히 일치합니다. 서로 다른 괄호 배치가 같은 값으로 이어지는 경우(예: 3)에는 중복된 값이 그대로 출력되며, 필요하다면 set이나 unordered_set을 사용해 중복을 제거할 수 있습니다.

복잡도와 참고 사항

연산자가 n개인 표현식에서 가능한 괄호 배치의 수는 카탈란 수(Catalan number)로 결정되므로, 이 알고리즘의 시간 복잡도는 지수적으로 증가합니다. 입력이 길어질 경우 메모이제이션(memoization)으로 동일한 부분 표현식의 결과를 캐싱하면 성능을 크게 향상시킬 수 있습니다. 또한 위 코드는 한 자리 숫자 피연산자만 다루므로, 두 자리 이상의 숫자를 지원하려면 토큰화(tokenizing) 단계를 추가로 구현해야 합니다.