HihoCoder - 1110 | V2AS

V2AS问路

HihoCoder - 1110

阅读原文时间：2023年07月09日阅读：1

题意：

您的任务是判断输入是否是合法的正则表达式。正则表达式定义如下:

1: 0和1都是正则表达式。

2:如果P和Q是正则表达式，那么PQ就是正则表达式。

3:如果P是正则表达式，(P)就是正则表达式。

4:如果P是正则表达式，则P*是正则表达式。

5:如果P和Q是正则表达式，则P|Q是正则表达式。

题解：

如果只有01，那么这个串肯定符合要求。所以不符合要求主要是违背了3，4，5号规则。下面分别说一下

1、对于3号规则，我们可以用栈去判断左右括号是否配对（我记得专门有这样一道题）。如果配对的话还要注意一下左右括号之间不能为空

2、对于4号规则，我们发现我们不用去管‘*’号右边的，只要‘*’号左边的满足规则就行。if((s[i]=='*' && s[i-1]=='(') || (s[i]=='*' && s[i-1]=='|')) 或者s[0]=='*',这三项种情况只要发生一个这个串就不行

3、对于5号规则if((s[i]=='|' && s[i-1]=='(') || (s[i]=='|' && s[i+1]==')'))，s[0]=='|' ， s[len-1]=='|'。这四项种情况只要发生一个这个串就不行

代码：

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 using namespace std;
11 typedef long long ll;
12 const int maxn=105;
13 const int INF=0x3f3f3f3f;
14 const double eps=1e-10;
15 stackr;
16 int main()
17 {
18 char s[maxn];
19 while(~scanf("%s",s))
20 {
21 while(!r.empty())
22 r.pop();
23 int len=strlen(s);
24 int flag=0;
25 if(s[0]=='*' || s[0]=='|' || s[len-1]=='|')
26 {
27 printf("no\n");
28 continue;
29 }
30 for(int i=0; i<len; ++i)
31 {
32 if((s[i]=='*' && s[i-1]=='(') || (s[i]=='*' && s[i-1]=='|'))
33 {
34 flag=1;
35 break;
36 }
37 if((s[i]=='|' && s[i-1]=='(') || (s[i]=='|' && s[i+1]==')'))
38 {
39 flag=1;
40 break;
41 }
42 if(s[i]=='(')
43 r.push(i);
44 else if(s[i]==')')
45 {
46 if(r.size())
47 {
48 if(i-r.top()==1)
49 {
50 flag=1;
51 break;
52 }
53 else r.pop();
54 }
55 else
56 {
57 flag=1;
58 break;
59 }
60 }
61 }
62 if(flag)
63 {
64 printf("no\n");
65 }
66 else
67 {
68 printf("yes\n");
69 }
70 }
71 return 0;
72 }

手机扫一扫

移动阅读更方便

你可能感兴趣的文章

hihocoder offer收割赛。。#1284

hihocoder 1290 DP