백준 1918 - 후위 표기식

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

1918번: 후위 표기식

스택을 활용해 해결하는 문제. 학교에서 한번 배운 덕분에 겨우 풀었다..

 

0. 문제 해결을 위해 두 개의 스택을 선언한다.

 

하나는 연산자를 저장하는 Operator, 다른 하나는 피연산자를 저장하는 Operand이다.

이때, 피연산자에는 이미 완성된 표기식 또한 저장될 수 있다. 이는 풀이를 진행하면서 더 자세히 설명한다.

 

1. 기본형인 A+B에서부터 시작해보자.

프로그램이 마지막 문자까지 읽고나면, 두 개의 스택은 다음과 같은 상태일 것이다.

A+B

문제의 지시대로 연산자를 오른쪽으로 꺼내야 한다.

이를 구현하기 위해 다음과 같은 코드를 작성한다.

    string op1 = Operand.top(); Operand.pop();
    string op2 = Operand.top(); Operand.pop();
    char oper = Operator.top(); Operator.pop();

    Operand.push(op2 + op1 + oper);

Operand에서 2번 pop, Operator에서 1번 pop 한 뒤, 이를 적절히 연결해 완성된 결과물을 다시 Operand에 push한다.

이를 PMP 연산(pop - merge - push, 내 맘대로 이름 지음)이라 하자.

 

PMP 연산을 위의 예시에 적용하면 다음과 같다.

위에서 언급한 것처럼 피연산자에 이미 완성된 표기식 AB+가 저장되었다!

 

마지막까지 PMP 연산을 수행하면, Operand 스택에는 출력을 기다리는 단 하나의 후위 표기식만이 남을 것이다.

 

2. 이제 A*B+C, 우선순위가 여러 가지인 연산을 변환해보자.

 

A*B 까지는 앞의 예시와 비슷하게 진행될 텐데, + 더하기가 들어오면 어떻게 될까?

곱하기는 더하기보다 먼저 수행되어야 하므로, +를 스택에 저장하기 전에 곱하기를 먼저 수행해야 한다.

 

그림으로 나타내면 다음과 같다.

사실 좀 더 생각해보면, 우리는 A+B+C처럼 우선순위가 동일한 연산에서도 앞의 +를 먼저 계산한 뒤 뒤의 +를 계산한다.

 

따라서 일반화하면, 현재 Operator 스택의 맨 위에 있는 연산과 우선순위가 같거나 더 낮은 연산이 입력되면, 먼저 PMP연산을 수행하고 나서 입력받은 연산을 저장해야 한다. 우선순위가 더 크다면 PMP연산 없이 입력받은 연산자를 push한다.

 

식 A+B*C-D를 생각해보자.

여기까진 무사히 진행됐는데, -가 들어오면 어떻게 되는가?

현재 연산자 스택의 맨 위에 있는 연산은 *, 입력받은 연산은 -이므로, 현재 우선순위가 더 크다. 따라서 위의 규칙대로 PMP를 수행한다. 그런데 PMP를 수행하고 나니, 오잉? 연산자 스택의 맨 위에 새로 위치하게 된 연산 + 역시 -와 우선순위가 같다. 따라서 PMP연산을 또 수행해야 한다!

 

요약하자면 PMP연산을 통해 갱신된 연산자의 top에 대해서도 계속 비교를 진행하며 PMP연산을 반복해야 한다. 더 짧게 말하면 if가 아니라 while로 구현해야 한다. 나는 이 점을 깨닫는 데 시간이 좀 걸렸다.

 

3. 그럼 괄호는 어떻게 처리하는가?

 

글이 너무 길어지므로.. 짧게 설명한다.

괄호는 여는 괄호 '('와 닫는 괄호 ')'로 나뉘는데, 여는 괄호의 경우 무조건 PMP 없이 스택에 저장한다.

저장한 뒤 기존 규칙대로 입력을 받다가, 닫는 괄호가 등장하면 괄호 내부의 표기식만 먼저 처리한다.

여는 괄호가 나올 때까지 PMP를 수행하고, 반복을 마치면 여는 괄호를 제거하면 된다.

4. 실제 구현 코드

괄호 처리에 유의해서 작성한다.

int main() {
    char ch;
    string temp;

    while ((ch = getchar()) != '\n') {

        //닫는 괄호
        if (ch == ')') {
            //처음 여는 괄호가 나올 때까지 PMP
            while (Operator.top() != '(') PMP();
            Operator.pop();
        }

        //연산자
        else if (isOperator(ch)) {
            //현재 top 연산자의 우선순위가 새 연산자의 우선순위보다 크거나 같은 경우
            while (!Operator.empty() && Operator.top() != '(' && (getPrec(Operator.top()) >= getPrec(ch))) PMP();
            Operator.push(ch);
        }

        //피연산자
        else {
            temp = ch;
            Operand.push(temp);
        }
    }

    //마지막 1번 더
    while (!Operator.empty())
        PMP();

    cout << Operand.top() << endl;
}

 

배운 내용

 

문자 하나씩 입력받기

while ((ch = getchar()) != '\n')

무작정 타이핑부터 하지 말고 코드 설계부터 하자

 

반복되는 내용 함수로 빼기, 직관적인 변수명 설정은 읽는 사람 뿐만 아니라 나한테도 꼭 필요하다.

 

위 내용들만 지키면 코드는 생각보다 간단해진다.