[BOJ] 백준 1918 후위 표기식 / 스택(Stack)

---

 

 

💣 문제 이해

 

 

후위 표기법(postfix)은 연산자가 피연산자 뒤에 위치하는 방법이다.

예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다.

중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성한다.

 

스택(Stack)을 활용하여 풀이했다.

 

 

💭 풀이 과정

 

 

C++ Stack 라이브러리를 참조하여 중위 표기법을 구현하였다.

 

 

작성 언어: C++

 

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

int main() {
    string expression = "";
    stack<char> s1;
    
    cin >> expression;
    
    for (int i = 0; i < expression.length(); ++i) {
        if (expression[i] >= 60) {
            // 피연산자 출력(모든 문자 숫자는 ASCII 코드로 60 이상임)
            cout << expression[i];
        }else {
            if (expression[i] == '*' || expression[i] == '/') {
                if (!s1.empty()) {
                    if (s1.top() == '*' || s1.top() == '/') {
                        cout << s1.top();
                        s1.pop();
                    }
                }
                s1.push(expression[i]);
            }else if (expression[i] == '+' || expression[i] == '-') {
                if (s1.empty()) {
                    s1.push(expression[i]);
                }else {
                    while (!s1.empty()) {
                        if (s1.top() == '(')    break;
                        cout << s1.top();
                        s1.pop();
                    }
                    s1.push(expression[i]);
                }
            }else if (expression[i] == '(') {
                s1.push(expression[i]);
            }else if (expression[i] == ')') {
                while (s1.top() != '(') {
                    cout << s1.top();
                    s1.pop();
                }
                s1.pop();
            }else {
                cout << "뭔가 잘못 읽어왔슈!!!" << endl;
                exit(1);
            }
        }
    }
    
    while (!s1.empty()) {
        cout << s1.top();
        s1.pop();
    }
}

 

 

❗️ "*" 또는 "/" 연산자의 경우

      1) 스택이 비어있지 않다면, 스택의 top이 "*"와 "/"인 경우 동일한 우선순위이므로 pop 시킨다.

      2) 새로 읽어온 연산자를 push 한다.

❗️ "+" 또는 "-" 연산자의 경우

      1) 스택이 비어있다면 그냥 push 한다.

      2) 비어있지 않다면, 스택이 비워지거나 여는 괄호("(")를 만날 때까지 pop 한다. 그 후 새로 읽어온 연산자를 push 한다.

 

❗️ "(" 또는 ")"의 경우

      1) "("의 경우 무조건 push 한다.

      2) ")"의 경우 여는 괄호("(")를 만날 때까지 pop 한다. 이후 여는 괄호 역시 pop 한다.

 

 

🏆 배운 점

 

 

자료구조 수업시간에 스택을 배우면서 과제로 수행했던 중위 표기식 -> 후위 표기식 변환을 구현하는 내용이었다.

역시 오랜만에 복습하며 다시 내용을 상기할 수 있어 유익했다.