[BOJ] 19832 - Configuration file

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

BOJ - 19832 - Configuration file

문제 유형: 문자열 처리, 파싱, 스택, 해시

문제 난이도: Gold IV

시간 제한: 2초

메모리 제한: 512MB

 

문제

Vadim develops a parser for configuration files of his project. A configuration file consists of blocks delimited with braces: "{" marks the beginning of the block, and "}" marks the end of the block. Blocks can be nested. One block can contains several other blocks.

There are variables in the configuration file. Each variable has a name that consists of at most ten lowercase English letters. Each variable has an integer value, initially all variables are set to 0. 

New values can be assigned to variables. Assigning a constant value to a variable is specified as "<variable>=<number>", here <variable> is the variable's name, and <number> is an integer, its absolute value doesn't exceed 10^9. The parser reads the file line after line. As it reads the assignment operation, it assigns the new value to the variable. This value is used until the end of the current block, after that the previous value is restored. If the current block has some nested blocks following the assignment, the new value of the variable is used inside those blocks.

A variable can also be assigned the value of another variable. Such operation is specified as "<variable1>=<variable2>". When the parser reads such line, it assigns the current value of variable2 to variable1. Similarly to the case of a constant value assignment, the new value is used until the end of the current block. After the end of the current block, the value that the variable had at the beginning of the block is restored.

For debugging purpose Vadim wants to print all values that are assigned when processing lines of the form "<variable1>=<variable2>". Help him to debug the parser.

 

Vadim은 설정 파일의 파서를 만들고 있습니다.

설정 파일의 '{'는 블록을 열고, '}'는 블록을 닫습니다.

블록은 중첩될 수 있습니다.

하나의 블록은 여러 블록을 가질 수도 있습니다.

설정 파일에는 변수가 있습니다.

<변수>=<숫자>의 꼴이면 변수에 숫자를 할당합니다.

<변수1>=<변수2>라면 변수1에 변수2를 할당해야 합니다.

블록 안에서의 선언은 블록 안에서만 유효합니다.

변수의 기본 값은 0입니다.

 

입력

Input data contains at least 1 and at most 105 lines. Each line has one of four types:

• { --- beginning of the block;
• } --- end of block;
• <variable>=<number> --- assigning a constant value to a variable;
• <variable1>=<variable2> --- assigning one variable to another, here <variable1> and <variable2> can be the same.

It is guaranteed that the input is correct and corresponds to the statement. Input doesn't contain spaces.

 

별도의 공백없이 줄로만 구분되어주어집니다.

• { - 블록의 시작
• } - 블록의 끝
• <변수>=<값> - 변수에 값을 할당해야 합니다.
• <변수1>=<변수2> - 변수1에 변수2의 값을 할당해야 합니다.

 

출력

For each line that has the form "<variable1>=<variable2>" print the value that is assigned.

<변수1>=<변수2>꼴에 대해서 결과값을 출력하시오.

 

풀이

기본적으로, 파싱하면서 여는 괄호를 만나면, layer를 1 늘리고, 닫는 괄호를 만나면 layer를 1 줄이는식으로 했다.

매번 괄호를 닫을때마다 만료된 것들을 없앤다면, 시간이 부족하다.  lazy하게 처리할 줄 알아야 한다.

 

해시맵 mp를 만들어서, mp[변수명] = {{값, 특별 식별자}...}로 했다.

int형의 특별 식별자의 구조는 다음과 같다:

상위 15비트: 그 layer에서의 몇 번째 괄호쌍인지가 저장되어있다.

하위 17비트: layer의 번호이다. 최대 layer는 약 5만까지 올라올 수 있으므로, 17비트면 여유있다.

 

왜 이렇게까지 해야 하냐면, 

{

 b=5

}

{

 a=b

}

의 꼴이면 마지막에는 a=0이어야 정상이기 때문이다. 즉, 같은 레이어에 있더라도 서로 다르게 식별해주어야 한다.

 

문자열을 한 줄씩 받아서, 여는 괄호면 layer를 1 올리고, 해당 레이어에서 몇 번째로 열린 것인지 트래킹하기 위해, layer_num[layer]를 1 증가시킨다.

닫는 괄호면 layer를 1 내리고 패스한다.

 

그게 아니라면, 수식이다. 중간에 반드시 '='를 포함한다.

'='를 기점으로 전후로 문자열을 나눈다.

