다음과 같이 중위 표기법(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개도 같은 이유로 스택에 실제로 쌓이는 토큰 수를 넘는다.
오류나 개정된 내용이 보이면 알려주세요