백준 [N2504 - 괄호의값]

 

풀이과정

스택응용문제이다. 스택을 사용해 올바른 괄호열인지 확인하는 것은 알았지만, 괄호값을 계산하는 것을 어떻게 구현할지 풀지 못했다. 이는 분배법칙을 생각하면 풀 수 있던 문제였다.

 

입출력 예제로보면,

(()[[]])는 다음과 같이 계산된다. 2*(2+3*3). 이를 분배법칙으로 풀어보면 2*2+2*3*3이 된다.

(연산을 위한 val변수, 연산결과를 나타내는 result변수 선언 후)

열린 괄호가 나오면 무조건 val * (2 or 3) 괄호종류에 따라 곱해주도록 한다.

닫힌 괄호가 나오면,

(올바르지 않은 괄호열인 경우)
스택이 비어있거나 peek()값이 괄호의 짝이 아닌 경우 올바른 괄호열이 아니기에 result = 0으로 하고 넘어간다.

(올바른 괄호열인 경우)
바로 직전 인덱스에 그 괄호의 짝이 있다면, result이 이제까지 연산해온 val값을 더해준다.
stack에서 pop해주고, 무조건 곱해온 val/(2 or 3) 괄호종류에 따라 나눠준다.

 

(	(	)	[	[	]	]	)	계산
val *= 2								val =2
	val *= 2							val =4
		val /=2						result = 4 val =2	2*2
			val *= 3					val = 6
				val *=3				val = 18
					val /=3			result = 22 val = 6	2*2+ 2*3*3
						val /= 3		val = 2
							val /=2	val = 1

 

소스코드

public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int val = 1;
        int result = 0;
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<str.length();i++){
            char x = str.charAt(i);

            if(x=='(' || x=='['){
                stack.push(x);
                val*= (x=='(')?2:3;
            }else if(x==')'){
                if(stack.isEmpty() || stack.peek()!='(') {//올바르지 않은 괄호열
                    result =0;
                    break;
                }
                //올바른 괄호열
                if(i-1>0 && str.charAt(i-1)=='(') result+=val;//바로직전에 괄호짝이 있는 경우
                stack.pop();
                val/=2;
            }else{
                if(stack.isEmpty() || stack.peek()!='[') {//올바르지 않은 괄호열
                    result =0;
                    break;
                }
                //올바른 괄호열
                if(i-1>0 && str.charAt(i-1)=='[') result+=val;//바로직전에 괄호짝이 있는 경우
                stack.pop();
                val/=3;
            }
        }
        if(!stack.isEmpty()) result = 0;
        System.out.println(result);
    }