[문제] 다음의 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해주면 되기 때문이다.
'알고리즘' 카테고리의 다른 글
[JavaScript] N-Queen 문제 (백준9663, 프로그래머스) (2) | 2023.10.02 |
---|---|
Heap (0) | 2021.10.28 |
Queue의 개념 (0) | 2021.10.03 |