알고리즘

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

Junly_21 2021. 9. 30. 18:02

[문제] 다음의 infix notationpostfix 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의 내용을 적고 그 이유를 적으시오. , operand1자리 숫자이다.

41+4*62/-

 

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

 

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

'알고리즘' 카테고리의 다른 글

[JavaScript] N-Queen 문제 (백준9663, 프로그래머스)  (2) 2023.10.02
Heap  (0) 2021.10.28
Queue의 개념  (0) 2021.10.03