[Algorithm] 백준 4466 - A Smart Brain is a Tasty Brain (Node / C#)

문제

https://www.acmicpc.net/problem/4466

 

풀이

1. Node.js(fs)

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const numCases = parseInt(input[0]);

function evaluateExpression(expr) {
    const stack = [];
    for (let i = 0; i < expr.length; i++) {
        if (expr[i] === ')') {
            let subExpr = [];
            while (stack[stack.length - 1] !== '(') {
                subExpr.unshift(stack.pop());
            }
            stack.pop(); // Remove '('
            stack.push(evaluateSubExpression(subExpr));
        } else {
            stack.push(expr[i]);
        }
    }
    return evaluateSubExpression(stack);
}

function evaluateSubExpression(expr) {
    const result = [];
    let i = 0;
    while (i < expr.length) {
        if (expr[i] === '!') {
            result.push(expr[i + 1] === 't' ? 'f' : 't');
            i += 2;
        } else if (expr[i] === '&') {
            const left = result.pop();
            const right = expr[i + 1];
            result.push(left === 't' && right === 't' ? 't' : 'f');
            i += 2;
        } else if (expr[i] === '|') {
            const left = result.pop();
            const right = expr[i + 1];
            result.push(left === 'f' && right === 'f' ? 'f' : 't');
            i += 2;
        } else {
            result.push(expr[i]);
            i++;
        }
    }
    return result[0];
}

let output = '';
for (let i = 1; i <= numCases; i++) {
    const [expr, expected] = input[i].split(' = ');
    const evaluation = evaluateExpression(expr);
    output += `${i}: ${evaluation === expected ? 'Good brain' : 'Bad brain'}\n`;
}
console.log(output.trim());

 

2. Node.js(readLine)

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let numCases;
let currentCase = 0;
let output = '';

function evaluateExpression(expr) {
    const stack = [];
    for (let i = 0; i < expr.length; i++) {
        if (expr[i] === ')') {
            let subExpr = [];
            while (stack[stack.length - 1] !== '(') {
                subExpr.unshift(stack.pop());
            }
            stack.pop(); // Remove '('
            stack.push(evaluateSubExpression(subExpr));
        } else {
            stack.push(expr[i]);
        }
    }
    return evaluateSubExpression(stack);
}

function evaluateSubExpression(expr) {
    const result = [];
    let i = 0;
    while (i < expr.length) {
        if (expr[i] === '!') {
            result.push(expr[i + 1] === 't' ? 'f' : 't');
            i += 2;
        } else if (expr[i] === '&') {
            const left = result.pop();
            const right = expr[i + 1];
            result.push(left === 't' && right === 't' ? 't' : 'f');
            i += 2;
        } else if (expr[i] === '|') {
            const left = result.pop();
            const right = expr[i + 1];
            result.push(left === 'f' && right === 'f' ? 'f' : 't');
            i += 2;
        } else {
            result.push(expr[i]);
            i++;
        }
    }
    return result[0];
}

rl.on('line', (line) => {
    if (!numCases) {
        numCases = parseInt(line);
    } else {
        currentCase++;
        const [expr, expected] = line.split(' = ');
        const evaluation = evaluateExpression(expr);
        output += `${currentCase}: ${evaluation === expected ? 'Good brain' : 'Bad brain'}\n`;
        
        if (currentCase === numCases) {
            console.log(output.trim());
            rl.close();
        }
    }
});

3. C#

using System;
using System.Text;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int numCases = int.Parse(Console.ReadLine());
        StringBuilder output = new StringBuilder();

        for (int i = 1; i <= numCases; i++)
        {
            string[] input = Console.ReadLine().Split(" = ");
            string expr = input[0];
            string expected = input[1];
            string evaluation = EvaluateExpression(expr);
            output.AppendLine($"{i}: {(evaluation == expected ? "Good brain" : "Bad brain")}");
        }

        Console.Write(output.ToString());
    }

    static string EvaluateExpression(string expr)
    {
        var stack = new List<char>();
        for (int i = 0; i < expr.Length; i++)
        {
            if (expr[i] == ')')
            {
                var subExpr = new List<char>();
                while (stack[stack.Count - 1] != '(')
                {
                    subExpr.Insert(0, stack[stack.Count - 1]);
                    stack.RemoveAt(stack.Count - 1);
                }
                stack.RemoveAt(stack.Count - 1); // Remove '('
                stack.Add(EvaluateSubExpression(subExpr));
            }
            else
            {
                stack.Add(expr[i]);
            }
        }
        return EvaluateSubExpression(stack).ToString();
    }

    static char EvaluateSubExpression(List<char> expr)
    {
        var result = new List<char>();
        int i = 0;
        while (i < expr.Count)
        {
            if (expr[i] == '!')
            {
                result.Add(expr[i + 1] == 't' ? 'f' : 't');
                i += 2;
            }
            else if (expr[i] == '&')
            {
                char left = result[result.Count - 1];
                result.RemoveAt(result.Count - 1);
                char right = expr[i + 1];
                result.Add(left == 't' && right == 't' ? 't' : 'f');
                i += 2;
            }
            else if (expr[i] == '|')
            {
                char left = result[result.Count - 1];
                result.RemoveAt(result.Count - 1);
                char right = expr[i + 1];
                result.Add(left == 'f' && right == 'f' ? 'f' : 't');
                i += 2;
            }
            else
            {
                result.Add(expr[i]);
                i++;
            }
        }
        return result[0];
    }
}

 

 

설명

1. 입력 처리:
   • 첫 번째 줄에서 테스트 케이스의 수를 읽습니다.
   • 그 다음 각 줄마다 Boolean 표현식과 예상 결과를 읽습니다.
2. 데이터 구조:
   • 스택을 사용하여 괄호 내부의 표현식을 처리합니다.
   • 배열을 사용하여 부분 표현식을 평가합니다.
3. 알고리즘:
   • evaluateExpression 함수:
     1. 문자열을 순회하며 각 문자를 스택에 push합니다.
     2. 닫는 괄호 ')'를 만나면, 여는 괄호 '('까지 스택에서 pop하여 부분 표현식을 만듭니다.
     3. 부분 표현식을 평가하고 결과를 다시 스택에 push합니다.
   • evaluateSubExpression 함수:
     1. 배열을 한 번 순회하며 NOT, AND, OR 연산을 모두 처리합니다.
     2. NOT('!') 연산은 다음 문자를 반전시킵니다.
     3. AND('&')와 OR('|') 연산은 이전 결과와 다음 문자를 비교하여 결과를 도출합니다.
4. 결과 출력:
   • 각 테스트 케이스마다 평가 결과를 저장합니다.
   • 모든 테스트 케이스를 처리한 후 결과를 한 번에 출력합니다.