후위표기식 변환 및 계산

음..
컴퓨팅 언어를 배우다보면 사칙연산 프로그램을 많이 만들어 보게된다.
(특히 조건분기문을 공부하기 위해서 말이죠)
 
그런데 이런 간단한 사칙연산 프로그램은 연산자가 여럿 쓰인 수식에는 적합하지 않다.
예를들어 (1+2*3)/4-5  같은 수식을 계산하려 한다면 사람이직접 연산자의 우선순위를 고려해서
2*3 입력 -> 1+ (2*3의 결과) -> ....   이렇게 나누어서 입력해줘야 한다.

그렇담 이런 수식을 한번에 계산해주도록 할 순 없을까?

라는 생각중에 나타난 것이 후위표기식(Postfix notation)에 관한 알고리즘들이다.

일단 후위표기식이 뭔지부터 보자.
1+2*3   이건 인간세상에서 많이 접하는 일반적인 수식이고 결과는 7이다.
그렇다면..  1 2 3 * +  이건??
이상하게 생겼지만 이놈의 결과또한 7이다.

이렇게 연산자들이 피연산자의 뒤에 위치하는 수식을 후위표기식이라고 한다.
(우리가 늘 쓰는 첫번째 수식같은 경우는 중위표기식(infix notation)이라고 함.  전위표기식(prefix notation)이라는 것도 있다)

왜 이런 알아먹기 힘든 식으로 만들어놓느냐 한다면, 컴퓨터의 입장에서 보면 중위표기식보단 후위(또는 전위)표기식이 계산하기 더 쉽기때문이다.
(컴퓨터의 입장이라곤 해놨지만, 실상은 컴퓨터 프로그래머의 입장이 더 맞는거같다..)

그렇다면 어떤 규칙을 가지고 중위표기식을 후위표기식으로 만들어놓을까?
이런 고민끝에 에드거 다익스트라(Edsger Dijkstra) 라는 위대한 수학자(이자 프로그래머)가 후위표기법 변환 알고리즘을 고안해내었다.

그 과정을 적어보면,
1. 중위표기식에서 토큰을 읽어
2. 피연산자라면 결과에 출력하고, 
3. 연산자라면,

스택 최상위 노드의 연산자부터 자기보다 낮은 우선순위의 연산자를 만날때까지 팝하여 출력한 후 자신을 푸쉬한다.
(즉, 현제 연산자보다 스택의 연산자의 우선순위가 높거나 같으면 팝하여 출력하며 이를 반복한는것)
(왼쪽괄호는 우선순위가 가장 낮지만, 예외적으로 무조건 스택에 삽입한다)

4. 오른쪽 괄호라면 최상위 노드부터 왼쪽괄호가 나올때 까지 팝 하면서 결과에 출력한다.
   (왼쪽괄호는 제거하고 출력하지 않습니다.)
5. 더 읽을것이 없을때까지 반복한다.

의 다섯가지 과정으로 적을 수 있다.
이런 과정을 거치면 중위식이 후위식으로 변하며, 괄호도 사라지게 된다.(이것또한 후위식의 장점이라고도 할 수 있다.) 

예를 들어서 중위표기식인 (1+2*3)/5 을 후위식으로 바꿔보자
(단계마다 하나의 과정씩 순차적으로 적었으니 이해하긴 어렵지 않을것같다.)

