백준 : 2504 - 괄호의 값

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

 

 

수많은 삽질끝에 해결했다!

---

두가지 생각을 해야하는데,,,,,

 

1. 올바른 괄호의 판단 : stack을 이용한다

2. value 계산 : 재귀로 해결

 

value계산은! 아주 복잡하진 않고, 조각조각 나눠주면서 해결해주면 된다.

1. 덧셈인 경우 : (())[[]] 라는 문자열 => (())와 [[]]의 value를 각각 더해주면 된다.

    즉 반복문을 돌면서 괄호판단을 할 때, (())이후 [를 검사할 때 한번 stack이 empty상태가 된다 == 이 때 이전부분을 value함수로 넣어주기

                                                        [[]]까지 다 검사한 다음, 마지막에 또 stack이 empty면 나머지 부분인  [[]]를 value함수로 넣어준다

2. 곱셈인 경우 : (()[]) 라는 문자열 => ()[]의 value에 2를 곱해준다

    반복문을 돌 때, 중간에 empty가 안나오고 마지막에 한번만 empty가 나오는경우가 이런경우이다!

                           str[0]이 '(' 이면 2 * value ()[] 를 해주면 된다

3. 문자열의 길이가 2인경우 : () 또는 []가 들어온 상황이라고 생각할 수 있다!

                     각각 2 또는 3을 그대로 반환해준다

4. 올바르지 않은 괄호인경우 : 0을 반환해준다!

             재귀상황에서, 0이 반환되면 그대로 0을 계속 보내준다.

 

옛날에 컴파일러 과목 들을 때 신텍스 트리였나? 약간 이런느낌으로 만들었던것같다.

거기서는 문법 검사 -> 트리만들기 순서로 진행했으니까

나도 차라리 올바른 괄호검사 -> value계산 두가지 step으로 나눴으면 좀 더 알아보기 쉬운 코드가 되지 않았을까 싶다.

괜히 검사하면서 계산한다고 삽질을....

 

#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <numeric>

using namespace std;

int value(string str){

    // () || [] 일 때
    if((int)str.size() == 2){
        if(str[0] == '(' && str[1] == ')'){
            return 2;
        }else if(str[0] == '[' && str[1] == ']'){
            return 3;
        }else{
            return 0;
        }
    }else if((int)str.size() < 2){
        return 0;
    }

    stack<char> mystack;

    vector<int> answers;
    mystack.push(str[0]);
    int start = 0;
    
    for(int i = 1; i<str.size(); i++){
        if(mystack.empty()){
            int this_value = value(str.substr(start, (i - start)));
            if(this_value == 0){
                return 0;
            }
            answers.push_back(this_value);
            start = i;
        }
        
        switch(str[i]){
            case '(':
                mystack.push(str[i]);
                break;
            case '[':
                mystack.push(str[i]);
                break;
            case ')':
                if(!mystack.empty() && mystack.top() == '('){
                    // 정상적으로 짝지어짐
                    mystack.pop();
                }else{
                    // 이상한 문자열인것!
                    return 0;
                }
                break;
            case ']':
                if(!mystack.empty() && mystack.top() == '['){
                    // 정상적으로 짝지어짐
                    mystack.pop();
                }else{
                    // 이상한 문자열인것!
                    return 0;
                }
                break;
        }
    }

    if(!mystack.empty()){
        return 0;
    }

    // str이 ( ~~~~ ) || [ ~~~~~] 모양일 때! => 겉에걸 빼고, 안쪽만 다시 넣어보기
    if(answers.empty()){
        if(!mystack.empty()){
            return 0;
        }
        if(str[0] == '('){
            int answer = 2 * value(str.substr(1, (int)str.size()-2));
            return answer;
        }else if(str[0] == '['){
            int answer = 3 * value(str.substr(1, (int)str.size()-2));
            return answer;
        }
    }else{
        if(mystack.empty()){
            int this_value = value(str.substr(start, (str.size() - start)));
            if(this_value == 0){
                return 0;
            }
            answers.push_back(this_value);
        }
    }

    int answer = accumulate(answers.begin(), answers.end(), 0);
    return answer;
}

int main(){

    string str;
    cin >> str;

    cout << value(str);

    return 0;
}