一个等价性的判断的思路问题,用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

0
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
等价类和并查集
7.2 等价类和并查集7.2.1 等价关系与等价类1、在求解实际应用问题时常会遇到等价类的问题。2、 从数学上看,等价类是一个对象(或成员)的集合,在此集合中的所有对象应满足等价关系。3、 若用符号“≡”表示集合上的等价关系,那么对于该集合中的任意对象x, y, z,下列性质成立: (1)自反性:x ≡ x (即等于自身)。 (2)对称性:若 x ≡ y, 则 y ≡
正则表达式的等价判定
编译原理的两个课程设计之一,关于两个正则表达式是否等价的问题。题目描述及提交地址:http://soj.me/show_problem.php?pid=1000&cid=866,大概内容如下: Description 两个正则表达式等价,是指两个表达式描述完全相同的语言,即正则表达式expr1和expr2等价,当且仅当L(expr1)=L(expr2)。编写判断两个正则表达式是否等价的程序。
离散数学:验证P,Q两个逻辑表达式是否逻辑等价(C语言实现)
一、程序通过编译,并实现两个命题的各种逻辑运算 二、任意输入字符串P和Q逻辑表达式的合法性检查 三、利用真值表方法验证他们的等价性
谓词逻辑之 等价关系证明
前面说到了谓词逻辑的一些等价关系: 1.(a) ┐∀xΦ⇔∃x┐Φ    (b) ┐∃xΦ⇔∀x┐Φ 2.假设x在Ψ中不是自由的,那么: (a)∀xΦ∧Ψ⇔∀x(Φ∧Ψ) (b)∀xΦ∨Ψ⇔∀x(Φ∨Ψ) (c)∃xΦ∧Ψ⇔∃x(Φ∧Ψ) (d)∃xΦ∨Ψ⇔∃x(Φ∨Ψ) (e)∀x(Ψ→Φ)⇔Ψ→∀xΦ (f) ∃x(Φ→Ψ)⇔∀xΦ→Ψ (g)∀x(Φ→Ψ)⇔∃xΦ→Ψ ...
经典题回文串(c语言描述)
题目: 字符串中查找最大回文串例:abdfdce,则输出dfd ; creade,则输出0(字符串长度&amp;lt;1000)。 思路: 1、两个for循环第一个从前往后扫,第二个从后往前扫。 for (int i = 0; i &amp;lt; len; i++) { for (int j = len - 1; j &amp;gt; i; j--) { } } 当 s[i]==s[j] 则进入第三重whi...
指数爆炸问题的基本思路
指数爆炸问题的基本思路
数据结构(C语言版)”栈与队列“章节迷宫求解问题的思路与实现
迷宫求解问题来源自”数据结构(C语言版)“一书第50页的例题。该例题要求在不使用递归(因为暂时还没讲到),只能通过使用诸如入栈出栈的方式获取一条可以走出迷宫的路径。     在看完文字提示后,我就没有看后面的伪代码实现了(对于我来说,本书的所有伪代码的组织就像一团乱麻,反而更加没有头绪)。在理解文字说明的基础上我试图通过独立思考解决,以下就是我的思考过程。 1.迷宫求解问题的规则有哪些?
C++编写二元关系等价及其商集
#include&amp;lt;iostream&amp;gt; using namespace std; #define max 100 //定位函数 int locates(char *g, char ch,int number) { int i; for(i = 0; i &amp;lt;number; i++) { if(g[i] == ch) { ...
c语言三阶幻方问题(回溯)
Problem G 三阶幻方 时限:1000ms 内存限制:10000K 总时限:3000ms 描述: 三阶幻方是最简单的幻方,又叫九宫格,是由1,2,3,4,5,6,7,8,9九个数字组成的一个三行三列的矩阵,其对角线、横行、纵向的的和都为15。 输入: 无 输出: 输出所有的满足条件的矩阵,每个数字后带一个空格,每个幻方后带一个空行。 输入样例: 无 输
判断表达式括号是否匹配,C语言堆栈实现
#include #include #include #define STACK_INIT_SIZE 100 #define STACKINCREMENT  10 typedef struct Sq{ char *base; char *top; int stacksize; }SqStack; void InitStack(SqStack *s) { s->base
重言式判别 数据结构课程设计
重言式判别 数据结构课程设计
NextDate()函数判断输入日期的下一天(C语言编写)
这是我们软件测试课中设计决策表法所涉及到的实例,书中只给出了决策表而没有给出具体的代码,于是我就利用这个决策表自己动手用C语言把NextDate()函数给写出来了~~请大家赐教~~~
验证集合内的等价关系(自反,对称,传递)
本程序验证集合内的等价关系 检验是否满足自反关系 检验是否满足对称关系 检验是否满足传递关系
等价类划分--三角形测试用例设计
测试用例实例--三角形用例设计 测试一个图形是不是三角形,需考虑到三角形的性质要求。除了满足A B C均是整数且大于0,还需满足 A>0,B>0,C>0,且A+B>C,B+C>A,A+C>B。 如果是等腰的,还要判断A=B,或B=C,或A=C。 如果是等边的,则需判断是否A=B,且B=C,且A=C。 输入条件 有效等价类 无效等价类
主元素问题(算法)
主元素问题的绝妙算法 已知一个数组的大小,并且其中存在一个数,出现的频率大于50%,则称其为该数组的主元素。用一个算法找出这个数,要求其时间复杂度尽可能低。(这个问题貌似还是计算机专业的考研试题啊) 解法: 声明一个变量count = 0,声明一个常量size等于数组大小。 假设该数组的第一个元素a(1)为主元素,让其与a(2)进行比较,若相同,则使变量count+1,若不同,则count...
欧拉回路 (模板题,判断是否存在欧拉回路)
N - 欧拉回路   思路:使用并查集+degree处理,用并查集寻找每个连通分量的根节点,degree用来记录每个节点的度,注意无向图欧拉回路存在的条件是度全为偶数!! 代码: #include #include #include #include #include #include #include #include #define ll lon
1237: 华科版C语言程序设计教程(第二版)习题6.14
1237: 华科版C语言程序设计教程(第二版)习题6.14 时间限制: 1 Sec  内存限制: 128 MB [提交][状态][讨论版] Problem Description  输入一个八进制的字符串,将它转换成等价的十进制字符串,用pringf的%s格式输出。 输入  首先输入一个正整数t,表示有t组测试数据(1 接下来t行,每行一个字符串,表示一个八进制整数
算法课笔记系列(八)——NP问题及其计算复杂性
本周的内容是NP问题,NP的全称是Non-deterministic Polynomial,即多项式复杂程度的非确定性问题。百度上对NP的解释是,P/NP问题是在理论信息学中计算复杂度理论里至今没有解决的问题。通俗的说,是将不可知的问题转化为已知的问题,进而计算器复杂度。 首先介绍多项式时间的约减,即Polynomial-Time Reductions,通过解决另一个不同问题的假设的子程序,使用
三角形等价类划分
题目:一个程序读入三个整数,把这三个整数值看作一个三角形的三条边的长度值。这个程序要打印信息,说明这个三角形是一般三角形、等腰三角形、等边三角形、直角三角形、锐角三角形、钝角三角形。 针对上题进行等价类划分 条件 有效等价类 无效等价类
蛮力法之最近对问题(C实现)
#include #include /* 我们可以避免求平方根,窍门是忽略平方根函数,而只比较(x[i]-x[j])^2+(y[i]-y[j])^2的值本身。 */ int BruteForceClosestPoints(int n) { int d=1000, i, j, t, x[100], y[100]; for (i= 1; i < n + 1; i++) { pr
C语言实现迷宫求解问题(详细思路+附源代码)
二、数据结构 1) 建立一个二维数组表示迷宫的路径(0表示通道,1表示墙壁); 2) 创建一个栈,用来存储“当前路径”,即“在搜索过程中某一时刻所在图中某个方块位置”。 1) 创建一个Int类型的二维数组intmaze[n1][n2],用来存放0和1 ; 2) 创建一个结构体用来储存数组信息(数组的横坐标X,数组的纵坐标Y,方向C) typedef struct node
二进制问题解题思路
注:部分内容直接来自:MoreWindows博客:http://blog.csdn.net/MoreWindows,另外还有根据《剑指offer》添加的内容 一:基础知识 基本的位操作符有与、或、异或、取反、左移、右移这6种,它们的运算规则如下所示: 符号  描述  运算规则                        by MoreWind
砝码组合问题用c语言实现
5个砝码 用天平称重时,我们希望用尽可能少的砝码组合称出尽可能多的重量。 如果只有5个砝码,重量分别是1,3,9,27,81。则它们可以组合称出1到121之间任意整数重量(砝码允许放在左右两个盘中)。 本题目要求编程实现:对用户给定的重量,给出砝码组合方案。 例如: 用户输入: 5 程序输出: 9-3-1 用户输入: 19 程序输出: 27-9+1 要求程序输出的组合总是大数在前小数在后。 可以假设用户的输入的数字符合范围1~121。
C语言 3n+1问题
猜想: 对于任意大于1的自然数n,若n为奇数,则将n变为3n+1,否则变为n的一半。经过若干次这样的变换,一定会使n变为1。例如,3→10→5→16→8→4→2→1。输入n,输出变换的次数。n≤109。样例输入: 3 样例输出: 7这道题很简单,只需要一个while循环即可解决:#include <stdio.h>int main() { int n, count = 0;
离散题目13 判断是否自反
Problem DescriptionDaYu平时只顾着看电影,没有学习离散,学期末快考试的时候才慌了神,因为时间不够,因此他决定只复习一个知识点,但是他发现他一个知识点都不会,因此他跑过来请你帮他解决一个问题。求一个集合是否是自反的。Input第一行输入组数T(T<10),每组的第一行输入集合元素个数m(m < 100)和对应关系个数n(n < 100),集合中元素为1,2,…,m,接下来n行每行
等价类划分(三角形问题)
 任意输入3个整数作为三角形的3条边的长度,判断三角形的类型: 第一步:划分有效等价类和无效等价类 输入条件 有效等价类 无效等价类 是否能构成三角形的三条边 a>0              (1) a              (7) b>0              (2) b  