출력                                              스택

                                                                (
1                                                              (
1                                                              ( +
1 2                                                            ( +
1 2                                                            ( + * 
1 2 3                                                         ( + * 
                   (오른쪽 괄호를 만남)
1 2 3 *                                                       ( + 
1 2 3 * +                                                     ( 
1 2 3 * +                                                    
1 2 3 * +                                                     /
1 2 3 * + 5                                                  / 
1 2 3 * + 5 / (최종 결과)

과정을 따라 해보면 별로 어렵지 않다.

두번째로 이렇게 변환된 후위식을 가지고 계산을 진행하면 결과를 얻을 수 있다.
후위식의 계산과정은 변환알고리즘보단 간단하다.
1. 후위표기식에서 토큰을 읽어
2. 피연산자라면 스택에 삽입하고
3. 연산자라면 스택에서 2회 팝하여 그 피연사자들을 연산자와 함께 계산한 후 결과를 스택에 다시 삽입한다.
4. 읽을거리가 더 없으면 마지막에 스택에 있는 요소가 수식의 계산결과이다.

마지막으로 위에 과정들을 토대로 후위식 변환 및 계산프로그램을 짜봤다.
위에있는 과정은 스택을 사용하는데 지난번에 만들어놓은 리스트스택을 쓰겠다.
그리고 후위식으로 만들어진 결과하나하나를 후위식 계산에 편리하게 링크드리스트에 연결시켰다
(굳이 리스트가 필요한건 아니지만, 중위식 -> 후위식 -> 계산 할 때 계속 토큰끊어가며 하는게 싫어서 그랬을 뿐)

아래 코드는 핵심이 되는 몇개 함수만 올려놓았다.

//스택과 링크드리스트소스 인클루드

class PostfixCalc

{
private: 

        enum SYMBOL{...};

typedef struct tagDataInfo

{

...

} Datainfo;

char* infixExpression;

char* postfixExpression;

ListStack LS;

LinkedList LL_Postfix;

public:
        PostfixCalc(); 

bool isNumber(char Cipher);

int getPrecedence(char* oper);

       
        bool getToken(char* Token, SYMBOL* Type)

{

if(infixExpression == NULL)

return false;

static unsigned int index = 0;

static char* tmpInfixStr = new char[strlen(infixExpression)+1];

if(index == 0)

strcpy(tmpInfixStr, infixExpression);

if(index == strlen(tmpInfixStr))

{

*Type = ENDOFEXPRESSION;

return true;

}

for(int i=0; index<strlen(tmpInfixStr); i++)

{

if( isNumber(tmpInfixStr[index]) )

{

Token[i] = tmpInfixStr[index];

*Type = PostfixCalc::OPERAND;

if( !isNumber(tmpInfixStr[++index]))

break;

}

else

{

*Type = (SYMBOL)tmpInfixStr[index];

index++;

break;

}

}

return true;

}

bool ConvertToPostfixAndPushToStack()

{

SYMBOL Type;

char Token[64] = {0,};

char tmpPostfixStr[512] = {0,};

char* chTmpChar;

double dTmpDouble = 0;

Datainfo* tmpDinfo = NULL;

memset((void*)tmpPostfixStr, '\0', 512);

while(true)

{

if(!getToken(Token, &Type) )

return false;

switch(Type)

{

case SPACE:

break;

case OPERAND:

strncat(tmpPostfixStr, Token, strlen(Token));

strncat(tmpPostfixStr, " ",1);

tmpDinfo = new Datainfo;

dTmpDouble = atof(Token); //이 부분에서, atof가 실패한 경우라면 상당히 곤란해진다는 점을 유의할 것!

tmpDinfo->dOperand = dTmpDouble;

tmpDinfo->isOperand = true;

tmpDinfo->chOperator = 0;

LL_Postfix.addNode((void*)tmpDinfo);

break;

case LEFT_PARENTHESIS:

chTmpChar = new char;

*chTmpChar = (char)Type;

LS.PushToListStack((void*)chTmpChar );

break;

case PLUS:

case MINUS:

case MULTIPLY:

case DIVIDE:

chTmpChar = new char;

*chTmpChar = (char)Type;

while( !LS.isEmpty() && ( getPrecedence(chTmpChar) >= getPrecedence( (char*)(LS.TopData())) ) )

{

char *chTmpChar2 = (char*)(LS.PopFromListStack());

tmpDinfo = new Datainfo;

tmpDinfo->chOperator = *chTmpChar2;

tmpDinfo->isOperand = false;

tmpDinfo->dOperand = 0;

strncat(tmpPostfixStr, chTmpChar2, 1);

strncat(tmpPostfixStr," ", 1);

LL_Postfix.addNode((void*)tmpDinfo);

delete chTmpChar2;

}

LS.PushToListStack((void*)chTmpChar);

chTmpChar = NULL;

break;

case RIGHT_PARENTHESIS:

while(1)

{

if(LS.isEmpty())

{

perror("It doesn't match the Parenthesis\n");

exit(1);

}

chTmpChar = (char*)LS.PopFromListStack();

if(*chTmpChar == (char)LEFT_PARENTHESIS )

break;

tmpDinfo = new Datainfo;

tmpDinfo->chOperator =*chTmpChar;

tmpDinfo->isOperand = false;

tmpDinfo->dOperand = 0;

strncat(tmpPostfixStr, chTmpChar, 1);

strncat(tmpPostfixStr," ", 1);

LL_Postfix.addNode((void*)tmpDinfo);

delete chTmpChar;

}

break;

case ENDOFEXPRESSION:

while(LS.getCapacity() != 0)

{

chTmpChar = (char*)LS.PopFromListStack();

if(*chTmpChar == LEFT_PARENTHESIS)

{

perror("It doesn't match the parenthesis\n");

exit(0);

}

strncat(tmpPostfixStr, chTmpChar, 1);

strncat(tmpPostfixStr, " ", 1);

tmpDinfo = new Datainfo;

tmpDinfo->chOperator = *chTmpChar;

tmpDinfo->isOperand = false;

tmpDinfo->dOperand = 0;

LL_Postfix.addNode((void*)tmpDinfo);

delete chTmpChar;

}

break;

default:

return false;

}//end switch

if(Type == ENDOFEXPRESSION)

break;

memset(Token, 0x00, sizeof(Token));

}//end while

postfixExpression = new char[strlen(tmpPostfixStr)+1];

memset((void*)postfixExpression, 0x00, sizeof(postfixExpression));

strncpy(postfixExpression, tmpPostfixStr, strlen(tmpPostfixStr));

return true;

}

bool Calculate(double *result)

{

bool bTmp = ConvertToPostfixAndPushToStack();

if(!bTmp || (LL_Postfix.listLength() == 0))

return false;

//now postfixExpression is setted, and LL_Postfix is also setted//

Datainfo* tmpDinfo = NULL;

unsigned int i=0;

double *tmpOperand1, *tmpOperand2;

double* tmpResult = NULL;

if(!LS.isEmpty())

LS.deleteAll();

while(true)

{

tmpDinfo = (Datainfo*)LL_Postfix.retAt(i);

if(tmpDinfo == NULL)

break;

if( tmpDinfo->isOperand)

{

LS.PushToListStack((void*)&(tmpDinfo->dOperand));

}

else //if tmpDinfo->isOperand == false

{

tmpOperand2 = (double*)LS.PopFromListStack();

tmpOperand1 = (double*)LS.PopFromListStack();

tmpResult = new double;

*tmpResult = calc(*tmpOperand1, *tmpOperand2, tmpDinfo->chOperator);

LS.PushToListStack((void*)tmpResult);

tmpResult = NULL;

delete tmpOperand2;

delete tmpOperand1;

}

i++;

}//endl while

*result = *((double*)LS.PopFromListStack());

return true;

}

        double calc(double operand1, double operand2, char _operator);

bool printPostfixExpression();

bool printInfixExpression();

};

... 별로 효율적인 코드라고는 못하겠지만, 공부하는 입장에선 나름 볼만하다고 생각한다.

이 코드를 마무리로 이번 글은 끝