SG8. 伪正则表达式
描述
判断一个数字串是否匹配一个表达式，具体如下：#import <Foundation/Foundation.h>
//strcmp
//NSString:
//- (NSArray<NSString *> *)componentsSeparatedByCharactersInSet:(NSCharacterSet *)separator
//- (unichar)characterAtIndex:(NSUInteger)index;
//- (NSString *)substringWithRange:(NSRange)range;
int main(int argc, const char * argv[]) {
NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
//...
//add your code
//...
[pool drain];
return 0;
} 输入描述
见输入样例，其中最后一行的0表示结束输入输出描述
YES:匹配示例1
输入:
3 1* 11111 **1 121 **1 1221 0
输出:
YES YES NO
说明:
3表示case数有3个示例2
输入:
3 1* 11111 21* 2103 22* 22* 0
输出:
YES NO NO
说明:
3表示case数有3个C++ 解法, 执行用时: 2ms, 内存消耗: 384KB, 提交时间: 2020-10-31
#include <bits/stdc++.h>
using namespace std;
string p,t;
bool dfs(int i, int j, int cur) {
if (j == t.size()&&i == p.size())return true;
if (i == p.size())return false;
if (p[i] == t[j]) {
return dfs(i + 1, j + 1, (cur + t[j] - '0') % 10);
}else if (p[i] == '*') {
return cur == t[j] - '0' ? dfs(i, j + 1, cur % 10) || dfs(i + 1, j + 1, cur % 10) : false;
}
return false;
}
void getNum() {
if (t.size() < p.size()) {
cout << "NO" << endl;
return;
}
for (int i = 0; i < t.size(); ++i) {
if (!(t[i] >= '0'&&t[i] <= '9')) {
cout << "NO" << endl;
return;
}
}
int i = 0;
for (; i < p.size(); ++i) {
if (p[i] != '*')break;
}
t = t.substr(i);
p = p.substr(i);
if ((t == ""&&p != "") || (t != ""&&p == "")) {
cout << "NO" << endl;
return;
}
if (dfs(0, 0, 0)) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
string str;
getline(cin, str);
int n = stoi(str);
while (n--) {
getline(cin,p);
getline(cin,t);
getNum();
}
}
C++ 解法, 执行用时: 2ms, 内存消耗: 484KB, 提交时间: 2019-11-09
#include <bits/stdc++.h>
using namespace std;
string p,t;
bool dfs(int i, int j, int cur) {
if (j == t.size()&&i == p.size())return true;
if (i == p.size())return false;
if (p[i] == t[j]) {
return dfs(i + 1, j + 1, (cur + t[j] - '0') % 10);
}else if (p[i] == '*') {
return cur == t[j] - '0' ? dfs(i, j + 1, cur % 10) || dfs(i + 1, j + 1, cur % 10) : false;
}
return false;
}
void getNum() {
if (t.size() < p.size()) {
cout << "NO" << endl;
return;
}
for (int i = 0; i < t.size(); ++i) {
if (!(t[i] >= '0'&&t[i] <= '9')) {
cout << "NO" << endl;
return;
}
}
int i = 0;
for (; i < p.size(); ++i) {
if (p[i] != '*')break;
}
t = t.substr(i);
p = p.substr(i);
if ((t == ""&&p != "") || (t != ""&&p == "")) {
cout << "NO" << endl;
return;
}
if (dfs(0, 0, 0)) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
string str;
getline(cin, str);
int n = stoi(str);
while (n--) {
getline(cin,p);
getline(cin,t);
getNum();
}
}
C++ 解法, 执行用时: 2ms, 内存消耗: 524KB, 提交时间: 2020-10-31
#include <bits/stdc++.h>
using namespace std;
string p,t;
bool dfs(int i, int j, int cur) {
if (j == t.size()&&i == p.size())return true;
if (i == p.size())return false;
if (p[i] == t[j]) {
return dfs(i + 1, j + 1, (cur + t[j] - '0') % 10);
}else if (p[i] == '*') {
return cur == t[j] - '0' ? dfs(i, j + 1, cur % 10) || dfs(i + 1, j + 1, cur % 10) : false;
}
return false;
}
void getNum() {
if (t.size() < p.size()) {
cout << "NO" << endl;
return;
}
for (int i = 0; i < t.size(); ++i) {
if (!(t[i] >= '0'&&t[i] <= '9')) {
cout << "NO" << endl;
return;
}
}
int i = 0;
for (; i < p.size(); ++i) {
if (p[i] != '*')break;
}
t = t.substr(i);
p = p.substr(i);
if ((t == ""&&p != "") || (t != ""&&p == "")) {
cout << "NO" << endl;
return;
}
if (dfs(0, 0, 0)) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
string str;
getline(cin, str);
int n = stoi(str);
while (n--) {
getline(cin,p);
getline(cin,t);
getNum();
}
}
C++ 解法, 执行用时: 3ms, 内存消耗: 376KB, 提交时间: 2020-07-15
#include <iostream>
#include <string>
using namespace std;
//s为数字串,p为表达式，sum为'*'前面所有数字和
bool getP(string s, string p,int sum)
{
int m=s.length();
int n=p.length();
int i=0,j=0;
int flag=false; //‘*’是否已经匹配过
while(i<m && j<n)
{
if(s[i] >'9' || s[i] <'0') //字符串非法
return false;
if(p[j] !='*') //统计数字余数和
sum = (sum+ p[j]-'0')%10;
if(s[i] == p[j]) //正常匹配
{
i++;j++;
}
else if(p[j] == '*') //'*'匹配
{
if(j==0 ||( j>=1 && p[j-1] == '*') ) //只能匹配一个任意字符的‘*’
{
i++;
j++;
continue;
}
if(flag == true) //可匹配多个的'*'已匹配过
{
if( (sum+'0') == s[i] ) //两种选择，继续匹配或者匹配下一个
{
if( getP(s.substr(i,s.length()-i),p.substr(j+1,p.length()-j-1),sum) ==true )
return true; //成功直接返回
i++;
}
else //匹配失败，匹配下一个
{
flag=false;
j++;
}
}
else //'*'未匹配
{
if((sum+'0') == s[i]) //匹配成功
{
flag=true;
i++;
}
else //匹配失败
return false;
}
}
else
return false; //匹配失败
}
if(j>0 && p[j] =='*' && p[j-1] !='*' ) //最后剩一个匹配多个‘*’
j++;
if(i==m && j==n) //匹配完成
return true;
else
return false ;
}
int main(){
int n;
cin >> n;
string s,p;
getline(cin,p); //因为存在空串，使用getline,不用cin>>,这里把n后面的换行读取掉
while(n--)
{
getline(cin,p); //因为存在空串，使用getline,
getline(cin,s); //因为存在空串，使用getline,
bool f=getP(s,p,0);
if(f)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
cin>>n;
return 0;
}
C++ 解法, 执行用时: 3ms, 内存消耗: 380KB, 提交时间: 2020-11-01
#include <bits/stdc++.h>
using namespace std;
string p,t;
bool dfs(int i, int j, int cur) {
if (j == t.size()&&i == p.size())return true;
if (i == p.size())return false;
if (p[i] == t[j]) {
return dfs(i + 1, j + 1, (cur + t[j] - '0') % 10);
}else if (p[i] == '*') {
return cur == t[j] - '0' ? dfs(i, j + 1, cur % 10) || dfs(i + 1, j + 1, cur % 10) : false;
}
return false;
}
void getNum() {
if (t.size() < p.size()) {
cout << "NO" << endl;
return;
}
for (int i = 0; i < t.size(); ++i) {
if (!(t[i] >= '0'&&t[i] <= '9')) {
cout << "NO" << endl;
return;
}
}
int i = 0;
for (; i < p.size(); ++i) {
if (p[i] != '*')break;
}
t = t.substr(i);
p = p.substr(i);
if ((t == ""&&p != "") || (t != ""&&p == "")) {
cout << "NO" << endl;
return;
}
if (dfs(0, 0, 0)) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
string str;
getline(cin, str);
int n = stoi(str);
while (n--) {
getline(cin,p);
getline(cin,t);
getNum();
}
}