[C/C++] 코드업(codeup) 4624번 괄호의 값

▽문제 바로가기

https://codeup.kr/problem.php?id=4624

괄호의 값

---

입력

첫 째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

 

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다. 

 

문제 풀이

 

올바른 괄호 인지도 판단해야 하고 값도 구해야 하는 문제입니다.

괄호가 올바른지에 대한 여부는 기존에 '올바른 괄호 2'와 비슷합니다. 열린 괄호는 push, 닫힌괄호는 pop 하여 top값이 최솟값보다 작다면 잘못된 괄호입니다. 또한 스택에 남아있는 값이 있다면 역시 잘못된 괄호입니다.

---

https://swblossom.tistory.com/74

[C/C++] 코드업(codeup) 3129번 올바른 괄호 2

---

하지만 추가적으로 고려해야할 것이 있습니다. 괄호가 소괄호뿐만 아니라 대괄호가 생겼습니다. 예를 들어 ( ]와 같은 경우는 잘못된 괄호입니다. 

 

이제 계산하는 부분이 남았습니다.

처음에는 ( ( ) [ [ ] ] ) 와 같은 입력이 있다면 2*(2+3*3) = 2*11과 같이 계산하도록 구현하고자 하였으나 실패하였습니다.

따라서 2*(2+3*3) = 2*2 + 2*3*3 과 같이 괄호를 전개하는 방식으로 풀었습니다.

 

방법은 다음과 같습니다.

 

1. 계산용 변수를 하나 선언하고 1로 초기화합니다.

2. 열린괄호면 괄호의 종류에 따라 계산용 변수에 2나 3을 곱해줍니다.

3. 닫힌괄호면 바로 이전의 입력이 같은 종류의 열린 괄호이면 계산 스택에 계산용 변수 값을 push 하고 괄호의 종류에 따라 계산용 변수를 2나 3으로 나눠줍니다.

 

위의 ( ( ) [ [ ] ] ) 와 같은 입력이라면 스택에 ( 4 18 ) 이 입력되어 괄호를 전개하여 푸는 과정과 동일함을 알 수 있습니다.

 

#include <iostream>
#include <stack>

using namespace std;

int main(){
	
	char arr[31];	//입력받을 문자열
	stack <int> s;	//계산할 스택
	bool isGood = true;
	int small = 0, big = 0;	//작은괄호 갯수, 큰 괄호 갯수
	
	gets(arr);	//입력받음
	
	int top = -1;	//실제로 스택쌓지 않고 올바른 괄호인지 계산용
	int cal = 1;	//괄호에 따라 누적 계산할 값
	for(int i=0;;i++){
		if(arr[i]!='('&&arr[i]!=')'&&arr[i]!='['&&arr[i]!=']') break;
		
		//열린소괄호이면 *2
		if(arr[i]=='('){
			top++;
			small++;
			cal *= 2;
		}
		
		//열린대괄호이면 *3 
		if(arr[i]=='['){
			top++;
			big++;
			cal *= 3;
		}
		
		//닫힌소괄호이면
		if(arr[i]==')'){
			//열린소괄호가 없으면 올바른 괄호가 아님 
			if(small<=0){
				isGood = false;
				break;
			}
			//바로전값이 열린소괄호면 스택에 push 
			if(arr[i-1]=='(') s.push(cal);
			top--;
			small--;
			cal /= 2;
		}
		
		//닫힌대괄호이면
		if(arr[i]==']'){
			//열린대괄호가 없으면 올바른 괄호가 아님 
			if(big<=0){
				isGood = false;
				break;
			}
			//바로전값이 열린대괄호면 스택에 push 
			if(arr[i-1]=='[') s.push(cal);
			top--;
			big--;
			cal /= 3;
		}
		
		if(top==-2){
			isGood = false;
			break;
		}
		
	}
	
	int sum = 0;
	for(int i=0;!s.empty();i++){
		sum += s.top();
		s.pop();
	}
	
	if(!isGood||top!=-1) printf("0");
	else printf("%d", sum);
	
	
}