Stack예제- 후위 계산법 (Postfix)

[문제] 다음의 infix notation을 postfix notation으로 변경하고자 한다. 매 character를 읽을 때마다 stack의 내용을 적고, 그렇게 변하거나 변하지 않는 이유도 함께 적으시오.

a*(b+c/d)-e

 

a*바로 뒤에 괄호가 있다. 즉 a출력후 괄호 사이의 bcd도 바로 이어서 출력. 그 후 top부터/ + *으로 쌓여있는걸 출력해야겠지?

 

아, 중위연산을 후위연산으로 바꿀때는 연산자를 stack에 저장해야한다.

 

하여 출력값은 abcd/+*e-이다.

 

이 문제를 풀면서 괄호의 우선순위가 어느정도인지 헷갈렸다.

 

a*(b+c/d)-e가 아니라a*(b/c+d)-e 였다면 어떻게 달라지는거지?

 

큰 차이가 없다. 괄호의 닫는 부분까지는 어쨌든 push를 계속 해줘야하고, 괄호를 닫고 난 이후에 출력을 진행해야하기 때문이다.

 

 

후위연산식을 계산하는 문제도 풀어보도록 하자.

[문제] 다음의 postfix notation을 읽어서 그 값을 계산하고자 한다. 매 character를 읽을 때마다 stack의 내용을 적고 그 이유를 적으시오. 단, operand는 1자리 숫자이다.

41+4*62/-

 

후위연삭식을 계산하는 문제가 훨씬 더 쉽게 느껴진다.

 

그냥 피연산자를 냅다 때려박으면서 연산자가 나올때마다 위쪽 두개를 pop해서 연산 후 다시 push해주면 되기 때문이다.