[C++] 백준 1918 - 후위 표기식, 반례

• 문제

• 풀이 과정

• 1. +, -, /, *

• 2. (

• 3. )

• 실수 및 반례

• 최종 코드

• 잡담

백준 1918 : 후위 표기식
난이도 : 골드 2

시간 : 56분 소요

 

 

 

문제

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

1918번: 후위 표기식

풀이 과정

풀이 과정은 생각보다 단순하다.

스택을 사용하면 쉽게 구현할 수 있다.

 

 

먼저 피연산자는 결과 문자열(result) 뒤에 바로바로 넣어준다.

 

연산자를 처리하는 것이 관건이다.

 

1. +, -, /, *

위의 4개의 연산자는 아래의 규칙을 따른다. 

 1. 스택이 비어있으면 스택에 해당 연산자를 넣는다.

 

 2. 비어있지 않으면 비교 연산자가 해당 연산자에 비해 계산 상 우선순위에 있는지 확인한다.

  2-1. 비교 연산자가 우선순위에 있다면 해당 연산자를 pop하고, 결과값(result)에 넣어준다.

        2-1-1. pop했다면 새로운 top값과 해당 연산자를 비교하기 위해 2번과정을 반복한다.

  2-2. 해당 연산자가 우선순위에 있다면 스택에 push 해준다.

 

2. (

무조건 스택에 넣는다.

 

3. )

'(' 가 top값이 될 때까지 피연산자를 pop해서 결과값(result)에 넣어준다.

'('이 top값이 되면 '('도 pop 해준다.

 

 

실수 및 반례

입력 : A*((B*C)*D)*E

출력 : ABC*D**E*

 

check 함수에서 pop하다가 stack이 비워지면 해당 연산자를 넣어줘야 하는데 그 과정을 생략했었다.

그래서 반례를 찾느라 30분정도를 썼다.

check 함수에서 while문 밖에 push 코드를 넣어주니 통과했다.

 

 

최종 코드

#include <iostream>
#include <cstring>
#include <stack>

using namespace ::std;

string nota;
stack<char> st;
string result;

int oper(char q){
    if(q == '+' || q == '-'){
        return 1;
    }else if(q == '*' || q == '/'){
        return 2;
    }else{
        return 0;
    }
}

void check(char q){
    if(st.empty()){
        st.push(q);
        return;
    }
    char tmp = oper(q);
  
    while(!st.empty()){
        if(oper(st.top()) >= tmp){
            char p = st.top();
            result += p;
            st.pop();
        }else{
            st.push(q);
            return;
        }
    }
    st.push(q);  // 추가한 코드
}

int main(){
    cin >> nota;
    
    for(int i=0; i<nota.length(); i++){
        if(nota[i] == '+' || nota[i] == '-' || nota[i] == '*' || nota[i] == '/'){
            check(nota[i]);
        }else if(nota[i] == '('){
            st.push(nota[i]);
        }else if(nota[i] == ')'){
            
            while(st.top() != '('){
                char t = st.top();
                result += t;
                st.pop();
            }
            st.pop();
            
        }else{
            result += nota[i];
        }
    }
    
    while(!st.empty()){
        char t = st.top();
        result += t;
        st.pop();
    }
    
    cout << result << '\n';
}

 

 

 

잡담

자료구조 시간 때 이미 배운 거라 그런지 골드2 난이도처럼 느껴지진 않았다.