논리식은 컴퓨터 과학의 중요한 개념으로, 참(1)과 거짓(0) 값을 가지며 논리 연산자로 연결됩니다. 여기서는 AND(&)와 OR(|) 연산자만 고려하며, 연산자 우선순위는 AND가 OR보다 높고, 동일 연산자일 경우 왼쪽에서 오른쪽으로 계산합니다. 괄호 안의 식이 먼저 계산됩니다.

또한, C++ 등 일부 컴파일러는 "단락(short-circuit)" 평가를 사용합니다. a & b에서 a가 0이면 전체 결과는 0이므로 b를 계산하지 않고, a | b에서 a가 1이면 전체 결과는 1이므로 b를 계산하지 않습니다. 단, 외부에서 이미 단락이 발생하여 내부가 평가되지 않으면, 내부의 단락은 횟수에 포함하지 않습니다.

예를 들어 1|(0&1)에서는 1|...에서 이미 단락이 발생했으므로 0&1의 단락은 카운트하지 않습니다.

입력으로 논리식 문자열이 주어질 때, 식의 최종 값과 AND 단락, OR 단락 발생 횟수를 출력합니다.

입력 예시

0&(1|0)|(1|1|1&0)

출력 예시

1
1 2

괄호 처리를 위해 재귀를 사용합니다. 각 괄호 레벨의 깊이를 추적하고, 현재 레벨에서 가장 가까운 AND/OR 연산자 위치를 기록하여 계산 구간을 분할합니다.

구현 방법

1. 문자열을 전처리하여 각 위치별로 현재 괄호 깊이에서 가장 가까운 AND, OR 연산자 인덱스를 저장합니다.
2. 재귀 함수에서 현재 구간의 시작과 끝을 인자로 받습니다.
3. 구간 내에서 우선순위에 따라 OR 연산자 먼저 찾고, 없으면 AND 연산자를 찾습니다.
   • OR 연산자가 있고 그 인덱스가 구간 시작보다 크면, 왼쪽 부분(구간 시작 ~ 연산자 직전)을 먼저 계산합니다. 결과가 1이면 단락 발생(OR 단락 카운트)하고 즉시 1 반환. 아니면 오른쪽 부분 계산 후 OR 연산.
   • AND 연산자에 대해서도 동일하게 처리하며, 왼쪽 결과가 0이면 AND 단락 카운트 후 0 반환.
4. 연산자를 찾지 못했고 구간이 괄호로 둘러싸여 있으면, 괄호를 제거하고 재귀 호출.
5. 구간 길이가 1이면 해당 문자를 숫자로 변환하여 반환.

핵심 코드

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

const int MAX = 1e6 + 10;
string expr;
int n, orPos[MAX], andPos[MAX], nearOr[MAX], nearAnd[MAX];
int cntAndShort = 0, cntOrShort = 0;

int evaluate(int left, int right) {
    if (left == right) return expr[left] - '0';

    int opOr = nearOr[right];
    int opAnd = nearAnd[right];

    // OR 연산자 우선 처리
    if (opOr > 0 && opOr > left) {
        int leftVal = evaluate(left, opOr - 1);
        if (leftVal == 1) {
            cntOrShort++;
            return 1;
        }
        int rightVal = evaluate(opOr + 1, right);
        return leftVal | rightVal;
    }

    // AND 연산자 처리
    if (opAnd > 0 && opAnd > left) {
        int leftVal = evaluate(left, opAnd - 1);
        if (leftVal == 0) {
            cntAndShort++;
            return 0;
        }
        int rightVal = evaluate(opAnd + 1, right);
        return leftVal & rightVal;
    }

    // 괄호 제거
    if (expr[left] == '(' && expr[right] == ')')
        return evaluate(left + 1, right - 1);

    return -1; // 도달 불가
}

void preprocess() {
    int depth = 0;
    for (int i = 1; i <= n; i++) {
        char c = expr[i];
        if (c == '(') depth++;
        else if (c == ')') depth--;
        else if (c == '|') orPos[depth] = i;
        else if (c == '&') andPos[depth] = i;

        nearAnd[i] = andPos[depth];
        nearOr[i] = orPos[depth];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> expr;
    expr = ' ' + expr;
    n = expr.length() - 1;
    preprocess();
    int result = evaluate(1, n);
    cout << result << "\n";
    cout << cntAndShort << " " << cntOrShort << "\n";
    return 0;
}