[Algorithm] 백준 - 후위 표기식2 (1935번)

문제

[백준] 후위 표기식2

사용 알고리즘(자료구조)

- 스택(Stack)

해결방법

• 후위 표기식이란?? 

• 예를 들어, 중위 표기식 3+4를 후위 표기식으로 표현하면 34+ 가 된다
  1. => 그렇다면? 입력 받은 식을 앞에서부터 보면서,
     • 피연산자인 경우 : 스택에 저장
     • 연산자가 나온 경우 : 스택에서 2개의 피연산자를 꺼내서 연산한 뒤, 결과값을 다시 스택에 저장
  2. 예제 1번 ) 
     5
     ABC*+DE/-
     1
     2
     3
     4
     5
     1. 처리 과정
        1. 1 push
           st : [1]
        2. 2 push
           st : [1, 2]
        3. 3 push
           st : [1, 2, 3]
        4. pop 한 후, * 연산
           st : [1, 6]
        5. pop 한 후, + 연산
           st : [7]
        6. 4 push
           st : [7, 4]
        7. 5 push
           st : [7, 4, 5]
        8. pop 한 후 / 연산
           st : [7, 0.8]
        9. pop 한 후, - 연산
           st : [6.2]

• 알파벳으로 대체된 피연산자의 값을 저장해두기 위해 map<char, int>을 사용

소스코드

사용언어 : C++

#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <iomanip>

using namespace std;

int main() 
{   
    int N;
    string expression;
    string operators = "+-*/";

    cin >> N >> expression;

    map<char, int> alpha;
    for (int i='A'; i<'A'+N; i++) {
        cin >> alpha[static_cast<char>(i)];
    }

    stack<double> st;
    for (char c : expression) {
        if (operators.find(c) == string::npos) {
            st.push(alpha[c]);
        } else {
            double num2 = st.top(); st.pop();
            double num1 = st.top(); st.pop();
            double res;
            switch (c) {
                case '+':
                    res = num1 + num2;
                    break;
                case '-':
                    res = num1 - num2;
                    break;
                case '*':
                    res = num1 * num2;
                    break;
                case '/':
                    res = num1 / num2;
                    break;
                default:
                    break;
            }
            st.push(res);
        }
    }

    cout << fixed << setprecision(2) << st.top() << endl;    

    return 0;
}

static_cast<자료형>

* 동적 캐스팅

 

string 라이브러리

* for (char c : expression)

 

* find

* string::npos

 

 

한줄평

생각보다 쉽게 푼 문제.  . 스택 자료구조를 사용하는 문제는 느낌이 비슷 한 것 같다. 마치 괄호쌍 찾는 느낌