[BOJ알고리즘, C++]#1918_후위 표기식, 스택 자료구조, stack

#1. 문제

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

 

---

 

#2. 풀이

 

1. 스택

[자료 구조]#0_선형 자료구조

스택 자료구조는 후입선출 방식으로 동작하는 선형 자료구조로, 데이터 목록의 한쪽 끝에서만 삽입/삭제 연산이 이루어지는 특징이 있습니다.

 

2. 문자, 열린 괄호, 닫힌 괄호, 그리고 연산자일 경우로 나누자

1. 먼저, 문자일 경우 결과 문자열에 바로바로 추가해줍니다.
2. 다음으로, 열린 괄호일 경우 스택에 추가해 줍니다.
3. 다음으로, 닫힌 괄호일 경우 열린 괄호를 만날 때까지 스택의 데이터 항목을 결과 문자열에 추가해 주고, 스택에서 해당 항목을 제거해 줍니다.
4. 마지막으로, 연산자일 경우 s.top()과 비교하여 그 우선순위가 더 작은 연산자(* 혹은 /는 +와 -보다 우선순위가 더 높은 연산자로 가정)를 만날 때까지 스택의 데이터 항목을 결과 문자열에 추가해 주고 해당 항목을 제거해 준다. 그리고, 현재 연산자를 스택에 추가해 줍니다.
5. 위 작업을 모두 마치고 나와서, 스택 자료구조에 남아 있는 내용을 차례대로 결과 문자열에 추가해 줍니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/1918
*   @문제: 중위 표기식 -> 후위 표기식
*   @설명
        1. 알파벳의 경우 결과 문자열에 바로바로 추가
        2. 열린 괄호는 stack에 push
        3. 닫힌 괄호는 '열린괄호' 만날 때까지 stack에 있는 내용들 결과 문자열에 추가
        4. 연산자는 s.top() 보다 우선순위가 클 때까지, stack에 있는 내용들 결과 문자열에 추가
        5. 마지막으로, 스택에 남아 있는 애들 처리
*/


#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <map>
#include <algorithm>
using namespace std;

map<char, int> m = {
    {'(', 0},
    {'+', 1},
    {'-', 1},
    {'*', 2},
    {'/', 2}
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    stack<char> s;

    string inFix = "";
    string postFix = "";
    getline(cin, inFix);

    for(int i=0; i<(int)inFix.size(); ++i)
    {
        // @알파벳
        if(isalpha(inFix[i]))
        {
            postFix += inFix[i];
        }
        // @열린 괄호
        else if(inFix[i] == '(')
        {
            s.push(inFix[i]);
        }
        // @닫힌 괄호
        else if(inFix[i] == ')')
        {
            while(!s.empty() && s.top() != '(')
            {
                postFix += s.top();
                s.pop();
            }
            if(!s.empty() && s.top() == '(') s.pop();
        }
        // @연산자
        else
        {
            while(!s.empty() && m[s.top()] >= m[inFix[i]])
            {
                postFix += s.top();
                s.pop();
            }
            s.push(inFix[i]);
        }
    }

    // @스택 남은거 처리
    if(!s.empty())
    {
        while(!s.empty())
        {
            postFix += s.top();
            s.pop();
        }
    }

    cout << postFix;

    return 0;
}

 

---