首页 > 试题广场 >

伪正则表达式

[编程题]伪正则表达式
  • 热度指数:1010 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
判断一个数字串是否匹配一个表达式,具体如下:
1)表达式m:一定不为空,只能由数字和“*”构成,其中的“*”表示匹配一个或多个“它前面所有非”*“的数字的和值除以10的余数”;“*”如果在最前面或其前面都是“*”,则只可以是任意一个数字。
2)数字串s:可能为空,只能由数字构成,不能包含其它字符。
3)是否匹配:匹配要求覆盖整个数字串s,而不是某一部分匹配。

解题要求:不能将m转写成标准正则表达式来解题,需要自己编程实现匹配算法。

注意,对应objc语言,系统里的@autoreleasepool {} 需要改写成如下形式
#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:匹配

NO:不匹配
示例1

输入

3
1*
11111
**1
121
**1
1221
0

输出

YES
YES
NO

说明

3表示case数有3个
case 1:1*是表达式,11111是数字串,*前面所有数字的和值除以10的余数为1,*表示匹配1个或1个以上的前面数字”1“,刚好“1111”符合匹配规则,所以,输出YES。
case 2:**1是表达式,121是数字串,第一个*在最前面,可以是任意数字,与“1”匹配;第二个“*”因为前面都是“*”,所以可以是任意一个数字,与“2”匹配。总体看,两者符合匹配规则,输出YES。
case 3:**1是表达式,1221是数字串,第一个*与“1”匹配,第二个*与“2”匹配,但只能匹配一个“2”,整体不符合匹配规则,所以,输出NO。
示例2

输入

3
1*
11111
21*
2103
22*
22*
0

输出

YES
NO
NO

说明

3表示case数有3个
case 1:1*是正则表达式,11111是数字串,两者符合匹配规则,所以,输出YES。
case 2:21*是正则表达式,2103是数字串,*前面所有数字的和值除以10的余数为3,刚好“03”并不符合匹配规则,所以,输出NO。
case 3:22*是正则表达式,22*是数字串,但是因为其中包含了*这样的非数字字符,并不符合匹配规则,所以,输出NO。
#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;
}
发表于 2019-08-30 13:48:39 回复(1)
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        //while(in.hasNext()){
            int T=Integer.parseInt(in.nextLine());
            for(int i=0;i<T;i++){
                String repre=in.nextLine();
                String numStr=in.nextLine();
                if(numStr.equals("")){
                    System.out.println("NO");
                    continue;
                }
                if(match(repre,numStr,false,0))
                    System.out.println("YES");
                else 
                    System.out.println("NO");
            }
            in.nextLine();
        //}
        
    }
    public static boolean match(String repre,String numStr,boolean flag,int remain){
        if(repre.length()>numStr.length())
            return false;
        if(repre.length()==0)
            if(numStr.length()==0)
                return true;
            else return false;
        if(!flag){
            int idx=0;
            for(;idx<repre.length()&&repre.charAt(idx)=='*';idx++){
                if(numStr.charAt(idx)>'9'||numStr.charAt(idx)<'0')
                    return false;
            }
            if(idx==repre.length()){
                if(idx==numStr.length())
                    return true;
                return false;
            }
            flag=true;
            for(;idx<repre.length()&&repre.charAt(idx)!='*';idx++){
                if(repre.charAt(idx)>='0'&&repre.charAt(idx)<='9'&&repre.charAt(idx)==numStr.charAt(idx))
                    remain=(remain+(repre.charAt(idx)-'0'))%10;
                else return false;
            }
            if(idx==repre.length()){
                if(idx==numStr.length())
                    return true;
                return false;
            }
            return match(repre.substring(idx),numStr.substring(idx),flag,remain);
        }
        if(repre.charAt(0)=='*'){
            if(numStr.charAt(0)!=(char)(remain+'0'))
                return false;
            boolean ret=match(repre.substring(1),numStr.substring(1),flag,remain);
            for(int idx=1;idx<numStr.length()&&(char)(remain+'0')==numStr.charAt(idx);idx++){
                ret=ret||match(repre.substring(1),numStr.substring(idx+1),flag,remain);
            }
            return ret;
        }
        int idx=0;
        for(;idx<repre.length()&&repre.charAt(idx)!='*';idx++){
            if(repre.charAt(idx)>='0'&&repre.charAt(idx)<='9'&&repre.charAt(idx)==numStr.charAt(idx))
                remain=(remain+(repre.charAt(idx)-'0'))%10;
            else return false;
        }
        return match(repre.substring(idx),numStr.substring(idx),flag,remain);
    }
}

//这题真恶心,后台有这样一组数据
5
1*
111211
2*1*3
2213
*22*
224444
**9**1*0*2*1*5*2***2****1*8
0199999100002221352000022222218
***7*2*1*0*2*1*5*2***2****1*8
071777299910000222135882000022221338
1*
1111
0
明明case数只有5个,却给了6组数据,最后把while(in.hasNext())注释掉才过,花了很多时间找程序的问题,最后发现是输入的问题,不知道是故意给这种错误数据还是什么意思?

发表于 2020-03-21 17:20:32 回复(0)