Tientohautopheptinh
quoc14
c_cpp
18 days ago
3.1 kB
2
Indexable
Never
ArrayString
[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; }
Leave a Comment