1918번: 후위 표기식

첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의

www.acmicpc.net

문제 분석

  • 시간 제한 2초: Big-O 기준 2억연산
  • 다루는 값들의 수 100
  • 문자열로 입력된 값을 우선순위에 맞춰 출력 해줘야 함
  • 우선순위 : A~Z > *,/ > +,- 
  • '()'에 대한 처리도 해줘야함

주의 사항

  • '()'안에 들어 있는 식은 독자적인 하나의 식으로 생각하기
  • '(',')'는 출력하지 않는다.

풀이 방식

  • 문자 하나씩 stack에 쌓기
  • stack.top 이 문자보다 우선순위가 높거나 같으면 출력하고 pop
  • '('의 우선순위는 A~Z 보다 낮고 연산자 보다 높다.
  • ')'가 나오면 가장 위에 있는 '(' 까지 pop
  • 마지막으로 stack에 남아있는 문자 전부 pop
stack<char> opr;
string exp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> exp;
    for (char &c: exp) {
        if (c >= 'A' && c <= 'Z') { // 가장 우선순위 높음 pop해줄 거 없음
            opr.push(c);
        } else if (c == '(') { // 우선순위 두번째
            while (!opr.empty() && opr.top() != '(') {
            //괄호 안에 있는 식은 독자적인 식으로 생각하기 위해 
            //stack이 비거나 괄호 안에 있는 식일때 까지 반복
                if (opr.top() >= 'A' && opr.top() <= 'Z') {//A~Z 만 pop
                    cout << opr.top();
                    opr.pop();
                } else break;
            }
            opr.push(c);
        } else if (c == '*' || c == '/') {//우선순위 세번째
        	//'('와는 비교하지않음, 괄호안에 있는 식은 독자적인 식
            while (!opr.empty() && opr.top() != '(') {
                if (opr.top() >= 'A' && opr.top() <= 'Z') {
                    cout << opr.top();
                    opr.pop();
                } else if (opr.top() == '*' || opr.top() == '/') {
                    cout << opr.top();
                    opr.pop();
                } else {
                    break;
                }
            }
            opr.push(c);
        } else if (c == '+' || c == '-') {
            while (!opr.empty() && opr.top() != '(') {
            //우선순위가 가장 낮으므로 비교없이 전부 pop
                cout << opr.top();
                opr.pop();
            }
            opr.push(c);
        } else if (c == ')' && !opr.empty()) {
        //')' 가 나오면 '('까지 pop
            while (!opr.empty() && opr.top() != '(') {
                cout << opr.top();
                opr.pop();
            }
            opr.pop();
        }
    }
    //stack에 남은거 pop
    while (!opr.empty()) {
        cout << opr.top();
        opr.pop();
    }
    return 0;
}

느낀 점

  • 괄호연산이 없는 후위표기식 문제는 풀어봤기에 어렵지 않게 풀 수 있을 거라 생각했다.
  • 괄호를 처리해 주기 위해 연산과정을 그림을 그려가며 스스로 후위 표기식으로 식을 바꿔 봤다.
  • stack 그림을 그려가며 푸니까 스스로 어떤 사고방식으로 후위 표기식으로 바꾸는지 파악하고, 이 사고방식을 코드로 옮겨 봤다.
  • 그럼에도 구현이 쉽지는 않았지만 큰 어려움 없이 해결했다.

'Algorithm > baekjoon' 카테고리의 다른 글

[BOJ 1655] 가운데를 말해요  (0) 2022.07.30
[BOJ 5052] 전화번호 목록  (0) 2022.07.27
[BOJ 2493] 탑  (0) 2022.07.26
[BOJ 17299] 오등큰수  (0) 2022.07.26
[BOJ 17298] 오큰수  (0) 2022.07.26

+ Recent posts