2002년 가을학기 문제해결기법 - 문제 1

피연산자

한국대학교 노 상국 교수는 식에서 피연산자를 얻어내기 위한 함수 op(i,e)를 고안하였다. 식은 우선순위가 가장 낮은 연산자에 의해서 부분식으로 나누어진다. 예를 들면, 식 e가 "a*b+b*c+c*d"라면 연산자 "+"가 가장 우선순위가 낮기 때문에, 세 개의 부분식 "a*b", "b*c", 그리고 "c*d"로 나뉘어 진다. 이 함수의 목적은 i번째 부분식을 얻는 것이다. 따라서 위의 예에서 op(2,e)=b*c이다.

부분식을 다시 원래의 식이라고 간주하면 그것을 다시 나눌 수 있다. 식 p를 "a^b*c+(d*c)^f*z+b"라고 할 때, 아래의 예를 참조하시오.

op(1,op(1,op(2,p)))=(d*c)

op(1,op(1,op(1,op(2,p))))=d*c

op(2,op(2,p))=z

op(3,p)=b

op(1,op(3,p))=b

식이 주어질 때, 노 상국 교수가 고안한 함수를 계산하는 프로그램을 작성하는 것이 문제이다. 식에서 연산자는 "+", "(", ")", "*", 그리고 "^"이 전부이다. 여기서 기호 "^"는 지수를 나타낸다. 즉, "2^3"은 2의 3승을 말한다. 예를 들면 "a^b*c+(d*c)^f*z+b"는 유효한 식이다. 연산자 중에는 괄호가 가장 우선순위가 높고, 그 다음은 지수, 곱셈, 덧셈을 나타내는 연산자 순서이다.

프로그램명은 operand.xxx라고 하고 실행 파일명은 operand.exe로 한다. 프로그램의 실행 시간은 2초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 입력 파일의 첫째 줄에 식이 주어진다. 먼저 식 이름, ":=" 기호, 뒤를 이어 식의 내용이 나온다. 식 이름과 피연산자는 모두 영문 소문자 한자로 나타낸다. 식에 나타나는 피연사자의 수는 100개 이하라고 가정해도 좋다. 둘째 줄에는 계산해야할 함수의 수 n(이 입력된다. 셋째 줄부터 n개의 줄에 한 줄에 함수 하나씩 입력되는데, 함수를 입력하기 위해서 정수만 입력된다. 예를 들어 "2 1 1"은 함수 op(1,op(1,op(2,e)))을 나타낸다. 이 함수를 계산하기 위해서는 먼저 맨 앞의 2를 보고 2번째 부분수식을 찾는다. 다음 1을 보고, 그 부분수식을 다시 분할하여 1번째 부분수식을 찾고, 다시 분할하여 첫 번째 부분수식을 찾는다. 함수를 나타내는 숫자 사이에 공백이 하나 혹은 그 이상 있다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 입력파일에 주어진 각 함수를 계산하여 순서대로 한 줄에 하나씩 출력한다. 이때 계산할 함수와 그 값을 모두 나타낸다.

입력과 출력의 예

INPUT.TXT

p:=a^b*c+(d*c)^f*z+b

4

2 1 1

2 2

3

3 1

OUTPUT.TXT

op(1,op(1,op(2,p)))=(d*c)

op(2,op(2,p))=z

op(3,p)=b

op(1,op(3,p))=b