一个等价性的判断的思路问题,用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问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
离散数学:验证P,Q两个逻辑表达式是否逻辑等价(C语言实现)
一、程序通过编译,并实现两个命题的各种逻辑运算 二、任意输入字符串P和Q逻辑表达式的合法性检查 三、利用真值表方法验证他们的等价性
等价类和并查集
7.2 等价类和并查集7.2.1 等价关系与等价类1、在求解实际应用问题时常会遇到等价类的问题。2、 从数学上看,等价类是一个对象(或成员)的集合,在此集合中的所有对象应满足等价关系。3、 若用符号“≡”表示集合上的等价关系,那么对于该集合中的任意对象x, y, z,下列性质成立: (1)自反性:x ≡ x (即等于自身)。 (2)对称性:若 x ≡ y, 则 y ≡
谓词逻辑之 等价关系证明
前面说到了谓词逻辑的一些等价关系: 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语言版)”栈与队列“章节迷宫求解问题的思路与实现
迷宫求解问题来源自”数据结构(C语言版)“一书第50页的例题。该例题要求在不使用递归(因为暂时还没讲到),只能通过使用诸如入栈出栈的方式获取一条可以走出迷宫的路径。     在看完文字提示后,我就没有看后面的伪代码实现了(对于我来说,本书的所有伪代码的组织就像一团乱麻,反而更加没有头绪)。在理解文字说明的基础上我试图通过独立思考解决,以下就是我的思考过程。 1.迷宫求解问题的规则有哪些?
等价类划分(三角形问题)
 任意输入3个整数作为三角形的3条边的长度,判断三角形的类型: 第一步:划分有效等价类和无效等价类 输入条件 有效等价类 无效等价类 是否能构成三角形的三条边 a>0              (1) a              (7) b>0              (2) b  
