|Online Judge||Problem Set||Authors||Online Contests||User|
Most of the programming languages used in practice perform strictevaluation. When a function is called, the expressions passed in the function arguments (for instance a + b in f (a + b, 3)) are evaluated first, and the resulting values are passed to the function.
However, this is not the only way how expressions can be evaluated, and in fact, even such a mainstream language as C++ is sometimes performing lazy evaluation: the operators && and || evaluate only those arguments that are needed to determine the value of the expression.
Pal Christian is now working on a comparative study of the performance of the lazy and strict evaluation. Pal wants to evaluate in both ways a set of expressions that follow this simplified syntax:
User-defined functions are defined using the following syntax: function name arg1 . . . argN = body, where arg1 . . . argN are distinct words (up to 32 English lowercase letters), denoting the formal parameters of the function, and the body is an expression. The formal parameters can occur in the body of the function in place of constants or names. The
function name and the formal parameters are separated by a single space. There is one space on both sides of the "=". functions with zero (no) arguments are legal. Note that the formal parameters can overshadow the function names (i.e. op in definition of not in sample input overshadows the function name op), but each function must have a unique name.
The first part of the input contains (less than 1000) lines with one function definition each, followed by a single empty line. Forward references (that is, referring to functions defined later in the input) and recursion are legal.
The second part of the input contains less than 1000 test expressions. Each test expression is an expresion occupying a single line. Function names and the arguments are always separated by a single space, but there are no extra spaces around parentheses (see sample input). There is an empty line after the last expression. Expressions are to be evaluated by both the lazy and the strict evaluation.
You can assume that all function definitions and expressions are syntactically correct, and that the arithmetic built-in functions (add, sub, mult, div, rem, eq, gt) will always be called with integers only, and no division by 0 occurs. Overflows outside the 32-bit integer range are legal and do not require any special treatment (just use the value produced by C, C++, or Java operators +, -, *, /, or %). In strict evaluation, built-in functions evaluate all their arguments too. In lazy evaluation, arithmetic built-in functions always evaluate all their arguments. All lines on the
input contain no more than 255 characters including spaces.
The program should produce a table in exactly the following format:
operator lazy evaluation strict evaluationwhere each oplazy is an integer - how many times op has been executed in lazy evaluation of all expressions, and opstrict is the number of evaluations of op in strict evaluation. Just one space is allowed to seperate them. If the evaluation of a test expression does not terminate after a total of 2345 function evaluations, you can assume that it is in an infinite loop, the program should skip that expression, and do not count it into the totals (omit counting operations both in lazy and strict evaluation of this expression).
if cond truepart elsepart = (cond truepart elsepart) fact x = (facta x 1) facta x a = (if (eq x 0) a (facta (sub x 1) (mult a x))) and x y = (x y false) ident x = x two = 2 op op x = ((if (eq op 1) add sub) op x) not op = (op false true) sum n = (suma n 0) suma n a = (((gt n 1) suma false) (sub n 1) (add a n)) (true (add 1 2) (mult 1 2)) 5 true (and (gt (op (sub 2 1) 1) 5) (eq (two) (op 1 1))) (false (sub 1 2) (sum 4)) ((eq (true 1 2) (false 2 1)) (add 1 2) (sub 1 2)) (fact 3)
operator lazy_evaluation strict_evaluation add 7 8 sub 4 7 mult 0 1 div 0 0 rem 0 0
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator