Pro.ID21014 TitleIt's Logical Title链接http://10.20.2.8/oj/exercise/problem?problem_id=21014 AC0 Submit0 Ratio- 时间&空间限制描述At the University of Kentucky, they build a lot of high-performance computer hardware and software, often using one supercomputer to design the next. One of the most fundamental computer design problems is logic optimization: making sure that the optimized logic still computes the same function as the original design. For this problem, your program will be given two logic expressions to compare for logical equivalence. 输入The first line of the input consists of a positive integer n, which is the number of datasets (lines) that follow. Each dataset consists of a single line containing the two input expressions to be tested. The input expressions consist of any of 26 variables named a-z, the binary operators |, &, ^, (OR, AND and XOR respectively), the unary ~ (NOT),and parenthesis. The expressions should be evaluated ignoring all other characters and with operator precedence as in the C language (parenthesis, ~, &, ^, |). The two expressions will be input in sequence and it is up to your program to determine where one expression ends and the next begins. Most logic manipulation programs would convert each expression into a normal form and check if the two normalized expressions are identical. Fortunately for you, each expression will consist of no more than 100 operations using no more than 10 different variables. For that many cases, you can test for equivalence by simply evaluating the two input expressions for all possible inputs and comparing the results. 输出Description At the University of Kentucky, they build a lot of high-performance computer hardware and software, often using one supercomputer to design the next. One of the most fundamental computer design problems is logic optimization: making sure that the optimized logic still computes the same function as the original design. For this problem, your program will be given two logic expressions to compare for logical equivalence. Input The first line of the input consists of a positive integer n, which is the number of datasets (lines) that follow. Each dataset consists of a single line containing the two input expressions to be tested. The input expressions consist of any of 26 variables named a-z, the binary operators |, &, ^, (OR, AND and XOR respectively), the unary ~ (NOT),and parenthesis. The expressions should be evaluated ignoring all other characters and with operator precedence as in the C language (parenthesis, ~, &, ^, |). The two expressions will be input in sequence and it is up to your program to determine where one expression ends and the next begins. Most logic manipulation programs would convert each expression into a normal form and check if the two normalized expressions are identical. Fortunately for you, each expression will consist of no more than 100 operations using no more than 10 different variables. For that many cases, you can test for equivalence by simply evaluating the two input expressions for all possible inputs and comparing the results. Output For each data set, print: Data set N: Equivalent if the expressions produce the same result, or: Data set N: Different if they produce different results. Of course N should be replaced by the data set number. Sample Input 3
a ^b&(b|a)~b^ a
a^b&(b|a)(a^(b&(b|a)))
~~~~z~~zSample Output Data set 1: Different
Data set 2: Equivalent
Data set 3: EquivalentSource 样例输入3
a ^b&(b|a)~b^ a
a^b&(b|a)(a^(b&(b|a)))
~~~~z~~z样例输出Data set 1: Different
Data set 2: Equivalent
Data set 3: Equivalent作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2024-9-21 16:46 , Processed in 0.014952 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
