셀
면접 대비시간 제한1초메모리 제한1024 MB
셀 수식과 셀 참조가 주어질 때 모든 셀의 값을 계산하고, 셀 이름의 사전순으로 출력합니다.
문제
Tim은 스프레드시트를 좋아한다. 컴퓨터로 하는 일은 무엇이든 스프레드시트로 한다. 용돈 지출을 기록할 때도, 살 자동차를 고를 때도, 게임 목록을 정리할 때도 스프레드시트를 만든다. 가장 좋아하는 여자를 고를 때도 …?
안타깝게도 그의 스프레드시트 프로그램이 방금 종료되었다. 지금 당장 데이터 일부가 필요하지만, 다른 오피스 프로그램을 설치할 시간이 없다.
주어진 스프레드시트 셀들의 수식으로 모든 셀의 값을 계산하라.
식을 계산할 때는 일반적인 연산 우선순위를 따른다. 먼저 *와 /를 왼쪽에서 오른쪽으로 모두 계산하고, 그다음 +와 -를 왼쪽에서 오른쪽으로 계산한다.
식을 올바른 순서로 계산했을 때 최종 결과와 모든 중간값이 32비트 부호 있는 정수 변수에 들어간다고 가정해도 된다.
/ 연산자는 내림 정수 나눗셈이다. 피제수는 항상 0 이상이고, 제수는 항상 양수이다.
입력
첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 하나 있다.
각 테스트 케이스는 식의 개수 N을 적은 한 줄로 시작한다. 이어지는 N줄에는 CELL = EXPRESSION 형태의 셀 수식이 한 줄에 하나씩 주어진다. CELL은 셀 이름이고, EXPRESSION은 셀 이름과 연산자 +, -, *, /로 이루어진 수식이다. 셀 이름은 하나 이상의 영문자 뒤에 양의 정수가 붙은 형태이며, 길이는 5 이하이다.
각 테스트 케이스는 올바르다. 순환은 없고, 식에서 참조하는 모든 셀은 정의되어 있다.
출력
각 테스트 케이스에 대해 셀의 계산 값을 CELL = VALUE 형식으로 한 줄에 하나씩 출력한다. 행은 알파벳 순으로 정렬한다. 두 행을 비교할 때는 처음으로 다른 문자를 찾는다. 그 문자의 ASCII 값이 작은 행이 먼저 나온다.