백준 1935번 C++ 풀이

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

1935번: 후위 표기식2

시간 제한	메모리 제한	solved.ac 티어
2초	128MB	실버3

문제

후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. 3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C ...이 주어진다, 그리고 피연산자에 대응 하는 값은 100보다 작거나 같은 자연수이다.

후위 표기식을 앞에서부터 계산했을 때, 식의 결과와 중간 결과가 -20억보다 크거나 같고, 20억보다 작거나 같은 입력만 주어진다.

출력

계산 결과를 소숫점 둘째 자리까지 출력한다.

---

스택에 대해 배우다보면 후위표기식에 관한 내용은 단골일 것이다. 저번에는 후위표기식으로 나타난 수식을 스택으로 계산을 하는 문제였지만(https://codejin.tistory.com/187), 이 문제는 후위표기식으로 작성된 수식을 계산해야하는 문제이다. 후위표기식으로 작성된 수식을 계산하는 방법은 중위표기식을 후위표기식으로 변환하는 과정과는 다르게 그냥 차례대로 스택에 넣으면서, 연산자가 등장하면 연산을 해주면 된다.

예제 1을 통해 조금 더 자세히 살펴보자. 예제 1은 ABC*+DE/-에 [1, 2, 3, 4, 5]인 문제이다. 스택을 선언하고, 왼쪽부터 차례로 읽으면서 시작하자.

 

우선 연산자가 등장하기 전까지 왼쪽부터 차례로 읽은 A, B, C인 1, 2, 3을 push한다. 

1

2

3

 

이제 연산자*가 등장한다. 스택에서 pop을 두번하고, pop된 두 수에 *연산을 한 값을 다시 push한다.

 

2 * 3 = 6

1

6

 

이번에는 연산자+가 등장한다. 같은 방법으로 진행하자.

1 + 6 = 7

7

 

이제 다시 D, E인 4, 5를 push하자.

7

4

5

 

이번엔 / 연산자이다. 역시 같은 방법으로 연산을 진행한다.

4 / 5 = 0.8

7

0.8

 

마지막으로 -연산이다.

7 - 0.8 = 6.2

6.2

 

후위표기식의 모든 연산이 끝났기 때문에 스택에 최종적으로 남아있는 6.2를 pop하면 그 수가 연산 결과이다.

 

/연산과 - 연산은 순서가 바뀌면 값이 달라지기 때문에(비대칭적), 이에 유의하자. 4 / 5와 5 / 4는 값이 다르기 때문이다.

 

#include <bits/stdc++.h>
using namespace std;

int n;
int* num_elem;
string infix;

void input() {
    cin >> n;
    cin >> infix;
    num_elem = new int[n];

    for(int i = 0; i < n; i++) cin >> num_elem[i];
}

void solution() {
    stack<double> compute_infix;
    double n1, n2;
    for(const auto& x : infix) {
        if(x >= 'A' && x <= 'Z') compute_infix.push(num_elem[x - 'A']);
        else {
            n2 = compute_infix.top();
            compute_infix.pop();
            n1 = compute_infix.top();
            compute_infix.pop();

            switch(x) {
            case '+':
                compute_infix.push(n1 + n2);
                break;
            case '-':
                compute_infix.push(n1 - n2);
                break;
            case '*':
                compute_infix.push(n1 * n2);
                break;
            case '/':
                compute_infix.push(n1 / n2);
                break;
            }
        }
    }
    cout << compute_infix.top();
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed;
    cout.precision(2);

    input();
    solution();
}