[C++] 1935. 후위 표기식2

 

후위 표기식?

제일 뒤에 입력된 것끼리 연산하는 방식으로, 대표적인 스택 문제이다.

 

[ 입력 예시 ]

입력 = ABC*+DE/-

 

첫번째 연산자

➡️ 연산자 *

➡️ 스택 상황

A	B	C
1	2	3

➡️ 연산

B * C = 2 * 3 = 6

 

❗️연산 순서 주의 ❗️

덧셈,곱셈에서는 문제가 되지 않지만 뺄셈,나눗셈에서는 문제발생한다.

첫번째 pop한 원소를 두번째 연산자로 정하고, 두번째 pop한 원소를 첫번째 연산자로 정해준다.

 

➡️ 연산 후 스택 상황

A	B*C = F
1	6

---

두번째 연산자

➡️ 연산자 +

➡️ 스택 상황 : 위 연산 후 스택 상황

➡️ 연산

A + F = 1 + 6 = 7

 

➡️ 연산 후 스택 상황

A + F = G

7

 

... 이런식으로 연산을 진행한다.

 

마지막까지 연산을 진행하면 스택의 top이 정답이 된다.

소숫점 둘째 자리까지 출력하기 때문에

cout.precision() 함수로 둘째 자리까지 출력을 해준다.

여기서 precision은 정수+소수 자리를 다 합친 자릿수이므로,

cout << fixed 를 통해서 소수 자릿수로만 정해준다.

 

[ 코드 ]

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

int N;
string inp;
int* element;

void input()
{
    cin >> N;;
    cin >> inp;
    element = new int[N];
    for(int i=0; i<N; i++) cin >> element[i];
}

void solution() {
    stack<double> cal;
    for(const auto& i : inp)
    {
        if(i >= 'A' && i <= 'Z') cal.push(element[i - 'A']); //i-'A' == element index(0~N)
        else
        {
            double t1, t2;
            t2 = cal.top(); //첫번째 pop을 두번째 연산자로 정하기
            cal.pop();
            t1 = cal.top(); //두번째 pop을 첫번째 연산자로 정하기
            cal.pop();
            
            switch (i)
            {
            case '*':
                cal.push(t1*t2); //연산된 결과를 다시 push
                break;
            case '+':
                cal.push(t1+t2);
                break;
            case '/':
                cal.push(t1/t2);
                break;
            case '-':
                cal.push(t1-t2);
                break;
            
            default:
                break;
            }
        }
    }
    cout << fixed; //소수점 자리로만 정함
    cout.precision(2); //둘째자리까지만 출력
    cout << cal.top() << "\n"; //연산이 끝나고 가장 마지막 원소가 연산결과.
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    input();
    solution();

    return 0;
}