伪正则表达式

#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;
}

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())注释掉才过，花了很多时间找程序的问题，最后发现是输入的问题，不知道是故意给这种错误数据还是什么意思？

import java.io.*;
import java.util.*;

// 字符串完全匹配：搞懂*、**的匹配规则
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (n-- > 0) {
            String m = br.readLine();
            // if (m.equals("0")) break;
            String s = br.readLine();
            if (m.isEmpty() || !m.matches("[0-9*]+") || !s.matches("[0-9]+")) {
                sb.append("NO\n"); // 输入非法
                continue;
            }
            boolean matched = dfs(m.toCharArray(), s.toCharArray(), 0, 0, 0, true);
            sb.append(matched ? "YES\n" : "NO\n");
        }
        System.out.print(sb.toString());
    }

    static boolean dfs(char[] m, char[] s, int i, int j, int mod, boolean allStar) {
        if (i == m.length || j == s.length)
            return i == m.length && j == s.length; // 必须完全匹配

        if (m[i] != '*') {
            if (m[i] != s[j]) return false;
            return dfs(m, s, i + 1, j + 1, (mod + s[j] - '0') % 10, false);
        } else {
            if (allStar) {
                // 前面都是*：匹配任意1个数字
                return dfs(m, s, i + 1, j + 1, mod, true);
            } else {
                if (mod != s[j] - '0') return false;
                // 1个*：匹配1个或多个mod
                return dfs(m, s, i, j + 1, mod, false) || dfs(m, s, i + 1, j + 1, mod, false);
            }
        }
    }
}