[백준(BOJ)/C++] 1918번: 후위 표기식 - 코딩밥상

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

1918번: 후위 표기식

 

접근방법

대표적인 스택 자료구조를 활용하여 풀 수 있는 문제이다.

우리가 흔히 알고있는 계산식은 중위 표기식인데 이는 피연산자 사이에 연산자가 들어가는 구조이지만, 이 문제에서 제시하는 후위 표기식은 피연산자 뒤에 연산자를 나타내는 방식으로 컴퓨터 논리 순서에 용이하게 식을 바꾸는 문제이다.

즉 중위표기식에서 연산자만 따로 스택에 관리하여 후위 표기식으로 풀어쓰는 방식이다.

 

알고리즘

-입력 받은 문자열을 char형으로 하나하나씩 받아 조건에 따라 분류

-받은 토큰(char)이 피연산자이면 결과값이 되는 문자열에 추가

-받은 토큰이 연산자라면 조건에 맞게 스택에서 관리

• 받은 연산자의 우선순위가 현 스택의 top보다 낮으면 top을 꺼내어 결과값에 추가
• 작업이 끝나면 받은 연산자는 스택에 저장 

-토큰이 ')'라면 '('가 올 때까지 스택에 저장되어있는 연산자들을 꺼내어 결과값에 추가

-입력받은 문자열을 모두 받은 후에 스택에 남아있는 연산자들을 모두 결과값에 추가

 

 

코드

#include <iostream>
#include <stack>
#include <cstring>
using namespace std;

int main(){
    string before;
    string after;
    
    cin>>before;
    
    stack<char> stack;
    for(int i=0; i<before.length(); i++){
        char token = before[i];
        
        switch (token) {
            case '(':
                stack.push(token);
                break;
                
            case ')':
                while(stack.top() != '('){  //괄호 안 연산자들 처리
                    after += stack.top();
                    stack.pop();
                }
                stack.pop();
                break;
            
            case '*': case '/':
                if(!stack.empty()){
                    while(!stack.empty() && stack.top() != '('){
                        if(stack.top() == '*' || stack.top() == '/'){
                            after += stack.top();
                            stack.pop();
                        }
                        else break;
                    }
                }
                
                stack.push(token);
                break;
                
            case '+': case '-':
                if(!stack.empty()){
                    while(!stack.empty() && stack.top() != '('){
                        after += stack.top();
                        stack.pop();
                    }
                }
                
                stack.push(token);
                break;
                
            default:    //피연산자일 경우 바로 후위식으로 넣어줌
                after += token;
                break;
        }
    }
    
    while(!stack.empty()){
        after += stack.top();
        stack.pop();
    }
    
    cout<<after<<'\n';
}

 

'(' , ')' : 연산자 우선순위가 가장 높기 때문에 '(' 후에 ')'가 등장할 때 까지 최우선순위로 처리

'*' , '/' : 다음으로 우선순위가 높기 때문에 먼저 오는 곱셈,나눗셈 연산자만 우선순위 처리

'+' , '-' : 가장 낮은 운선순위이기 때문에 앞서 나오는 모든 연산자들(스택에 있는 연산자들)을 우선순위 처리