[백준/Baekjoon] 1918 후위 표기식 C++ :: Data Structure & Stack

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

1918번: 후위 표기식

---

1. Logic

중위 표기식은 연산자가 연산이 필요한 곳에 위치하는 우리가 흔히 쓰는 연산식이다. 반면 후위 표기식은 컴퓨터가 사용하는 연산자가 뒤에 있는 표기식이다. 컴퓨터는 우리가 아는 중위 표기식을 후위 표기식으로 변환해서 연산을 진행한다.

이 과정에서 스택이라는 자료구조가 필요하다.

 

중위 표기식 > 후위 표기식 변환 로직

1. 피연산자(연산하고싶은 숫자) 무조건 출력

2. 연산자인 경우

  2-1. stack.top() 보다 우선 순위가 큰 경우 > stack.push

  2-2. stack.top()보다 우선 순위가 작은 경우 > stack.top()보다 우선순위가 커질 때 까지 stack.top() 출력 &  stack.pop

3. '(' 무조건 stack.push

4. ')'면 '(' 나올 때 까지 stack.top출력 & stack.pop() 다 하고 stack에서 남은 '(' pop

5. 식이 다 끝났으면 stack에 남아있는 연산자 모두 출력

 

우선순위

연산자 우선순위

1. '('
2. +, -
3. *, /

'('는 항상 push해야하는데 '('의 우선순위가 가장 낮은 이유는 만약 '('의 우선순위가 가장 높으면 stack.top()이 '('일 때 다른 연산자가 들어오면 바로 (을 pop해버리기 때문에 가장 낮은 우선순위를 줬다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int priority(char ch) {
    if(ch == '+' || ch == '-') return 1;
    if(ch == '*' || ch == '/') return 2;
    return 0;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    stack<char> oper;
    
    string ans = "";
    string str;
    
    cin >> str;
    
    for(int i = 0; i < str.size(); i++) {
        if(str[i] >= 'A' && str[i] <= 'Z') {
            cout << str[i];
            continue;
        }
        
        if(oper.empty() || str[i] == '(') {
            oper.push(str[i]);
            continue;
        }
        
        if(str[i] == ')') {
            while(oper.top() != '(') {
                cout << oper.top();
                oper.pop();
            }
            oper.pop();
            continue;
        }
        
        if(priority(oper.top()) < priority(str[i])) {
            oper.push(str[i]);
        }
        else {
            while(!oper.empty() && priority(oper.top()) >= priority(str[i])) {
                cout << oper.top();
                oper.pop();
            }
            oper.push(str[i]);
        }
    }
    
    while(!oper.empty()) {
        cout << oper.top();
        oper.pop();
    }
}

---

3. Feedback

체고!

https://charles098.tistory.com/10

[C++] 중위 표기식을 후위 표기식으로 변환 후 계산

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90