연습문제

※ 스스로 풀어 보세요. 해법은 따로 제공하지 않습니다.

1. 스택은 구현할 수 있는 간단한 자료 구조다. 간단한 구현은 배열을 사용하는 것이다. 배열로 스택을 구현하는 코드를 작성하라. 본문에서 스택은 5개 이상의 연산이 있다고 했는데, 스택의 크기를 반환하는 연산과 스택이 가득 찼는지 확인하는 연산이다. 이 연산을 구현해 보라.

2. 주가 스팬 문제에서 스택을 사용하는 것과 스택을 사용하지 않는 것 2가지 해법을 제시했다. 여기서는 스택을 사용하는 해법이 더 빠르다고 했는데, 2가지 알고리즘을 실제 프로그래밍 언어로 구현하고 각 해법으로 문제를 푸는 데 걸리는 시간을 측정하여 실제로 스택을 사용한 것이 더 빠른지 확인해 보라. 프로그램의 실행 시간을 측정하는 데 충분한 데이터를 입력으로 취하고 합리적인 시간에 종료하게 해야 한다. 그리고 갑자기 컴퓨터에서 많은 일을 수행하면 각 실행이 다른 요소들에 의해 영향을 받을 수 있으므로 안정적인 측정 결과를 얻을 수 있게 반복적으로 실행해야 한다. 이것은 프로그램을 어떻게 벤치마킹하는지를 살펴보고 이해할 좋은 기회가 될 것이다.

3. 스택은 후위 표기법으로도 알려진 역 폴란드 표기법(Reverse Polish Notation, RPN)으로 작성된 산술 연산을 구현하는 데 사용된다. 모든 연산자가 피연산자 사이에 위치하는 중위 표기법과 대조적으로 RPN에서는 모든 연산자가 피연산자 뒤에 온다. 그래서 ‘1 + 2’라고 쓰는 대신 ‘1 2 +’라고 쓴다. 폴란드식(Polish)은 1924년에 폴란드 표기법(전위 표기법, PN)을 발명한 루카시에비치(Jan Łukasiewicz)의 국적에서 따온 것으로, 전위 표기법에서는 ‘+ 1 2’라고 쓴다.

RPN의 장점은 괄호가 필요 없다는 것이다. 즉, 중위 표기법에서 ‘1 + (2 × 3)’은 후위 표기법에서는 “1 2 3 * +”이 된다. 평가할 때는 왼쪽에서 오른쪽으로 읽고, 스택에는 숫자를 넣는다. 연산자를 만나면 스택에서 피연산자로 사용할 아이템을 꺼내어 연산을 수행한 후 다시 스택에 결과를 넣는다. 결국 스택의 가장 위에는 유일한 하나의 원소가 결과로 남는다. 예를 들어 ‘1 2 3 * + 2 -’를 평가할 때 스택을 대괄호([ ])를 사용하여 수평적으로 작성하면 [ ], [1], [1 2 3], [1 6], [7], [7 2], [5]가 된다. 임의로 주어진 사용자 입력 산술식을 RPN으로 평가하는 계산기를 구현해 보라.

4. 많은 프로그래밍 언어에서 괄호(( )), 중괄호({ }), 대괄호([ ])와 같은 구분자를 매칭하여 수식을 설정한다. 연속한 구분자들을 읽고 구분자들이 짝을 잘 이루고 있는지, ( ( )처럼 짝이 없는 괄호나 ( }와 같이 잘못된 괄호끼리 짝을 짓고 있지 않은지 등을 검사하고 보고하는 프로그램을 작성해 보라. 현재 열린 상태인 구분자들을 기억하는 데는 스택을 사용한다.