[ALGOSPOT] 짝이 맞지 않는 괄호
https://www.algospot.com/judge/problem/read/BRACKETS2
이 문제는 알고리즘 문제 해결 전략 2권의 19챕터에서 나오는 문제이다!
이 문제를 풀다보니
지난 학기 자료구조 시간에 스택 챕터에서 배웠던 계산기 문제가 떠올랐다
중위표기법에서 후위표기법으로 수식을 변환할 때 스택이 사용되었었다
중위표기법 : ( 1 + 2 * 3) / 4
후위표기법 : 1 2 3 * + 4 /
- 여는 괄호를 만나면 스택에 넣는다
- 피연산자를 만나면 수식 배열로 옮긴다
- 연산자를 만나면 스택에 넣는다
- 닫는 괄호를 만나면 스택에서 여는 괄호 위에 있는 연산자를 모두 꺼내어 수식 배열로 옮긴다
위와 같은 알고리즘으로 동작했는데,
이 문제에서도 비슷했다고 생각이 된다
스케치
계획을 세울 땐 배열에서 원소를 가리키는 포인터가 필요하다고 생각했는데,
그냥 반복문에서 바로바로 스택에 넣고 비교하고 하면 되는 거라 필요없었다
알고리즘을 정리해보면 다음과 같다
1. 여는 괄호를 만나면 스택에 넣는다
2. 닫는 괄호를 만나면 스택의 Top에 있는 여는 괄호와 비교한다
- 짝이 맞으면 스택에 있는 여는 괄호를 Pop
- 짝이 맞지 않으면 검사를 종료
또한 아래와 같은 예외처리가 필요했다
1. 여는 괄호만 있을 경우
- 배열의 끝까지 검사를 마쳤는데 스택에 연산자가 남아있는 경우가 된다
- pop 연산이 이루어지지 못했으므로 짝이 맞지 않아 NO를 반환한다
2. 닫는 괄호만 있을 경우
- 이번 검사 대상이 닫는 괄호이고, 스택이 비어있을 경우가 된다
- 여는 괄호보다 닫는 괄호가 먼저 나왔다는 의미가 되므로 NO를 반환한다
CODE
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
#define SIZE 3
bool IsOpenBracket(vector<char> & open, char target);
bool IsMatch(char open, char close);
bool SearchBracketCouple(string input, vector<char> open_bracket);
int main(void)
{
vector<char> open_bracket = {'(', '{', '['};
vector<string> inputs;
int testcase = 0;
cin>>testcase;
for(int i=0; i<testcase; i++)
{
string temp;
cin>>temp;
inputs.push_back(temp);
}
for(int i=0; i<testcase; i++)
{
if(inputs[i].size() % 2 != 0)
{
cout<<"NO"<<endl;
continue;
}
if(SearchBracketCouple(inputs[i], open_bracket))
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
return 0;
}
bool SearchBracketCouple(string input, vector<char> open_bracket)
{
stack<char> open;
// 1. string을 순회한다
// 2. 여는 괄호이면 push
// 3. 닫는 괄호이면 stack의 top과 비교
// - 맞으면 여는 괄호 pop
// - 틀리면 탐색 종료
for(int i=0; i<input.size(); i++)
{
// cout<<input_1[i]<<endl;
if(IsOpenBracket(open_bracket, input[i]))
{
open.push(input[i]);
}
else
{
if(!open.empty())
{
if(IsMatch(open.top(), input[i]))
{
open.pop();
}
else
{
return false;
}
}
else
return false;
}
}
if(open.empty()) // 여는 괄호만 있어서 stack이 비워지지 못하면 false
return true;
else
return false;
}
bool IsOpenBracket(vector<char> & open, char target)
{
for(int i=0; i<open.size(); i++)
{
if(target == open[i])
{
return true;
}
}
return false;
}
bool IsMatch(char open, char close)
{
if(open == '{' && close == '}' )
return true;
else if(open == '[' && close == ']')
return true;
else if(open == '(' && close == ')')
return true;
else
return false;
}
Author And Source
이 문제에 관하여([ALGOSPOT] 짝이 맞지 않는 괄호), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@minjujuu/ALGOSPOT-짝이-맞지-않는-괄호저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)