[BOJ/C++]1918번_후위 표기식(중위표기->후위표기변환)(작성중..)

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

 

#문제 풀기 위해 알아야 할 개념 :

1_ 핵심 개념 : 연산자를 보관할 Stack은 밑에서 Top()방향으로 우선순위가 낮->높 순서로 쌓여야 한다.

2_ ★코드 논리 순서(일단 암기) :

ⓐ. 알파벳 => 무조건 출력

ⓑ. ( => 무조건 Push()

ⓒ. ) => '(' 가 나올때 까지 Pop()

ⓓ. 나머지 우선순위를 가진 연산자 (높 => 낮) 순으로 한다.

3_ ★ⓒ(')')와ⓓ(우선순위를 가진 연산자) 처리 차이 기억

• ⓒ : S.top()=='('을 신경쓰고, '('는 출력을 안하고, 버림
• ⓓ : 지칭값 > 우선순위 => Push / 지칭값 <= 우선순위 => Pop() , ★그리고 '('을 신경 안써도 된다.

 

##코드

#include <iostream>
#include <stack>
#include <string>
 
using namespace std;
 
void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
 
bool IsOp(char c) {
    if (
        c == '*' ||
        c== '/'||
        c == '+' ||
        c == '-'||
        c== '(' ||
        c == ')'
        ) {
        return true;
    }
    return false;
}
 
int GP(char op) {
    if (op == '*' || op == '/') {
        return 3;
    }
    else if (op == '+' || op == '-') {
        return 2;
    }
    else if (op == '(' || op == ')') {
        return 1;
    }
 
    return 0;
}
 
int VGP(char op1, char op2) {
    return GP(op1) - GP(op2);
    /*
    + : op1이 더 우선순위
    0 : 같다.
    - : op2가 더 우선순위
    */
}
 
int main() {
 
    string text;
    stack<char> S;
    cin >> text;
 
    for (int i = 0; i < text.length(); i++) {
        char c = text[i];
 
 
        //1_ 알파벳
        if (!IsOp(c)) cout << c;
        else {
            if (c == '(')//2_ ( => 무조건 push 
            {
                S.push(c);
            }
            else if (c == ')') //3_ ) => '('가 나타나기 전까지 모두 pop() 
            {
                while (!S.empty() && S.top() != '(') {
                    
                    cout << S.top();
                    S.pop();
                }
                if (!S.empty() && S.top() == '(') {
                    S.pop();
                }
            }
            else//4_ 우선순위 쎈 : * || /
            {
                while (!S.empty() && VGP(c, S.top())<=0)//pop()하는 조건
                {
                    cout << S.top();
                    S.pop();
                }
 
                S.push(c);//지칭값 push
            }
        }
 
    }
    
    while (!S.empty()) {
        cout << S.top();
        S.pop();
    }
 
    return 0;
}