[DataStructure] bracketComplete? - Stack, Map, String

[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;
}