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