[백준][C++] 1918 후위 표기식

www.acmicpc.net/problem/1918

1918번: 후위 표기식

 

 

 

알고리즘 종류

자료구조

스택

 

 

 

사고 과정

스택을 이용해서 풀 수 있습니다. 문제에서 제시된 예시를 손으로 풀어보면 나중에 나온 연산자가 알파벳 뒤에 먼저 붙는 것을 알 수 있습니다. 그리고 문자는 그대로 출력되는 것을 알 수 있습니다. 그래서 문자는 그대로 출력하고 연산자만 스택에 넣어서 해결하면 될 것 같습니다.

 

조건이 몇 가지 있습니다.

 

1. 괄호로 인해서 우선순위가 바뀔 수 있습니다. 그래서 괄호도 스택에 넣어줍니다.

 

2. + 또는 - 가 나오면 스택에서 '('를 제외하고 다 뽑습니다. 이들은 우선순위가 제일 낮기 때문입니다.

 

3. * 또는 / 가 나오면 스택에서 * 또는 / 일 때만 뽑습니다. 우선순위가 제일 높기 때문입니다. (문제에서 제시된 예시를 손으로 해보면 알 수 있습니다.)

 

4. )가 나오면 (를 만날 때까지 뽑습니다.

 

5. for문이 끝났다면, 스택에 남아있는 연산자들을 모두 뽑습니다.

 

 

 

구현(C++)

#include <iostream>
#include <stack>
#include <string>
 
using namespace std;
 
string str;
 
stack<char> s;
 
 
int main(void){
    
    cin >> str;
 
    for(int i=0; i<str.length(); i++){
        char c = str[i];
 
        if(c >= 'A' && c <= 'Z') cout << c;
        
        else if(c == '(') s.push(c);
        
        else if(c == ')'){
            while(s.top() != '('){
                cout << s.top();
                s.pop();
            }
            s.pop();
        }
        
        else if(c == '+' || c == '-'){
            while(!s.empty() && s.top() != '('){
                cout << s.top();
                s.pop();
            }
            s.push(c);
        }
        
        else if(c == '*' || c == '/'){
            while(!s.empty() && (s.top() == '*' || s.top() == '/')){
                cout << s.top();
                s.pop();
            }
            s.push(c);
        }
    }
    
    while(!s.empty()){
        cout << s.top();
        s.pop();
    }
}

 

 

 

시행착오