티스토리 뷰

[DataStructure] BracketComplete?


자료구조 활용을 묻는 문제이다. 아주 기본중의 기본.

https://www.acmicpc.net/problem/9012

// 완벽하게 닫힌 괄호인지 검사하기
// < [ { ( 4가지 종류의 괄호로 주어진 스트링이 제공된다.
// 괄호를 살펴보면서 짝이 맞게 닫혔는지 검사한다.
// Stack, String, Map

#include <iostream>
#include <stack>
#include <map>
using namespace std;

int main() {
stack<char> stack;
map<char, char> map;
map['>'] = '<';
map[']'] = '[';
map['}'] = '{';
map[')'] = '(';

string bracket;
cin >> bracket;

bool result = true;
for(int i=0; i<bracket.length(); i++) {
char b = bracket.at(i);

switch(b) {
case '<':
case '[':
case '{':
case '(':
stack.push(b);
break;
default:
if(!stack.size()) result = false;
else if(stack.top() == map.find(b)->second) stack.pop();
break;
}
}

if(stack.size() > 0) result = false;
cout << result << endl;

return 0;
}



스택을 두개 사용해서 푸는 괄호문제

https://www.acmicpc.net/problem/2504

// 완벽하게 닫힌 괄호인지 검사하기 - 가중치 두기
// Stack 2개 사용 - 괄호 검사 / 가중치

// 괄호가 완벽하게 닫힌 것들 끼리만 더하고
// 불안전하게 닫힌 것들은 곱해져야 한다

// 괄호의 시작점에 0 플래그를 주고
// 닫을 때 0 플래그까지 숫자를 뽑으면서 괄호 안에 숫자들을 더한다.
// 0 플래그를 만나면 현재 괄호 가중치와 더한 숫자를 곱한 후 스택에 다시 넣는다

// 완전한 괄호인 경우, 스택에 있는 숫자를 모두 더하면 결과값이다.

#include <iostream>
#include <stack>
#include <map>
using namespace std;

int main() {
stack<char> bracketStack;
stack<int> score;

map<char, char> bracketMap;
bracketMap[']'] = '[';
bracketMap[')'] = '(';
map<char, int> scoreMap;
scoreMap[']'] = 3;
scoreMap[')'] = 2;

string bracket;
cin >> bracket;

bool result = true;
int s = 1;
for(int i=0; i<bracket.length(); i++) {
char b = bracket.at(i);

switch(b) {
case '[':
case '(':
bracketStack.push(b);
score.push(0);
break;
default:
if(!bracketStack.size()) result = false;
else if(bracketStack.top() == bracketMap.find(b)->second) {
bracketStack.pop();

int s = 0;
while(score.top() != 0) {
s += score.top();
score.pop();
}

if(!s) s = 1;
score.pop();
score.push(s*scoreMap.find(b)->second);
}
break;
}
}

int totalScore = 0;
while(score.size()) {
totalScore += score.top();
score.pop();
}
if(bracketStack.size() > 0) result = false;
cout << result * totalScore << endl;

return 0;
}


댓글
댓글쓰기 폼