Tientohautopheptinh

[Problem]

Create a program which converts a character string of calculation formula to a postfix expression and calculates it.

 

For example, a character string “3+(4+5)*6+7” can be converted to a postfix expression "345+6*+7+".

The calculation should yield 64.

The operators used in the formula are ‘+’ and ‘*’. Parentheses can be used in the formula. The operands are the integers between 0 ~ 9. The parentheses are always paired properly.


[Input]

The first line of the input file provides the length of the test case. The test cases are given in the next lines. Total of 10 test cases are given.


[Output]

The output file outputs the test case number following the ‘#’ symbol. It is followed by a space, and then the answer.


[Input Example]

113

(9+(5*2+1)+(3*3*7*6*9*1*7+1+8*6+6*1*1*5*2)*4*7+4*3*8*2*6+(7*8*4*5)+3+7+(2+6+5+1+7+6+7*3*(6+2)+6+6)*2+4+2*2+4*9*3)

85

(4+8+4*(8*5*(7*(6*8)+3+(6+(3+7+1*7*5*4)*3)*2*3+5)+6+7*7)*4+2+9*4+7+2*3*(7*6*1*8)+9+9)

...

 

[Output Example]

#1 672676

#2 1974171

...

#1 672676
#2 1974171
#3 12654
#4 38756
#5 4035
#6 155304
#7 6964
#8 2819
#9 24711
#10 208785
113
(9+(5*2+1)+(3*3*7*6*9*1*7+1+8*6+6*1*1*5*2)*4*7+4*3*8*2*6+(7*8*4*5)+3+7+(2+6+5+1+7+6+7*3*(6+2)+6+6)*2+4+2*2+4*9*3)
85
(4+8+4*(8*5*(7*(6*8)+3+(6+(3+7+1*7*5*4)*3)*2*3+5)+6+7*7)*4+2+9*4+7+2*3*(7*6*1*8)+9+9)
97
(9*5+7+8+6+3+9*2+1+7+4+3+9*3*1+4*(4+4*3*1+9*3+(9*5)*1*7*8+2+8+8*7+9*4*9)+(1+1*8+8*9*7+1*4*5*2*5))
89
((3*1*4+6*3+8+4+5+4+2*1+5+3*4)*1+1+(3*2*2+9+5*4*6*9+9+4+1*8+9)*4*8+9+3*7+9*6*9*5+8+3*8+1)
125
(2+(6*5+6+5+3*9+6+2+8*2+2)+6+2*2+2*5*1*2+1*8+1*(4+7*5+8+9+7+3*8*5)+(2+9+5*4*4+1+3*9*6*4*5+(5*(3+4)*9+8+7+9*2)+7+7+2)+8+2+7+5)
113
(8+8*6+3*9*8*7*6*3+5*(7*6*6+3*5+2*4*9*3+5+2+1*4)*1*7+6*8+9+3+2+8*3+8*(2+6*9+2*2*7+8*1*2+9*3+1+5)*(5*8+4*1*2*4*2))
115
(7+9*2+6+5*7+1*7*(9+8+6)*1*2+7+5*9*6*3+4*8*9*6*1*3+7*1+2+5+1*4*9+6*4+7*1*2*4*2+3+((3*4+9+7*1+7+5+3*7*1*7+8*3*8)+7))
99
(9*4+(1+5*7*8+9+1+2)+5+(6*(7+4*5*2+4+8*4+7)+9)*1*3*1+1*2*8+3+(2+9*(1*5*9+7*1+1+7+3*2))+1+3*7*8+9*6)
75
(2*2+((7+8*8*6+(6*6)*7+7*1)*5)*7+3+1*5+1*8*4+(9+6+(7*5+3+1*8*8*9+4+7+9)*3))
117
(8+6*9+2*3+4+2+(6+9+3+7*5*1+2+2+2)*9+4+6*1+6*4+7+7*2+5+2*6*(8*9*8*6+4*2)*5+5*8*3+(6+1+3+3*8*1*2*1+5+6)+1+5+4*7*1*3+1)
#include <iostream>

using namespace std;

int n;
long result;
char str[1000];

long calc(int &index){
	index++;
	long preNum, r = 0;
	bool isMul = false;
	while(str[index] != ')' && index < n){
		if(str[index] == '('){
			if(isMul) preNum *= calc(index);
			else preNum = calc(index);
		} else if(str[index] >= '0' && str[index] <= '9'){
			if(isMul){
				preNum *= (str[index] - '0');
			} else {
				preNum = str[index] - '0';
			}
		} else if(str[index] == '+'){
			isMul = false;
			r += preNum;
		} else if(str[index] == '*'){
			isMul = true;
		}
		index++;
	}
	r += preNum;
	return r;
}

int main() {
	freopen("input.txt", "r", stdin);

	for(int tc = 1; tc <= 10; tc++) {

		cin >> n;
		cin >> str;
		int index = 0;
		
		// Output
		cout << "#" << tc << " " << calc(index) << endl;
	}

	return 0;
}