首页 > ACM题库 > HDU-杭电 > hdu 1947 Lazy Evaluation待解决[解题报告]C++
2013
12-26

hdu 1947 Lazy Evaluation待解决[解题报告]C++

Lazy Evaluation

问题描述 :

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 jj 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 simplied syntax:
--an expression is either a constant, a name, or a function call
--a constant is a signed 32-bit integer; for example, 3, 0, -2, 123 are constants;
--a name is a name of a built-in or user-dened function, for example, f , or add are names; names are words containing up to 32 lowercase letters from the English alphabet;
--function call has the form: ( f unction arg1 . . . argN ), where f unction is an expression that evaluates to some function of N arguments, and arg1 . . . argN are expressions that evaluate to arguments passed to the function. For example, ( f 3 5 ) , or ( add 2 ( add 1 2 )) are valid function calls.
Expressions are evaluated according to the following simple rules:
--constants evaluate to themselves
--names evaluate to the functions they denote
--function calls:
in lazy evaluation: the first expression is evaluated first to obtain a function, whose function body, with formal parameters substituted for the expressions provided as the arguments, is evaluated; however, whenever some argument gets evaluated while evaluating the function body, the resulting value will replace all occurences of the same parameter in that function body. In other words, the expression passed in the argument is never evaluated more than once.
in strict evaluation: all expressions are evaluated first: the first expression should evaluate to a function, the remaining to values that are used as function arguments; the result is the result of evaluating the corresponding function body, where all occurences of formal parameters are replaced by the values obtained by evaluating the arguments.

The following built-in functions are available: add x y – sum of the constants x and y, sub x y – returns the value x-y, mult x y – product of x and y, div x y – integer division, and rem x y – remainder (same semantics as ‘/’ and ‘%’ in C, C++ or Java), true x y – always returns x, f alse x y – always returns y , eq x y – returns true if x and y is the same constant, otherwise returns f alse, gt x y – returns true if x is greater than y, otherwise returns f alse.

User-defined functions are defined using the following syntax:
f unction 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) rguments 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 denition each, followed by a single empty line. Forward references (that is, referring to functions dened 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. Overows 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 first part of the input contains (less than 1000) lines with one function denition each, followed by a single empty line. Forward references (that is, referring to functions dened 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. Overows 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.

样例输入:

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


  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  2. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.