다음과 같이 중위 표기법(infix notation)으로 되어 있는 수… | [7급 국가직 자료구조론] 19년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 19년 1회차
다음과 같이 중위 표기법(infix notation)으로 되어 있는 수식을 후위 표기법(postfix notation)으로 변환하기 위해 스택을 이용한다. 변환 과정에서 스택에 토큰이 가장 많이 쌓여 있을 때의 스택 내 연산자 토큰 수는?
a*(b-c*d)/e
1
3개
2
4개
3
5개
4
6개
해설

스택에 가장 많이 쌓일 때 토큰 수는 4개이다.

a 출력 → * 삽입 → ( 삽입 → b 출력 → - 삽입 → c 출력 순으로 진행된다.
이어 *는 스택 top의 -보다 우선순위가 높아 그대로 쌓이므로 스택은 *, (, -, *로 최대가 되며, 여는 괄호도 스택 토큰으로 센다.

이후 ) 에서 *와 -가 꺼내지고 ( 가 제거되며, / 는 같은 우선순위의 *를 꺼낸 뒤 들어가므로 다시 4개에 이르지 않는다. 변환 결과는 a b c d * - * e / 이다.

  • 3개는 여는 괄호를 빼고 연산자만 센 값이다.
  • 5개는 피연산자가 스택을 거치지 않고 바로 출력된다는 점을 놓친 값이다.
  • 6개도 같은 이유로 스택에 실제로 쌓이는 토큰 수를 넘는다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 19년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기