[BOJ/백준] 1918 후위 표기식

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

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

1918번: 후위 표기식

 

● 알아야 할 것

: stack 자료구조와 메소드

: 후위 표기식에 대한 이해

 

● 풀이 과정

: 후위 표기식에 대한 이해가 있으면 쉽게 구현가능

 

1. 피연산자는 바로 출력

2. 연산자는 stack에 있는 동일하거나 높은 우선순위의 연산자를 출력

3. 남아있는 stack의 연산자 모두 출력

 

: '(' 의 우선순위가 제일 높으므로 일단 stack에 저장

: ')' 는 저장하지 않고 stack의 '(' 연산자가 나올 때 까지 출력

: '*' , '/' 는 동일하거나 ( '*' ,  '/' ) (높은) 우선순위의 연산자 모두 출력

: '+' , '-' 는 동일하거나 ( '+' ,  '-' ) 높은 ( '*' , '/' ) 우선순위의 연산자 모두 출력

 

● 주의 할 것

: 연산자의 우선순위를 이해할 때 우선순위 1이 우선순위 2보다 높다.

: 동일하거나 높은 우선순위의 연산자를 뽑을 때 stack이 비어있는 지 확인해야한다.

 

● 참고 할 것

: (이해를 위한 링크) https://jaimemin.tistory.com/828

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// 연산자를 저장할 stack
// 우선순위 1 '(' ')'   이지만 개별적으로 작업
// 우선순위 2 '*' '/'
// 우선순위 3 '+' '-'
// 연산자의 우선순위와 같거나 높은 연산자를 출력
// 사실상 '*' '/' 과 '+' '-' 의 우선순위 비교
stack<char> s;
string str;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> str;
    
    for(int i = 0; i < str.length(); i++)
    {
        // 피연산자인 경우 바로 출력
        if('A' <= str[i] && str[i] <= 'Z')
            cout << str[i];
        // 우선순위 제일 낮으므로 '('가 나올 때 까지 출력
        else if(str[i] == '+' || str[i] == '-')
        {
            while(!s.empty() && s.top() != '(')
            {
                cout << s.top();
                s.pop();
            }
            // 현재 연산자 저장
            s.push(str[i]);
        }
        // 동일하거나 (높은) 우선순위까지만 출력
        else if(str[i] == '*' || str[i] == '/')
        {
            while(!s.empty() && (s.top() == '*' || s.top() == '/'))
            {
                cout << s.top();
                s.pop();
            }
            // 현재 연산자 저장
            s.push(str[i]);
        }
        // '('연산자는 바로 저장
        else if(str[i] == '(')
        {
            s.push(str[i]);
        }
        // ')'연산자는 '('연산자가 나올 때까지 모든 연산자 출력
        else if(str[i] == ')')
        {
            while(!s.empty() && s.top() != '(')
            {
                cout << s.top();
                s.pop();
            }
            // '(' 꺼내기
            s.pop();
        }
    }
    
    // 남아있는 연산자 모두 출력
    while(!s.empty())
    {
        cout << s.top();
        s.pop();
    }
    
    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