[Baekjoon] 4466_A Smart Brain is a Tasty Brain

문제(출처: https://www.acmicpc.net/problem/4466)

---

< A Smart Brain is a Tasty Brain >

 

문제 풀이 

 

Stack을 사용하여 닫는 괄호가 나올 때마다 괄호 안의 표현식을 계산한다.

 

* ! 연산 순서를 조심한다.

 

my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class _4466_ { // A Smart Brain is a Tasty Brain

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int x = Integer.parseInt(bf.readLine());

		Stack<Character> stack = new Stack<>();
		for (int i = 0; i < x; i++) {
			st = new StringTokenizer(bf.readLine());

			String str = st.nextToken();
			st.nextToken();
			char evaluation = st.nextToken().charAt(0);

			for (int j = 0; j < str.length(); j++) {
				if (str.charAt(j) != ')') {
					stack.add(str.charAt(j));
				} else {
					calc(stack);
				}
			}
			while (stack.size() > 1) {
				calc(stack);
			}

			if (stack.pop() == evaluation) {
				bw.write((i + 1) + ": Good brain\n");
			} else {
				bw.write((i + 1) + ": Bad brain\n");
			}
		}
		bw.flush();
	}

	private static void calc(Stack<Character> stack) {
		char a = stack.pop();
		while (!stack.isEmpty() && stack.peek() != '(') {
			if (stack.peek() == '!') {
				stack.pop();
				a = (a == 't') ? 'f' : 't';
			} else {
				char op = stack.pop();
				char b = stack.pop();
				while (stack.peek() == '!') {
					stack.pop();
					b = (b == 't') ? 'f' : 't';
				}

				if (op == '&') {
					a = (a == 't' && b == 't') ? 't' : 'f';
				} else {
					a = (a == 't' || b == 't') ? 't' : 'f';
				}
			}
		}
		if (!stack.isEmpty() && stack.peek() == '(') {
			stack.pop();
		}
		if (!stack.isEmpty() && stack.peek() == '!') {
			stack.pop();
			a = (a == 't') ? 'f' : 't';
		}
		stack.add(a);
	}
}

변수)
x : 표현식 개수
stack : Stack <Character>
str : 표현식
evaluation : 표현식 답

 

Main

표현식 개수를 입력받는다. 표현식 개수만큼 표현식을 입력받아 다음 과정을 반복한다.

 

1) 표현식과 표현식 답을 각각 str과 evaluation 변수에 저장

2) 표현식을 순차 탐색하며 닫는 괄호가 아닌 경우 stack에 저장, 닫는 괄호인 경우 calc 함수를 호출

3) stack의 크기가 1보다 크다면 아직 계산이 남아있다는 뜻이므로 다시 calc 함수를 호출

4) stack에서 pop 한 값이 표현식 답과 일치하다면 "Good brain"을, 일치하지 않다면 "Bad brain"을 출력

 

Calc

stack에서 값을 제거하여 변수 a에 저장한다. stack이 비어있지 않고, stack의 값이 열린 괄호가 아닐 때까지 다음 과정을 반복한다.

 

1) stack의 값이 !라면 NOT 연산

2) stack의 값이 !가 아니라면 stack에서 값을 2개 pop 하여 각각 op와 b 변수에 저장 후 각 연산자에 맞게 연산 (이때, b 앞에도 NOT 연산이 있을 수 있으므로 확인한다.)

 

stack이 비어있지 않고, stack의 값이 열린 괄호라면 열린 괄호를 제거한다. 괄호 계산 후 앞에 NOT 연산이 있는지 확인한다. 연산 결과를 stack에 저장한다.

---

---