指数爆炸问题的基本思路
指数爆炸问题的基本思路
C语言OJ项目参考(2964) 查闰年
2964: 查闰年Description   大家知道如何判断某一年是否是闰年吗?这个问题可难坏了小编,小编在写一个查找m年到n年之间闰年的程序,却苦于判断闰年的函数不会写,据说 今天你有上机课,我就拿着这个问题来找你了–   闰年的条件是:能被4整除但不能被100整除,或能被400整除。#include <stdio.h> int leap_year(int n); /*声明判断闰年函数*
n皇后问题 --两种方法解决(c语言实现)
/* * n皇后问题 n个皇后两两不在一行,不在一列,不在同意对角线上 * 两种方法: 1、暴力法 2、回溯法 * @author 李政 &amp;amp;amp;lt;1244109467@qq.com&amp;amp;amp;gt; */ #include &amp;amp;amp;lt;stdio.h&amp;amp;amp;gt; #include &amp;amp;amp;lt;stdbool.h&amp;amp;amp;gt; #include &amp;amp;amp;lt;mat
【数据结构】高度平衡的二叉树
给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true  示例 2: 给定二叉树 [1,2,2,3,3,null,nu...
正则表达式的等价判定
编译原理的两个课程设计之一,关于两个正则表达式是否等价的问题。题目描述及提交地址:http://soj.me/show_problem.php?pid=1000&cid=866,大概内容如下: Description 两个正则表达式等价,是指两个表达式描述完全相同的语言,即正则表达式expr1和expr2等价,当且仅当L(expr1)=L(expr2)。编写判断两个正则表达式是否等价的程序。
c语言栈实现括号匹配
在文字处理软件或编译程序设计时,常常需要检查一个字符串或一个表达式中的括号是否相匹配? 匹配思想:从左至右扫描一个字符串(或表达式),则每个右括号将与最近遇到的那个左括号相匹配。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括号时,就将它与栈顶的左括号(如果存在)相匹配,同时从栈顶删除该左括号。 算法思想:设置一个栈,当读到左括号时,左括号进栈。当读到右括号时,则从栈中弹
[NYOJ] 02括号配对问题(c语言链栈实现)
题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=2 括号配对问题 时间限制:3000 ms  |  内存限制:65535 KB 难度:3 描述现在,有一行括号序列,请你检查这行括号是否配对。 输入第一行输入一个数N(0 输出每组输入数据的输出占一行,如果该字符串中所含的括号是配对
重言式的判别
小编今年大二,数据结构让搞个重言式的判别,感觉写得很成功,传上来给大家分享。 #include #include #define LENGTHOFDATA 50 //输入数据预计的长度 #define STACK_INIT_SIZE 100 //定义栈的初始长度 #define STACKINCREMENT 10 //当栈长度不足时的增量 char string[LE
迷宫问题——c语言栈实现
我们用一个二维数组表示迷宫的点,1能走,0不能走,用回溯法写,用一个简单一点的迷宫做事例: #define _CRT_SECURE_NO_WARNINGS 1 #include &amp;lt;assert.h&amp;gt; #include &amp;lt;stdio.h&amp;gt; #include &amp;lt;stdlib.h&amp;gt; #define N 6 //N*N的迷宫 #define length N...
C语言实现迷宫求解问题(详细思路+附源代码)
二、数据结构 1) 建立一个二维数组表示迷宫的路径(0表示通道,1表示墙壁); 2) 创建一个栈,用来存储“当前路径”,即“在搜索过程中某一时刻所在图中某个方块位置”。 1) 创建一个Int类型的二维数组intmaze[n1][n2],用来存放0和1 ; 2) 创建一个结构体用来储存数组信息(数组的横坐标X,数组的纵坐标Y,方向C) typedef struct node
主元素问题(算法)
主元素问题的绝妙算法 已知一个数组的大小,并且其中存在一个数,出现的频率大于50%,则称其为该数组的主元素。用一个算法找出这个数,要求其时间复杂度尽可能低。(这个问题貌似还是计算机专业的考研试题啊) 解法: 声明一个变量count = 0,声明一个常量size等于数组大小。 假设该数组的第一个元素a(1)为主元素,让其与a(2)进行比较,若相同,则使变量count+1,若不同,则count...
迷宫问题 C语言实现(深搜)
问题描述: 2015年05月21日 10:24:05 这是我自己出的一道题   其原型基于迷宫问题,用深搜来解决的!我就简单的说一说吧! 给定一个N * M 的迷宫!,1代表有障碍,0代表无障碍可通行的! 每个迷宫只可以有一个起始点和一个出口!,但可以0或多条通往出口的路。 程序会自动计算出有多少条通往出口的路!分别用s 来代表起点 e代表终点 约定 N,M
棋盘覆盖问题(C实现)——分治算法的思想
算法思想参考 https://www.cnblogs.com/Jason-Damon/archive/2013/06/14/3136893.html https://wenku.baidu.com/view/e331f06c336c1eb91a375d75.html C语言代码实现 #include&amp;lt;stdio.h&amp;gt; int matrix[100][100]={0}; i...
C语言解决约瑟夫问题算法
据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人
C语言实现的数独解题程序
用最暴力的递归方式在所有可能的空间中寻找数独的解法。试了一下,不管多难的数独都能在1s内找到所有答案,所以也没有采取更智能的算法进行优化,如加入人的逻辑推理算法。 这里只是把一种最笨的方法分享出来,只是感叹现在的计算机运算能力太强大了。源码如下: #include #include /*数独二维数组*/ int g_s[9][9] = {     {0,4,0,7,0,
等价类划分--三角形测试用例设计
测试用例实例--三角形用例设计 测试一个图形是不是三角形,需考虑到三角形的性质要求。除了满足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。 输入条件 有效等价类 无效等价类
C语言实现RNN项目时遇到的一些问题
#include&amp;lt;stdio.h&amp;gt; void main() {     FILE *fw=fopen(&quot;D:\\data.txt&quot;,&quot;r&quot;);     int i,j,a[4][5];     for(i=0;i&amp;lt;4;i++)         {         for(j=0;j&amp;lt;5;j++)         {             fscanf(fw,&quot;%d&quot;,&amp;a...
C语言,数组实现约瑟夫环问题(两种方法)
约瑟夫环问题:约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。   第一种方法:要求将每次出列的人的序号输出,并输出最后一个出列的人。 代码如下: //c语言用数组实现约瑟夫环 #include #incl
NFA和DFA等价性证明
广告:我的博客 每个NFA都有一个等价的DFA 证明思路(NFA转DFA的方法) 我们要证明NFA和DFA等价,因为DFA是NFA的一般化,所以NFA一定可以模拟DFA,因此我们需要做的是用DFA模拟NFA。因为NFA在当前状态读到一个字符后可以有多条路可以走,所以模拟该NFA的DFA将有2k2k2^k个状态,每个状态都是NFA状态集的幂集的一个元素。具体操作在证明过程中。 证明 ...
用C语言实现说谎问题的推理题
题目介绍:A说B说谎,B说C说谎,C说A,B都在说谎,编程说明,谁在说谎话,谁在说真话解法:#include &amp;lt;stdio.h&amp;gt; //A说B说谎,B说C说谎,C说A,B都在说谎,编程说明,谁在说谎话,谁在说真话 int main(int argc, char *argv[]) { int a,b,c; for(a=0;a&amp;lt;=1;a++) { for(b=0;b&amp;lt;=...
棋盘覆盖问题的递归解决
搭建博客第一次就写一下,自己在github上利用github page这个功能搭建博客的过程也算是一个教程吧。第一次写有什么不对的地方请大家指正啦。准备工作首先想要使用github page搭建一个博客你需要一些准备,也就是一些储备知识。你先要了解git的基本用法,这里推荐一些廖雪峰的博客,感觉写的很好很适合入门,我也是从他那里入门的。廖雪峰的git教程 然后去github的官网申请一个账号,然后我
逻辑等价判断
写一段程序,测试p和q两个逻辑表达式是否逻辑相等  用真值表判断  输入的逻辑表达式为命题逻辑表达式  输入的逻辑表达式可以为复合命题,可包含四种联接词:与,或,非,条件编写代码,接收两个命题逻辑表达式。 2 分别为每种联接词实现其真值运算。 3.从左到右计算逻辑表达式,生成真值表,判断两个逻辑表达式是否等价有一部分是参考别人的思路include include inc
数据结构 树(树与等价问题)
树 离散数学中,对等关系和等价类的定义是: 如果集合S中的关系R是自反的、对称的和传递的,则成它为一个等价关系 划分等价类需要对集合进行的操作有3个:1、构造只含有单个成员的集合,2、判断某个单元所在子集,3、归并两个互不相交的集合为一个集合 由此,需要一个包含上述3种操作的数据类型MFSet ADT MFSet{ 数据对象:若设S是MF
【C语言编程】编写一个程序解决选择问题,令k=n/2
初次看到这个题目时有点懵,能力有限,没法写出高效版,先码个高时间复杂度的(O(N^2)): #include void sort(int a[]); int main() { int a[10]={1,4,2,34,12,5,76,33,9,18}; sort(a); printf("k:%d\n",a[10/2-1]); return 0; } //冒泡排
用c语言解决闰年问题的详细解释
在用c语言解决问题时我们可能会面临很多的问题,但是没关系,在这里,问您的入门提供帮助,我们一起畅游c----这个世界最强大的语言,也是最复杂的语言!基础从这里开始,梦想在这里启航。
N皇后问题--回溯算法的经典实例
问题描述: 皇后是国际象棋中威力最大的棋子。在下面所示的棋盘上,皇后可以攻击位于箭头所覆盖位置的所有棋子。我们能不能把N个皇后放在棋盘(N×N)上,它们中的任何一个都无法攻击其余的皇后?请编写程序输出皇后的摆放方案,并找出一共有几种方法。 问题分析: 编程即是先找到问题的解决方法,然后对其编程实现。这种经典实例是回溯算法的应用。回溯算法作为五大常用算法:动态规划算法,贪婪算法,分治算
【C语言】约瑟夫环(用单向循环链表解决)
约瑟夫环:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。这里我用单向循环链表来解决这个问题。 我们先考虑几种情况: 当m=1和k=1的时候,要挨个删除链表中的结点。 在k!=1和m=1的情况下,指针必须先向后移动到k的位置,并且记住k的
linux下C语言实现读者写者(写者优先)
可以并发读,读写、写读、写写互斥,写者优先,代码已在Ubuntu11.10下编译运行通过
POJ 3984 迷宫问题 广搜迷宫解法
本题是经典的迷宫搜索问题了,使用广搜比使用深搜效率要高。 思路关键点: 1 从终点出发查找起点,这样方便记录路径 2 每次查找到下一个空格,可走方格之后,可以马上标识该格为不可走了 3 找到起点之后,马上可以返回 关键是第二点为什么会成立? 因为我们需要找最短路径,只要最先可以达到,那么就肯定是最短路径,不需要从其他方向进入了。
蓝桥杯——派遣敢死队问题—C语言
蓝桥杯比赛题目: 题目描述: G将军有一支训练有素的军队,这个军队除开G将军外,每名士兵都有一个直接上级(可能是其他士兵,也可能是G将军)。现在G将军将接受一个特别的任务,需要派遣一部分士兵(至少一个)组成一个敢死队,为了增加敢死队队员的独立性,要求如果一名士兵在敢死队中,他的直接上级不能在敢死队中。 请问,G将军有多少种派出敢死队的方法。注意,G将军也可以作为一个士兵进入敢
NPC问题概念详解
转载自  http://www.caogenit.com/caogenxueyuan/yingyongfangxiang/rengongzhineng/1165.html
【DFS】素数环问题
题意:给定一个整数,求其满足起点为1的素数环,,并把所有的素数环输出来。 类型:dfs+回溯 思路:因为起点为1,所以每次都从1开始进行深度优先搜索,设置一个数组ring,用来存放素数环的路径,当找到素数环的时候就打印环的路径。其中有一个剪枝的操作,如果给定的整数为奇数,那么肯定不存在素数环,(因为肯定存在两个奇数相邻,而奇数与奇数的和为偶数,所以一定不是素数环)所以不用进行搜索。做题的时候忘...
C语言实现大数相乘(思路+代码+运行结果)
大数相乘 思路: 1.先将字符串倒序并转换为数字 2.逐位相乘,并存入一个数组e[i+j]中 3.处理进位,并消去多余的0 4.转换并把数组e[i]反转输出 #include&amp;lt;stdio.h&amp;gt; #include&amp;lt;algorithm&amp;gt; #include&amp;lt;string.h&amp;gt; #include&amp;lt;iostream&amp;gt; using namespace std...
荷兰国旗问题-C语言实现
荷兰国旗问题 数组中的元素,小于e的排在数组左边 等于在中间 大于在右边 /* * 运行环境 win10 + vs2015 * 结果: 运行正确 * 编者: 倾斜的正弦波 */ #include &quot;stdafx.h&quot; #define Maxsize 10 int buffer[Maxsize] = {4, 3, 9, 1, 5, 6, 7, 2, 0, 11}; /* ...
迷宫问题的非递归实现
迷宫问题可以抽象为一个二维数组来求解,假设有如图示的迷宫: 解题思路: 用一个栈来存放当前人的位置的坐标,并每次测试当前位置的上、下、左、右,看哪个位置可以继续前进,可以继续前进的位置入栈,并且将人走过的位置的值赋值为2,以此来区分在测试的是时候不会往回走,直至走进死胡同的时候,将走过的位置出栈,并再测试可以前进的位置,依次循环,直至找到出口。 本例代码:#pragma once#incl
文章热词 像质量评价标准 决策树算法评价标准熵 Objective-C培训 设计制作学习 机器学习教程
相关热词 ios获取idfa server的安全控制模型是什么 sql android title搜索 学习java的问题 java学习常出现的问题