구문 트리 해석하기

프로그램을 효율적으로 평가하려고 언어 처리기는 프로그램을 구문 트리로 바꾸는 경우가 많다. 이 문제에서는 ASCII 문자로 표현된 수식의 구문 트리가 주어진다. 이 수식의 값을 계산하라.

이 문제에서 다루는 구문 트리는 각 노드의 자식이 0개 또는 2개인 루트 있는 이진 트리이다. 자식이 0개인 노드는 0 이상 9 이하의 정수 하나에 대응하는 정수 노드이다. 자식이 2개인 노드는 덧셈, 뺄셈, 곱셈 중 하나의 이항 연산에 대응하는 연산 노드이다. 왼쪽 자식과 오른쪽 자식은 각각 왼쪽 피연산자와 오른쪽 피연산자에 대응한다. 예를 들어 그림 B.1은 $(9-4) \* ((7\*2)+5)$의 구문 트리를 나타낸다.

그림 B.1: 구문 트리의 예

이 구문 트리를 ASCII 문자로 나타내려고 $W$개 문자로 이루어진 문자열 $H$개가 주어진다. 각 문자는 '+', '-', '*', '0'부터 '9'까지의 숫자, 또는 빈칸을 뜻하는 마침표 중 하나이다. 그림 B.1의 구문 트리는 다음과 같이 표현된다.

...*.....
.-.....+.
9.4..*..5
....7.2..

그림 B.2는 이 표현의 규칙을 보여준다.

그림 B.2: 구문 트리 표현의 규칙

• 셀은 정수 노드나 이항 연산 노드 하나에 대응하는 직사각형 문자 영역이다.
• 정수 노드의 셀은 그 숫자 하나만 담는다. 높이와 너비는 모두 1이다.
• 이항 연산 노드 $v$에 대응하는 셀 $c$는 연산자 하나와 두 자식 셀을 담는다. 왼쪽 자식 $v_1$과 오른쪽 자식 $v_2$에 대응하는 셀을 각각 $c_1$, $c_2$라 하자. $c$의 높이는 $\max(h_1, h_2) + 1$이고, 너비는 $w_1 + w_2 + 1$이다. 여기서 $h_1$, $h_2$는 각각 $c_1$, $c_2$의 높이이고, $w_1$, $w_2$는 각각 너비이다. $c$의 맨 윗줄은 마침표 $w_1$개, 연산자, 마침표 $w_2$개 순서로 이루어진다. $c_1$은 $c$의 2행부터 $h_1+1$행, 1열부터 $w_1$열에 위치한다. $c_2$는 2행부터 $h_2+1$행, $w_1+2$열부터 $w_1+w_2+1$열에 위치한다. 두 자식 셀의 높이는 다를 수 있지만 윗변은 항상 맞춰져 있다.
• 두 셀이 일부만 겹치는 경우는 없다. 겹치면 한쪽이 다른 쪽을 완전히 포함한다.
• 위 규칙으로 정해지지 않은 나머지 문자는 모두 마침표이다.
• 전체 문자 영역이 루트 셀이며, 높이는 $H$, 너비는 $W$이다.

주어진 구문 트리가 나타내는 수식의 값을 계산하라.

첫 줄에 정수 $H$와 $W$ ($1 \le H, W \le 37$)가 주어진다. 다음 $H$개 줄에는 각각 길이 $W$의 문자열이 주어진다. 각 문자는 '+', '-', '*', '0'부터 '9'까지의 숫자, 또는 마침표이다. 입력은 올바른 형식의 구문 트리를 나타냄이 보장된다.

H W
s_1
...
s_H

입력이 나타내는 수식의 계산 결과를 출력한다.