离散数学基本等价关系
离散数学基本等价关系(1)E1:G ∨ G = GE2:G ∧ G = G(幂等律)(2)E3:G ∨ H = H ∨ GE4:G ∧ H = H ∧ G(交换律)(3)E5:G ∨ ( H ∨ S ) = ( G ∨ H ) ∨ SE6:G ∧ ( H ∧ S ) = ( G ∧ H ) ∧ S(结合律)(4)E7:G ∨ 0 = GE8:G ∧ 1 = G(同一律)(5)E9:G ∨ 1 = ...
约瑟夫问题解决及实现代码(C语言版)
约瑟夫问题: 据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从,Josephus要他
NPC问题概念详解
转载自  http://www.caogenit.com/caogenxueyuan/yingyongfangxiang/rengongzhineng/1165.html
[NYOJ] 02括号配对问题(c语言链栈实现)
题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=2 括号配对问题 时间限制:3000 ms  |  内存限制:65535 KB 难度:3 描述现在,有一行括号序列,请你检查这行括号是否配对。 输入第一行输入一个数N(0 输出每组输入数据的输出占一行,如果该字符串中所含的括号是配对
C语言中的数独问题(回溯)
描述: 数独游戏规则 在9阶方阵中,包含了81个小格(九列九行),其中又再分成九个小正方形(称为宫),每宫有九小格。 游戏刚开始时,盘面上有些小格已经填了数字(称为初盘),游戏者要在空白的小格中填入1到9的数字, 使得最后每行、每列、每宫都不出现重复的数字,而且每一个游戏都只有一个唯一的解答(称为终盘)。 输入: 一个9*9的矩阵,0表示该位置是空白。
(C语言)线性表的链式存储的实现
//带头结点单链表的实现 #include&amp;lt;stdio.h&amp;gt; #include&amp;lt;malloc.h&amp;gt; typedef struct LinkListNode { int data; struct LinkListNode *next; }Node,*pNode; pNode Create(void); //初始化,创建头结点 int Isempty(pNode...
带密码的约瑟夫环的解题思路
题目: 编号为1,2,…,n的n个人按顺时针方向围坐一圈,每个人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m 值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。 学完链表后面的题目,最后一题就是要求用链表实现约瑟夫环带密码的问题。 很明显建立一个循...
离散数学中等价关系的认识
等价关系的定义:设R是集合A的二元关系,若R是自反的,对称的,传递的,则称R是等价关系。由定义可知,所谓等价关系就是具有自反性,对称性和传递性的二元关系。(1)如何满足自反性?定义:设R是集合A的二元关系,若对任一x属于A,都有属于R,则R是自反的。注意,集合A中的每一个元素都自相关,且都属于R。(2)如何满足对称性?定义:设R是集合A的二元关系,若对任一对x,y属于A,每
C语言,数组实现约瑟夫环问题(两种方法)
约瑟夫环问题:约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。   第一种方法:要求将每次出列的人的序号输出,并输出最后一个出列的人。 代码如下: //c语言用数组实现约瑟夫环 #include #incl
C语言解决棋盘覆盖问题
棋盘覆盖问题是典型的利用分治法解决问题 把大问题分解成为相同性质的子问题 分治的技巧在于如何划分棋盘,使划分后的子棋盘的大小相同,并且每个子棋盘均包含一个特殊方格,从而将原问题分解为规模较小的棋盘覆盖问题。k&amp;gt;0时,可将2^k×2^k的棋盘划分为4个2^(k-1)×2^(k-1)的子棋盘,如图4.11(a)所示。这样划分后,由于原棋盘只有一个特殊方格,所以,这4个子棋盘中只有一个子棋盘包...
用C语言程序,解决数制之间的转化,超简单,告别进制的问题!
1、首先,需要先明白printf()函数的输出格式控制参数:                           %d:十进制有符号整数                           %u:十进制无符号整数                           %f:十进制浮点数                           %o:八进制数                   ...
如何测试java中对象的等价性
我们都知道,基本数据类型的比较我们一般用关系运算符 “==”以及”!=“。当然,这两个运算符也适用于所有对象,然而比较的结果却并不一定与预想的结果相符。 下面看一串代码:public class Equals { public static void main(String[] args) { Integer a1 = new Integer(12); In
C语言鞍点问题
描述 找出一个二维数组中的鞍点,即该位置上的元素在该行上最大,在该列上最小。也可能没有鞍点。输入数据 输入一个5行6列二维数组输出数据 二个表示鞍点位置的行、列号没有鞍点输出none输入示例 7 6 15 4 3 22 7 9 4 3 16 8 13 7 1 175 9 10 6 5 34 7 11 2 7 9输出示例 2 3#include &amp;lt;stdio.h&amp;gt;#include &amp;lt...
C语言实现数制转换
昨天实现了栈的初始化和压一个数据入栈这两个函数,今天添加一个判断栈是否为空以及出栈这两个函数,并且实现一个简单的数制转换的功能。 首先简单介绍一下数制转换功能,对于任意一个十进制数N,将其转换成d进制数,这里偷懒直接选用书上例子,将十进制数转换成八进制数,过程如下: N N/8 N%8 1348 168 4 168 21 0 21 2
文章热词 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型 设计制作学习
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 区块链问题 ios视频开发问题