[2257번] 화학식량 (스택 풀이)

지난 번, 재귀함수 풀이에 이어서 스택 풀이입니다.

 

문제 접근법.

1. 괄호에 대해서 먼저 연산을 할 필요가 있다.

2. 숫자가 있는 경우, 앞에 있는 문자나 괄호식에 대해서 곱셈을 해줘야 한다.

 

괄호와 같은 우선 순위가 필요한 연산일 경우, 적합한 자료구조는 스택입니다. 스택을 이용해서, 특정 우선 순위에 대해서 먼저 처리해주는 것이 필요합니다.

 

H, C, O에 대해서는 해당하는 숫자(1, 14, 16)를 넣어줍니다.

(은 우선순위 연산을 위해서 사용되므로, 그대로 넣어줍니다.

)의 경우에는 (를 만날 때까지 만나는 숫자들을 모두 더하도록 처리합니다.

숫자의 경우에는 스택의 Top에 대해서 곱셈을 처리해서, *다시 숫자를 넣어줍니다.

 

* )의 경우에 모든 숫자를 더할 수 있는 이유는, 스택에 들어가는 숫자들은 모두 곱셈이 된 상태로 들어가기 때문입니다.

 

이 과정이 끝나고 나면, 스택에는 있는 모든 숫자를 더해주면 정답이 나오게 됩니다.

 

이 과정이 정확하게 이해가 안되면, 스택의 기본 문제들을 풀면서 이해도를 높이는 것을 추천합니다.

 

해설코드(C++)

#include <iostream>
#include <string>
#include <cstdlib>
#include <stack>
 
using namespace std;
 
stack<string> tack;
string str;
int answer = 0;
 
int main(void) {
    freopen("input.txt", "r", stdin);
    cin >> str;
    int idx = 0;
    while (idx != str.length()) {
        string c(1, str.at(idx));
 
        if (c == "H" || c == "C" || c == "O" || c == "(")
            tack.push(c);
        else if (c == ")") {
            int tmp = 0;
            while (tack.top() != "(") {
                if (tack.top() == "C") tmp += 12;
                else if (tack.top() == "H") tmp += 1;
                else if (tack.top() == "O") tmp += 16;
                else tmp += stoi(tack.top());
                tack.pop();
            }
            tack.pop();
            tack.push(to_string(tmp));
        }
        else if(c >= "1" && c <= "9"){
            int tmp = 0;
            if (tack.top() == "H") {
                tmp = 1;
            }
            else if (tack.top() == "C") {
                tmp = 12;
            }
            else if (tack.top() == "O") {
                tmp = 16;
            }
            else {
                tmp = stoi(tack.top());
            }
            tack.pop();
 
            tmp = tmp * stoi(c);
            tack.push(to_string(tmp)); 
        }
        idx += 1;
    }
 
    while (!tack.empty()) {
        if (tack.top() == "H") answer += 1;
        else if (tack.top() == "C") answer += 12;
        else if (tack.top() == "O") answer += 16;
        else answer += stoi(tack.top());
 
        tack.pop();
    }
    
    cout << answer << endl;
    return 0;
}