一个等价性的判断的思路问题,用C语言对于这个问题的实现?

Problem Description
Numeric Regular Expression (NRE) is a simple version of regular expression. It is a useful tool for numeric string matching.

If S is an NRE, we often use function L(S) to represent the set of numeric strings matched by S. Note that L(S) maybe infinite.

NRE and function L can be recursively defined by the following rules:

  1. Atom: A single digit (0,1,2,...,9) is an NRE, and L(d)={d}, where d=0,1,2,...9.

  2. Nestification: If x is an NRE, then (x) is an NRE, and L((x))=L(x).

  3. Concatenation: If x and y are NREs, then xy is an NRE, and L(xy)={ab | a∈x and b∈y}.

  4. Option: If x and y are NREs, then x|y is an NRE, and L(x|y)= L(x)∪L(y).

  5. Closure: If x is an NRE, then x* is an NRE, and L(x*)={ε, L(x),L(xx),L(xxx),...}, hereε means “empty string”. In other word, x* matches x zero or more times.

To avoid confusion, the order of operations (from high to low) is: nestification, closure, concatenation and option. Operations with higher order will be applied first, and same operations will be applied from left to right. For example,01* is equal to 0(1*), not (01)*; 00|1 is equal to (00)|1, not 0(0|1).

Now give you two NERs r1 and r2, can you tell us whether L(r1)=L(r2) or not?

Input
There are several test cases in the input.

The first line contains an integer T (1 <= T <= 50) -- the number of test cases.

Each test case contains two lines, the first line is r1 and the second line is r2 (1 <= |r1|,|r2| <= 10). It is guaranteed that both r1 and r2 are correct NREs without any useless character.

Output
For each test case, output the answer “YES” or “NO” in a single line.

Sample Input
2
(1|2)*
(2|1)*
34|2
32|4

Sample Output
YES
NO

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