注意，lz并没有参加在线笔试，只是拿来练习一下，由于在hihocoder上并不能提交，只能用样例测试，所以不保证答案完全正确
题目：http://hihocoder.com/contest/ntest2015septdev/problem/3
分析：模拟题，不过可以通过【宏定义】+【异常处理】来简化代码，风格有点pythonic，感觉还是比较优雅的
#include <cstdio>
#include <cctype>
#include <cstdlib>
#define MAX_LEN 1000005
typedef long long LL;
const int kBracketMismatch = -1;
const int kOperatorMissing = -2;
const int kOperatorMismatch = -3;
const int kError = -4;
char* SkipSpaces(char* exp) throw()
{
for(; isspace(*exp); ++exp) ;
return exp;
}
char* ParseOperand(char* exp, LL& ret) throw()//exp points to the first digit of the operand
{
LL res = 0;
char *p = exp, c;
for(; isdigit(c = *p); ++p){
res = res * 10 + c - '0';
}
ret = res;
return p;
}
char* ExpectChar(char* exp, char ch) throw(int)
{
exp = SkipSpaces(exp);
if(*exp != ch){
// printf("expect %02X, but get %02X\n", ch, *exp);
if(ch == '(' || ch == ')') throw kBracketMismatch;
throw kError;
}
return exp;
}
char* ExpectOperator(char* exp) throw(int)
{
exp = SkipSpaces(exp);
char c = *exp;
if(c != '+' && c != '-' && c != '*'){
if(c == '(' || c == ')') throw kBracketMismatch;
throw kOperatorMissing;
}
return exp;
}
/*
* @exp: pointer of the first char after '+-*'
* @ret: where to store the expression result
* @return: beyond end of the expression, which points the first char after ')'
*/
char* EvalAdd(char* exp, LL& ret) throw(int);
char* EvalSub(char* exp, LL& ret) throw(int);
char* EvalMul(char* exp, LL& ret) throw(int);
/*
* @exp: pointer of the expression, may point to leading spaces or '('
* @ret: where to store the expression result
* @return: beyond end of the expression, which points the first char after ')'
*/
char* Eval(char* exp, LL& ret) throw(int)
{
// char* old = exp;
LL res = 0;
//expression should start with '('
char* p = ExpectChar(exp, '(');
//operator should follow '('
p = ExpectOperator(p+1);
char op = *p++;
//evaluate
if(op == '+') p = EvalAdd(p, res);
else if(op == '-') p = EvalSub(p, res);
else p = EvalMul(p, res);
//store result
ret = res;
// printf("[%s] = %d\n", old, int(ret));
return p;
}
//template define
#define ImplementEvalMethod(Name, InitValue, Op, ErrorCond) \
char* Eval##Name(char* exp, LL& ret) throw(int) \
{ \
LL res = InitValue, operand; \
int cnt = 0; \
while(true){ \
exp = SkipSpaces(exp); \
char c = *exp; \
if(c == '(') exp = Eval(exp, operand); \
else if(isdigit(c)) exp = ParseOperand(exp, operand); \
else if(c == ')'){ \
++exp; \
break; \
} \
else throw kError; \
res Op operand; \
++cnt; \
} \
if(ErrorCond) throw kOperatorMismatch; \
ret = res; \
return exp; \
}
//implementations, add ';' to make it looks magic
ImplementEvalMethod(Add, 0, +=, cnt < 1);
ImplementEvalMethod(Mul, 1, *=, cnt < 2);
char* EvalSub(char* exp, LL& ret) throw(int)
{
LL res = 0, operand;
int cnt = 0;
while(true){
exp = SkipSpaces(exp);
char c = *exp;
if(c == '(') exp = Eval(exp, operand);
else if(isdigit(c)) exp = ParseOperand(exp, operand);
else if(c == ')'){
++exp;
break;
}
else throw kError;
if(++cnt) res = operand;
else res -= operand;
}
if(cnt != 1 && cnt != 2) throw kOperatorMismatch;
if(cnt == 1) res = -res;
ret = res;
return exp;
}
//where to store the input
char exp[MAX_LEN];
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int test;
scanf("%d", &test);
while(getchar() != '\n') ;
LL res;
while(test--){
gets(exp);
try{
char* p = Eval(exp, res);
ExpectChar(p, '\0');//expression should end with '\0'
printf("%d\n", int(res));
} catch(int e){
// printf("e = %d, ", e);
puts("invalid expression");
}
}
return 0;
}