[자료구조] 3강. 스택 - 사칙 연산식의 표현

수식의 표현 - 수식의 계산

연산자의 계산순서를 생각해야 함

A+B*C+D

　⇨ ((A+(B*C))+D)

수식의 표현 - 수식의 표기 방법

중위 표기법(infix notation): 연산자를 피연산자 사이에 표기하는 방법

　⇨ A+B

전위 표기법(prefix notation): 연산자를 피연산자 앞에 표기하는 방법

　⇨ +AB

후위 표기법(postfix notation): 연산자를 피연산자의 뒤에 표기하는 방법

　⇨ AB+

수식의 표현 - 전위 표기법

(A - ( ( B+K ) / D ))

A + B => +AB

(A - (( B+K )/D))

　⇨ (A - ( (+BK) / D ) )

　　⇨ A - ( / (+BK) D )
　　　⇨ - A (/(+BK)D)

수식의 표현 - 후위 표기법

(A - ( ( B+K ) / D ))

A + B => AB+

(A - ( ( B+K ) /D))

　⇨ (A - ( ( B K + ) / D ) )

　　⇨ A - ( (BK+) D / )

　　　⇨ A ((BK+)D/) -

수식의 표현 - 중위 표기식의 후위 표기식 변환 방법

먼저 중위 표기식을 연산자의 우선순위를 고려하여 (피연산자, 연산자, 피연산자)의 형태로 괄호로 묶어줌

각 계산뭉치를 묶고 있는 괄호 안에서 연산자를 계산뭉치의 가장 오른쪽으로 이동 시킴

각 계산뭉치를 하나의 피연산자로 고려하여 위를 반복함

괄호를 모두 제거함

수식의 표현 - 후위 표기법

(A - ( ( B+K ) / D ))

A + B => AB+

(A - ( ( B+K ) /D))

　⇨ (A - ( ( B K + ) / D ) )

　　⇨ A - ( (BK+) D / )

　　　⇨ A ((BK+)D/) -

수식의 표현 - 중위 표기식의 후위 표기식 변환 방법

( ( A - ( B / C ) ) - ( D * E ) )

　　│　│↑ ↑　 │　 │↑ ↑

　　│　└┘│　 │　 └┘│

　　└───┘　 └───┘

( ( A ( B C / ) - ) ( D E * ) - )

수식의 표현 - 후위 표기식의 계산 알고리즘

// 후위 표기식(369*+)을 계산하는 연산
element evalPostfix(char *exp) {
    int oper1, oper2, value, i=0;
    int length = strlen(exp);
    char symbol;
    top = -1;
 
    for(i=0; i<length; i++) {
        symbol = exp[i];
 
        if(symbol != ‘+’ && symbol != ‘-’ && symbol != ‘*’ && symbol != ‘/’) {
            value = symbol - ‘0’;
            push(value);
        }
        else {
            oper2 = pop( ); oper1 = pop( );
 
            switch(symbol) {
                case ‘+’ :
                    push(oper1 + oper2);
                    break;
 
                case ‘-’ :
                    push(oper1 - oper2);
                    break;
 
                case ‘*’ :
                    push(oper1 * oper2);
                    break;
 
                case ‘/’ :
                    push(oper1 / oper2);
                    break;
            }
        }
    }
    return pop( );
}

수식의 표현 - 수식이 저장된 배열과 스택의 초기 모습

 

수식의 표현

 

 

 

수식의 표현 - exp[5]의 위치를 가리키는 i 변수의 모습

 

수직의 표현 - pop(57) 결과