Sunday, August 14, 2011

CF problem 7E

The problem gives n<=100 macro definitions and asks to check whether an expr is safe or not.

One idea is to replace all macros to get final expr and check. This runs out of time and memory as each macro might have 30+ terms and with 100 recursive substitution the resulting expr might have 30^100 terms which is simply too long.

Need to use standard parsing algorithms to do the check. Maybe it is not necessary to rewrite the left recursive grammar. watashi's idea is to evaluate all macros to
Expr: something without + - * /
Term: something with + -
Factor: something with * /
Suspicious: something already suspcious

Now keep all previous evaluated terms in a stack, as well as a stack for operators not processed so far. When hit lparen, make a recursive call and let the call return with the maching rparen. When hit a new operator, pop and evaluate all ops in stack with precedence higher or same. The code is very clean.

No comments:

Post a Comment