[백준] 1918 : 후위 표기식

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

1918번: 후위 표기식

 

스택을 이용한 꽤 유명한 문제이다. 

연산자 우선순위를 고려하여 적절하게 출력한다.

 

연산자 우선순위

() > *,/  > +, -

*, / : 우선순위 가장 높음 (숫자 2) -- 숫자가 클수록 우선순위 크다고 가정

+, - : 우선순위 낮음 (숫자 1)

• 문자의 경우 등장시마다 문자열에 저장하고, 연산자의 위치와 순서를 로직에서 결정한다.
• ()의 경우 ) 부분에서 ( 앞 부분까지 먼저 출력한다.
• *, /와 +,-는 그 전의 연산자가 무엇인지가 출력 여부를 결정한다.
  • 이전 연산자의 우선순위가 현재 연산자보다 더 크거나 같을 경우 먼저 계산되므로 스택에 이미 저장된 연산자들을 출력한다.
  • 그렇지 않을 경우 (이전의 연산자의 우선순위가 현재 연산자 우선순위보다 작을 경우) 현재 연산자 부분이 먼저 계산되므로 현재 연산자를 스택에 저장한다. (출력 예상 결과 : 현재 연산자 출력 후 ->  이전 저장된 연산자 출력)

코드

#include <bits/stdc++.h>
using namespace std;

stack<char> op; // 연산자 저장 스택

//우선순위 정하는 함수
int prio(char c){
    if (c=='*' || c=='/') return 2; // 가장 높음
    else if (c=='+' || c=='-') return 1;
    else return -1;
}

int main(){
    //1. 입력받기
    string str="";
    cin  >> str;
    string result="";
    //2. 구현
    for(int i=0;i<str.length();i++){
        char c = str[i];
        if (('A'<=c) && (c<='Z')) result += c;
        else if (c=='(') op.push(c);
        else if (c==')'){
            while (op.top() != '('){
                result += op.top();
                op.pop();
            }
            op.pop(); // '(' 제거
        }
        else{ // 이전 연산자가 더 크거나 같은 우선순위일 경우 출력
            while (!op.empty() && prio(op.top())>=prio(c)){
                result += op.top();
                op.pop();
            } op.push(c);
        } 
    }
    // 스택에 있는 값 모두 출력
    while(!op.empty()){
        result += op.top();
        op.pop();
    }
    // 3. 정답 출력
    cout << result;
}