[자료구조] 윤성우의 열혈 자료구조 08-2 중위 표기법의 소괄호 문제풀이

문제

 

보통 자료구조 과목에서 중위 표기법의 소괄호 출력까지 신경을 쓰지는 않는다.

순회 자체를 더 중요시하기 때문이다.

하지만 이는 여러분이 궁금해 할 수 있는 부분이다.

그래서 소괄호의 출력을 위한 힌트를 제시하고 문제의 해결을 돕기로 하겠다. 먼저 다음 세 중위 표기법을 보자.

 

• 3 + 2 * 7
• 3 + ( 2 * 7 )
• ( 3 + ( 2 * 7 ) )

셋 다 그 내용이 동일한 수식이다. 따라서 이를 수식 트리로 표현하면 그 결과는 당연히 같을 수밖에 없다. 

같지 않다면 잘못된 것이다. 자! 그럼 생각해보자. 위 수식을 표현한 수식 트리 각각을 대상으로 다음과 같이 요청을 한다면,

이 수식 트리에 담긴 수식을 중위 표기법의 수식으로 출력하여라!

어떻게 출력이 이루어지겠는가 ? 

첫 번째 수식을 대상으로 만들어진 수식 트리는 첫번째 수식을 출력하고, 세 번째 수식을 대상으로 만들어진 수식 트리는 세 번째 수식을 출력하도록 할 수 있겠는가 ?

불가능하다. 위의 세 수식을 대상으로 만들어진 수식 트리는 그 결과가 모두 동일한데 어떻게 다른 결과를 보이게 할 수 있겠는가!

 

그래서 우리는 구현에 앞서 중위 표기법의 출력 방식을 먼저 결정해야한다. 

그리고 필자가 추천하는 방식은 다음과 같다.

( 3 + ( 2 * 7 ) )

이 방식의 출력을 추천하는 이유는 연산자의 수와 소괄호 한쌍의 수가 일치하기 때문이며, 이것이 바로 문제해결의 힌트이다. 

그리고 이것을 성공하면, 코드를 조금 더 확장해서 여러분의 입맛에 맞는 방식의 출력도 가능하게 할 수 있다.

그럼 앞서 보인 ExpressionTree.c의 ShowInfixTypeExp 함수를 수정하여 소괄호를 포함하는 중위 표기법의 수식을 출력하기 바란다.

 

정답

void ShowInfixTypeExp(BTreeNode *bt)
{
    if (bt == NULL)
        return;

    if (bt->left != NULL || bt->right != NULL)
        printf(" ( ");

    ShowInfixTypeExp(bt->left);
    ShowNodeData(bt->data);
    ShowInfixTypeExp(bt->right);

    if (bt->left != NULL || bt->right != NULL)
        printf(" ) ");
}