왼쪽은 lvalue, 오른쪽을 rvalue로 하겠다.

 

lvalue와 rvalue가 같다면, 그냥 자기 자신을 출력하면 된다.

단, mp의 맨 뒤에 더 높은 레이어가 있을 수 있으므로, 현재 레이어보다 높거나, 현재 레이어와 같은데 현재의 레이어 번호(layer_num)보다 작다면, 이전에 닫힌 괄호라는 의미이다. 즉, 이러한 것들을 모두 pop한다.

이러한 정보들은 상태 정수에서 레이어와 식별자를 추출해서 확인할 수 있다.

만약 mp[lvalue]가 비어있다면, {0, layer | layer_num[layer] << 17} 로, 즉 0과 상태 정수를 추가해주면 된다.

mp[lvalue]의 맨 뒤 요소를 넣어주면 된다.

그러고 마친다.

 

다르다면, 이제 lvalue에 삽입을 해야 한다.

위처럼 복잡하게 제거하지 말고, mp[lvalue]에서 현재 레이어보다 높은 값들을 pop해주기만 하면 된다는 것을 알 수 있다.

 

숫자인 경우, 정수로 변환해주고, {정수 rvalue, layer | layer_num[layer] << 17}을 두에 추가해준다.

 

변수인 경우, mp[rvalue]도 만료된 값을 제거해야 한다. 단, 현재 같은 레이어 높이에서 같은 레이어번호를 가진다면, 남길 필요가 있다.

즉, lvalue == rvalue에서와 같은 방식으로 mp[rvalue]에서의 제거 반영을 해주면 된다.

그러고, mp[rvalue]가 비어있다면, mp[lvalue]에는 값으로 0을 넣어야 한다.

비어있지 않다면, mp[rvalue]의 맨 끝에서의 데이터를 mp[lvalue]로 넣으면 된다.

상태 정수는 역시 layer | layer_num[layer] << 17을 넣으면 된다.

변수인 경우에는 넣은 값을 출력해야 하는것도 잊지말자.

 

 

코드

C++

#include <bits/stdc++.h>
#define pii pair<int, int>

using namespace std;

int get_pure_layer(int id) { return id & 0x1FFFF; }
int get_pure_id(int id) { return id >> 17; }

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    unordered_map<string, vector<pii>> mp;
    unordered_map<int, int> layer_num;
    int layer = 0;
    string exp;

    while (cin >> exp) {
        if (exp == "{") {
            layer++;
            layer_num[layer]++;
            continue;
        } else if (exp == "}") {
            layer--;
            continue;
        }

        int mid = 0;
        while (exp[mid] != '=') {
            mid++;
        }

        string lvalue = exp.substr(0, mid);
        string rvalue = exp.substr(mid + 1);
        if (lvalue == rvalue) {
            while (!mp[lvalue].empty() &&
                   (get_pure_layer(mp[lvalue].back().second) > layer ||
                    get_pure_id(mp[lvalue].back().second) <
                        layer_num[get_pure_layer(mp[rvalue].back().second)])) {
                mp[lvalue].pop_back();
            }

            if (mp[lvalue].empty())
                mp[lvalue].push_back({0, layer | layer_num[layer] << 17});
            cout << mp[lvalue].back().first << "\n";
            continue;
        }

        while (!mp[lvalue].empty() &&
               get_pure_layer(mp[lvalue].back().second) >= layer) {
            mp[lvalue].pop_back();
        }

        if ((rvalue[0] >= '0' && rvalue[0] <= '9') || rvalue[0] == '-') {
            int val = stoi(rvalue);
            mp[lvalue].push_back({val, layer | (layer_num[layer] << 17)});
        } else {
            while (!mp[rvalue].empty() &&
                   (get_pure_layer(mp[rvalue].back().second) > layer ||
                    get_pure_id(mp[rvalue].back().second) <
                        layer_num[get_pure_layer(mp[rvalue].back().second)])) {
                mp[rvalue].pop_back();
            }
            if (mp[rvalue].empty()) {
                mp[lvalue].push_back({0, layer | layer_num[layer] << 17});
            } else {
                mp[lvalue].push_back({mp[rvalue].back().first,
                                      layer | (layer_num[layer] << 17)});
            }
            cout << mp[lvalue].back().first << "\n";
        }
    }

    return 0;
}