/*
1、左遞歸可以用循環(huán)來(lái)實(shí)現(xiàn)，右遞歸可以用遞歸實(shí)現(xiàn)(也可以用循環(huán)實(shí)現(xiàn),不過(guò)遞歸實(shí)現(xiàn)起來(lái)比較簡(jiǎn)單)
2、左遞歸實(shí)現(xiàn)左結(jié)合運(yùn)算，右遞歸實(shí)現(xiàn)右結(jié)合運(yùn)算
hdu 3624(網(wǎng)址： http://acm.hdu.edu.cn/showproblem.php?pid=3624 ) 的文法
exp -> addTerm | exp addOp addTerm
addOp -> + | -
addTerm -> mulTerm | addTerm mulOp mulTerm
mulOp -> * | / | %
mulTerm -> eTerm ^ mulTerm | eTerm
eTerm ->sNum | (exp)
sNum -> num | -eTerm
*/
#include <stdio.h>
#include <memory>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <cmath>
#include <set>
#include <queue>
#include <time.h>
#include <limits>
using namespace std;
#define vType long long
#define MAXLEN 2005
const int vMax = 0x7fffffff;
const int vMin = ~vMax;
#define checkVal(val) (val >= vMin && val <= vMax)
char str[MAXLEN];
int pos, cnt; //pos為當(dāng)前掃描位置，cnt為已經(jīng)分配的節(jié)點(diǎn)的數(shù)目
char ch; //ch為當(dāng)前掃描的字符
struct treeNode{
char op, flag;
vType val;
treeNode* ch[2];
void setFlag(){
if((ch[0] && !ch[0]->flag) || (ch[1] && !ch[1]->flag)){
flag = false;
}
}
}mem[MAXLEN*10];
treeNode* exp();
inline bool isDigit(char ch){
return ch >= '0' && ch <= '9';
}
inline treeNode* newNode(){
mem[cnt].flag = true;
mem[cnt].op = ' '; //op為空格表示不需要運(yùn)算
mem[cnt].ch[0] = mem[cnt].ch[1] = NULL;
return &mem[cnt++];
}
treeNode* getSyntaxTree(){
treeNode* tree;
pos = cnt = 0;
int i, j;
i = j = 0;
ch = '\n';
do{ //忽略空格
if(str[i] != ' ') str[j++] = str[i];
}while(str[i++]);
for(i = j = 0; str[i]; i++){ //加這一步是為了處理2000個(gè)(的變態(tài)數(shù)據(jù)
if(str[i] == '(') j++;
else if(str[i] == ')') j--;
}
if(j != 0){
tree = newNode();
tree->flag = false;
}else tree = exp();
return tree;
}
treeNode* eTerm(){
treeNode* t;
t = newNode();
ch = str[pos++];
if(ch == '('){
t = exp();
if(ch != ')') t->flag = false;
else ch = str[pos++];
}else if(isDigit(ch)){
vType a = ch - '0';
for(ch = str[pos++];isDigit(ch); ch = str[pos++]){
if(t->flag){
a = a * 10 + ch - '0';
}
if(!checkVal(a)){
t->flag = false;
}
}
t->val = a;
}else if(ch == '-'){
t->op = ch;
t->ch[0] = newNode();
t->ch[0]->val = 0;
t->ch[1] = eTerm();
t->setFlag();
}else t->flag = false;
return t;
}
treeNode* mulTerm(){
treeNode *t, *p, *r, *t0, *t1;;
r = t = eTerm();
p = NULL;
while(ch == '^'){ //循環(huán)實(shí)現(xiàn)右遞歸文法
t1 = newNode();
t1->op = ch;
t1->ch[0] = t;
t0 = eTerm();
t1->ch[1] = t0;
if(p){
p->ch[1] = t1;
}else r = t1;
p = t1;
t = t0;
}
return r;
}
treeNode* addTerm(){
treeNode *t, *p;
t = newNode();
t->ch[0] = mulTerm();
t->setFlag();
while(ch == '*' || ch == '/' || ch == '%'){
t->op = ch;
t->ch[1] = mulTerm();
t->setFlag();
p = t;
t = newNode();
t->ch[0] = p;
}
return t;
}
treeNode* exp(){
treeNode *t, *p;
t = newNode();
t->ch[0] = addTerm();
while(ch == '-' || ch == '+'){
t->op = ch;
t->ch[1] = addTerm();
p = t;
t = newNode();
t->ch[0] = p;
}
return t;
}
void cal(treeNode* root){
if(!root) return;
cal(root->ch[0]);
cal(root->ch[1]);
root->setFlag();
if(!root->flag) return;
if(root->op != ' '){
vType a = 0;
switch(root->op){
case '-':
a = root->ch[0]->val - root->ch[1]->val;
break;
case '+':
a = root->ch[0]->val + root->ch[1]->val;
break;
case '*':
a = root->ch[0]->val * root->ch[1]->val;
break;
case '/':
if(root->ch[1]->val == 0){
root->flag = false;
return;
}
a = root->ch[0]->val / root->ch[1]->val;
break;
case '%':
if(root->ch[1]->val == 0){
root->flag = 0;
return;
}
a = root->ch[0]->val % root->ch[1]->val;
break;
case '^':
if(root->ch[1]->val < 0 || (root->ch[0]->val == 0 && root->ch[1]->val == 0)){
root->flag = false;
return;
}
double b = pow((double)root->ch[0]->val, (double)root->ch[1]->val);
if(checkVal(b)) a = (vType)b;
else{
root->flag = false;
return;
}
break;
}
if(checkVal(a)){
root->val = a;
root->setFlag();
}else{
root->flag = false;
}
}else if(root->ch[0]){
root->flag = root->ch[0]->flag;
root->val = root->ch[0]->val;
}
}
int main(){
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
int i, c;
treeNode* root;
scanf("%d", &c);
getchar();
for(i = 1; i <= c; i++){
gets(str);
root = getSyntaxTree();
printf("Case %d: ", i);
cal(root);
if(root->flag){
printf("%I64d\n", root->val);
}
else printf("ERROR!\n");
}
return 0;
}