Week 5-2 : infix to postfix, exp(postfix)

< 180508 >

1) 후위식의 계산

- 피연산자를 만나면 push

- 연산자를 만나면 스택에 담겨있는 두개의 피 연산자를 꺼낸 다음(pop) 연산 후 다시 push

int exp(const char *eq)
{
    int i;
    Stack s;
    init(&s);
 
    for(i=0; eq[i]; i++) {
        if('0' <= eq[i] && eq[i] <= '9') push(&s, eq[i]-'0');
        else {
            int op2 = pop(&s);
            int op1 = pop(&s);
            switch(eq[i]) {
            case '+': push(&s, op1+op2); break;
            case '-': push(&s, op1-op2); break;
            case '*': push(&s, op1*op2); break;
            case '/': push(&s, op1/op2); break;
            }
        }
    }
    return peek(&s);
}
 
int main()
{
    printf("%d\n", exp("234*+"));       // 14
    printf("%d\n", exp("82/3-32*+"));   // 7
    return 0;
}

>> 10 : 오른쪽 피연산자가 먼저 꺼내짐에 주의.

>> 7 : 문자열의 끝은 널문자인데, 널문자의 아스키코드값은 0. 0은 조건식에서 거짓. 즉 널물자를 만나면 for 문을 탈출한다.

2) 중위식을 후위식으로.

- 연산자 우선순위 

>> *, / : 제일 크다.

>> +, - : 두번째

>> ( : 제일 작다.

- 규칙

>> 피연산자를 만나면 그대로 출력

>> 연산자를 만나면 스택에 push.

>> 스택 위에 있는 연산자의 우선순위가 새로 추가되는 연산자의 우선순위보다 높거나 같다면 꺼내서 출력. 

    우선순위가 낮은 연산자를 만날 때 까지 반복 후 해당 연산자 push.

>> ( 가중치에 상관없이 스택에 쌓는다. 

>> ) 가 나오면 스택에서 ( 위에 쌓여 있는 모든 연산자를 출력. 그리고 ( 는 꺼내서 버린다.

- 빠르게 계산하기.

>> 후위식을 계산하는 방식에서 연산자 앞에는 두개의 피연산자가 있어야 하는 원리를 이용.

a / (b-c+d) * (e-a) * c 에서 밑줄 친 수식들이 먼저 계산이 될 것이다. 

a(_____)/ 가 될 것이며, 이 결과를 A 라고 하자. ______ 은 나중에 계산.

그렇다면 처음의 식은  A * (e-a) * c 가 되는데, 역시 여기서도 밑줄 친 수식들이 먼저 계산이 될 것이다. 

A(___)* 가 될 것이며 이 결과를 B 라고 하자.

그럼 맨 처음 식은 B * c 가 되며 이것은 후위식으로 바꾸면 Bc* 가 될 것이다.

B를 풀어쓰면 A(___)*c* 가 되고,

A를 풀어쓰면 a(_____)/(___)*c* 이 된다.

이제 나중에 계산하기로 한 b-c+d 를 생각해보자. 생각할 필요도 없다. bc-d+ 이다.

그럼 위의 식은 abc-d+/(___)*c* 가 되고, 

아직 계산하지 않은 나머지인 e-a 는 ea- 가 된다. 

최종적으로 abc-d+/ea-*c* 이 된다.

Ex2)  a + (b-c+d) * (e-a) * c 를 생각해보자.

a + (b-c+d) * (e-a) * c 에서는 a 와 밑줄친 식의 결과를 더하는 연산이 진행되어야 한다.

a(_____________)+ 의 형태가 나온 것이다.

(b-c+d) * (e-a) * c 에서는 역시 밑줄친 수식이 먼저 계산이 될 것이기 때문에

(__________)c* 라고 쓸 수 있다.

두 식을 결합하면 a(_____________)c*+ 이 되고, 

(b-c+d) * (e-a) 에서 b-c+d 의 결과를 A, e-a 의 결과를 B라고 하면 후위식으로 AB* 가 될 것이다.

역시 위의 식을 다시 결합하면  aAB*c*+ 가 되고,

A를 풀어쓰면 bc-d+, B를 풀어쓰면 ea- 가 된다.

대입하면 최종적으로 abc-d+ea-*c*+ 가 된다.

<숙제>

- 중위식을 후위식으로 바꾸는 프로그래밍.

- 중위식을 후위식으로 바꾼 다음 그 후위식을 계산하는 프로그래밍.