전위 표기법을 후위 표기법으로 바꾸기

Write a C function that transforms a prefix expression into a postfix one. Carefully state any assumptions you make regarding the input. How much time and space does your function take?

전위표기법의 식을 후위표기법으로 변환하는 함수를 작성하는 문제이다. 이 문제를 해결하기 위해서 입력에 대한 몇 가지 가정을 하였다.

식의 입력은 문자열로 한다.
입력되는 식은 모두 표현될 수 있는 전위표기법의 식이다. 잘못된 식인 경우 오류가 발생한다. (제대로 실행이 안되며, 전위표기법인지 확인하는 예외처리 매커니즘이 필요하다)
입력되는 식의 길이가 80이하로 가정한다.
연산자를 제외한 모든 문자는 피연산자로 간주한다. (_ ^ 등도 피연산자)

이 문제를 해결하는 방법에 대해 생각해 보았다.

중위표기법으로 변형했다가 다시 후위표기법으로 변형한다.
트리를 이용한다.
스택을 이용한다.
재귀 함수를 이용한다.

첫번째와 두번째경우 중간과정을 거치는 것 해법이므로, 일단 전위표기법을 한 번에 후위표기법으로 만드는 함수를 구현하기로 한다. 세번쨰와 네번째의 기본적인 과정은 똑같다. 연산자가 단 한 개인 전위표기법을 후위표기법으로 바꾸는 것은 매우 쉽다.

operator operand1 operand2   (prefix expression)
operand1 operand2 operator   (postfix expression)

이렇게 간단한 식은 변형하기가 매우 쉽다. 연산자가 매우 많은 복잡한 식도 이 기본적인 룰을 이용하면 고칠 수 있다. 복잡한 식도 기본적으로는 이 하나의 룰로 변형이 되기 때문이다. 이 방법을 이용해 재귀적으로 문제를 쉽게 풀 수 있다.

#define TRUE 1
#define FALSE 0

#include &amp;lt;stdio.h&amp;gt;
#include &amp;lt;string.h&amp;gt;

char *PreToPostFix(char *, char *);
int isoperator(char );

char *PreToPostFix(char *Pre, char *Post)
{
    int index; // operand1과 operand2의 사이를 가르키는 index
    int NumOperator=0; // 피연산자를 구분할 때 쓰이는 연산자 갯수 카운터
    int NumOperand=0; // 피연산자를 구분할 때 쓰이는 피연산자 갯수 카운터

    int PreLen = strlen(Pre); // 주어진 prifix expression의 길이

    char Operator[2]; // 연산자를 저장할 문자열
    char operand1[80]; // 피연산자1을 저장할 문자열
    char operand2[80]; // 피연산자2를 저장할 문자열
    if(PreLen == 1) { // 길이가 1인 경우에 자기자신을 return
        strcpy(Post, Pre);
        return Post;
    }

    *operand1 = '\0'; // string.h 함수를 이용하기위해 초기화
    *operand2 = '\0';                    

    *Operator        = *Pre; // operator를 얻는다
    *(Operator+1)    = '\0';

    for(index=1; index&amp;lt;PreLen; index++) // 피연산자1과 피연산자 2를 구분하기 위한 index 찾기
    {
        if(isoperator(Pre[index]))
            NumOperator++;
        else
            NumOperand++;

        if(NumOperator +1 == NumOperand)
            break;
    }

    strncat(operand1, Pre+1, index); // 피연산자1과 피연산자2를 각각 변수에 대입
    strcat(operand2, Pre+index+1);

    PreToPostFix(operand1, operand1); // 재귀적으로 각 연산자의 postfix형을 구한다.
    PreToPostFix(operand2, operand2);

    strcpy(Post, strcat(strcat(operand1, operand2), Operator));    //결과값을 구한다.

    return Post; // 결과값 return
}

int isoperator(char ch) // 피연산자와 연산자를 구별하기 위한 함수
{
    return (ch == '*' || ch == '/' || ch == '+' || ch == '-' || ch == '%');
}

이 소스 코드에 대한 Space complexity와 Time complexity를 구해본다. 이 소스에서 함수가 한번 실행되는데 필요한 메모리 공간은 다음과 같다.

변수	바이트
char *Pre	4
char *Post	4
int index	4
int NumberOperator	4
int NumberOpreand	4
int PreLen	4
char Operator[2]	2
char operand1[80]	80
char operand2[80]	80
return adresss	4
총 바이트 수	190

길이가 n인 prefix 로 표현된 식을 입력받았을 때 recursive로 호출되는 함수의 개수는 n-1 이므로, 공간복잡도는 190*(n-1) 이다.

시간복잡도는 가장 최악의 경우 **abcdefgef 와 같이 operand1이 최대로 길때이다. 이유는, 함수내 operand1과 operand2를 구별할 때 for문이 가장 오래 돌기 때문이다. 그 외의 stirng.h의 함수의 경우, 길이가 n정도 되는 문자열을 쭉 읽으면서 처리하는 것이기 때문에 O(n)이다. 따라서 함수를 쭉 한번 읽는 것의 최대차항 계수는 ‘Cn + …’ (C는 상수) 로 나타내 수 있다. 그런데 함수를 재귀적으로 n-1 번 호출하기 때문에, 단계의 수는 대략 (Cn + …)(n-1) 가 됨을 알 수 있다. 따라서 이 함수의 시간 복잡도는 O(n2)가 된다.

그 외에 스택을 이용하여 구현할 수 있는 방법은 어렵지 않게 생각 할 수 있다.

전위 표기법을 후위 표기법으로 바꾸기 - recursive

Recent Posts