[BOJ/백준] 1935 후위 표기식2

● [문제번호 1935] 후위 표기식2

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

1935번: 후위 표기식2

 

● 알아야 할 것

: stack, vector 자료구조와 메소드

: 정수, 실수 자료형

 

● 풀이 과정

: 후위 표기식은 stack을 이용하여 풀이할 수 있다.

: 피연산자는 stack에 쌓고

연산자를 만났을 때는 피연산자를 2개 꺼내서

계산하고 다시 stack에 쌓는다

: 이를 반복하여 마지막에는 stack에 결과값1개만 남게 된다.

 

● 주의 할 것

: 나눗셈의 소수점을 표현하기 위해 실수 자료형(double)이 필요하고

cout으로는 원하는 출력을 만들기 어렵고

printf("%.2f", number);

를 사용하여 소수점 아래 2자리를 고정적으로 출력할 수 있다.

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// 각 피연산자에 대응하는 값 저장을 위한 vector
vector<int> v;
// 후위 표기식을 계산하기 위한 stack
// 소수점을 가진 값일 수 있으니 double형(실수)
stack<double> s;
// string은 cin에서만 사용가능
// 후위 표기식을 저장할 문자배열
// 입력 조건에 길이가 100이므로 배열크기는 101로 설정
char str[101];
int N;

int main()
{
    // 사용하면 안 됨 (소수 출력을 위해)
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    
    cin >> N;
    
    // 공백없는 문자배열 입력
    scanf("%s", str);
    
    v.assign(N, 0);
    
    // 피연산자에 대응하는 값 저장
    for(int n = 0; n < N; n++)
        cin >> v[n];
    
    // 문자배열을 하나씩 확인
    for(int i = 0, n = 0; i < strlen(str); i++)
    {
        // 피연산자인 경우
        if('A' <= str[i] && str[i] <= 'Z')
        {
            // 대응하는 값 저장
            // 'A'는 첫번째이므로 vector의 index는 str[i] - 'A'
            s.push(v[str[i] - 'A']);
            n++;
        }
        // 소수점을 가진 값일 수 있으니 double형
        else if(str[i] == '+')
        {
            double temp1 = s.top();
            s.pop();
            double temp2 = s.top();
            s.pop();
            s.push(temp2 + temp1);
        }
        // 소수점을 가진 값일 수 있으니 double형
        else if(str[i] == '-')
        {
            double temp1 = s.top();
            s.pop();
            double temp2 = s.top();
            s.pop();
            s.push(temp2 - temp1);
        }
        // 소수점을 가진 값일 수 있으니 double형
        else if(str[i] == '*')
        {
            double temp1 = s.top();
            s.pop();
            double temp2 = s.top();
            s.pop();
            s.push(temp2 * temp1);
        }
        // 소수점을 가진 값일 수 있으니 double형
        else if(str[i] == '/')
        {
            double temp1 = s.top();
            s.pop();
            double temp2 = s.top();
            s.pop();
            
            s.push(temp2 / temp1);
        }
    }
    
    // 소수점 아래 2자리까지 무조건 출력을 위해 printf 사용
    // cout은 전체자릿수에 의해 출력되므로 소수점 아래 n자리까지 임의로 지정하기 불가능하여 원하는 대로 출력 안됨
    printf("%.2f", s.top());
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [203 - 자료구조 1 (참고)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	1935	후위 표기식2	https://pirateturtle.tistory.com/170
2	1918	후위 표기식	https://pirateturtle.tistory.com/171
3	10808	알파벳 개수	https://pirateturtle.tistory.com/172
4	10809	알파벳 찾기	https://pirateturtle.tistory.com/173
5	10820	문자열 분석	https://pirateturtle.tistory.com/174
6	2743	단어 길이 재기	https://pirateturtle.tistory.com/175
7	11655	ROT13	https://pirateturtle.tistory.com/176
8	10824	네 수	https://pirateturtle.tistory.com/177
9	11656	접미사 배열	https://pirateturtle.tistory.com/178