[C++] 백준 1935번:후위 표기식2(stack)

문제링크

1935번: 후위 표기식2

문제

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

입력

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

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

출력

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

 

풀이

먼저 표기식에 대해 짚고 넘어가자. 표기식에는 크게 다음과 같이 3종류가 있다.

전위 표기식 : 문제와 반대로 연사자를 피연산자 앞에 적는 방법이다. (+AB)

중위 표기식 : 우리가 일반적으로 사용하는 방법이다. (A+B)

후위 표기식 : 문제처럼 연산자를 피연산자 뒤에 적는 방법이다. (AB+)

 

문제에서는 후위 표기식을 사용하고 있고 주어진 ABC*+DE/- 의 경우 보기 좋게 중위 표기식으로 바꿔보면 A+BC-D/E 가 된다. '+', '' 연산자의 경우는 앞에 오는 숫자와 뒤에 오는 숫자의 순서가 크게 상관이 없지만 '-', '/' 연산자의 경우는 순서가 중요하다.

이 같은 순서를 자료구조 스택을 이용하여 지켜줄 수 있다. 입력 받은 문자열을 처음부터 끝까지 돌면서 숫자라면 스택에 담는다.

만약 연산자라면 현재 스택의 top을 뒤에 오는 숫자로 저장하고 pop한 뒤 다시 top을 앞에 오는 숫자로 저장하고 pop을 진행한다. 그 후 입력 받은 연산자에 맞게 연산해준 뒤 스택에 담아주면 된다.

문자열을 모두 돌았다면 스택에는 모든 연산의 결과가 담겨있기 때문에 자릿수를 맞춰 출력해주면 된다.

코드

#include <iostream>
#include <stack>
using namespace std;
 
int arr[26];
int n;
string s;
stack<double> number;
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    cin >> s;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    int size = s.size();
 
    for (int i = 0; i < size; i++) {
        if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
            double sec = number.top();
            number.pop();
            double fir = number.top();
            number.pop();
 
            if (s[i] == '+') {
                number.push(fir + sec);
            }
            else if (s[i] == '-') {
                number.push(fir - sec);
            }
            else if (s[i] == '*') {
                number.push(fir * sec);
            }
            else if (s[i] == '/') {
                number.push(fir / sec);
            }
        }
        else {
            number.push(arr[s[i] - 'A']);
        }
    }
    cout << fixed;
    cout.precision(2);
    cout << number.top();
 }

 

메모

[C++] 백준 1874번:스택 수열(stack)