BOJ - 1935. 후위표기식2

문제

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

입력

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

출력

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

예제 입력 1

5 ABC*+DE/- 1 2 3 4 5

예제 출력 1

6.20

예제 입력 2

1 AA+A+ 1

예제 출력 2

3.00

---

사용할 자료구조

1. 피연산자를 담을 공간을 스택으로 구현하였습니다.

2. 피연산자는 A-Z의 대문자인데 입력한 숫자에 대응해야하기 때문에 key값을 알파벳, value값을 숫자로 갖는 맵을 생각했습니다.

풀이 과정

1. 문제에서 A부터 순서대로 N개의 영대문자만들 사용한다고 하여 map의 key값을 A,B,C,... 순으로 하나씩 늘리며 입력받은 value값과 함께 저장해두었습니다.

 

char key='A'; for(int i=0;i<n;i++){ int value; cin>>value; mp.insert(make_pair(key,value)); key++; }

 

2. 입력받은 문자의 크기만큼 루프를 돌며 스택에 저장하였습니다.

 

2-1) 입력받은 문자가 A~Z사이의 문자일 경우(피연산자일 경우), map의 key값에 대응하는 value값을 스택에 담았습니다.

 

2-2) 연산자일 경우, 스택의 가장 위쪽에 위치한 두개의 숫자를 pop하여 계산한 이후, 다시 스택에 push 하였습니다. (다음 연산에 사용해야하므로)

 

double top1 = st.top(); st.pop(); double top2 = st.top(); st.pop(); if(str[i]=='+'){ st.push(top2+top1); }else if(str[i]=='-'){ st.push(top2-top1); }else if(str[i]=='*'){ st.push(top2*top1); }else if(str[i]=='/'){ st.push(top2/top1); }

 

 

3. 루프를 다 돌고나면 최종 결과만 스택에 남으므로 해당 결과를 출력해주면 됩니다. 문제에서 소수점 두자리까지만 출력하라고 되어있으므로, 미리 double 형태로 받았고 두자리 형식에 맞게 출력해주었습니다.

 

answer = st.top(); cout<<fixed; cout.precision(2); cout<<answer;

시간복잡도

map 에 삽입하고 탐색하는데 O(logN)만큼 걸립니다

스택에 삽입하고 삭제하는데 O(1) 만큼 걸립니다

n만큼 루프를 돌며 map에 접근하고 str.size()만큼 루프를 돌며 스택에 삽입,삭제하므로 O(nlogN)+ O(n) ⇒ O(nlogN) 입니다(?)

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#include <functional>
using namespace std;

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int n;
    string str;
    double answer = 0;
    stack<double> st;
    map<char,double> mp;
    cin>>n>>str;
    char key='A';
    for(int i=0;i<n;i++){
        int value;
        cin>>value;
        mp.insert(make_pair(key,value));
        key++;
    }

    for(int i=0;i<str.size();i++){
        if(str[i]-'\0'>=65 && str[i]-'\0'<=90){
            st.push(mp[str[i]]);
        }else{
            double top1 = st.top();
            st.pop();
            double top2 = st.top();
            st.pop();
            if(str[i]=='+'){ 
                st.push(top2+top1);
            }else if(str[i]=='-'){
                st.push(top2-top1);
            }else if(str[i]=='*'){
                st.push(top2*top1);
            }else if(str[i]=='/'){
                st.push(top2/top1);
            }
        }
    }
    answer = st.top();
    cout<<fixed;
    cout.precision(2);
    cout<<answer;

    return 0;
}