正则问题

问题描述

　　考虑一种简单的正则表达式：
　　只由 x ( ) | 组成的正则表达式。
　　小明想求出这个正则表达式能接受的最长字符串的长度。

　　例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是6。

输入格式

　　一个由x()|组成的正则表达式。输入长度不超过100，保证合法。

输出格式

　　这个正则表达式能接受的最长字符串的长度。

样例输入

((xx|xxx)x|(x|xx))xx

样例输出

数据规模和约定

　　峰值内存消耗（含虚拟机） < 256M
　　CPU消耗 < 1000ms

　　请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

　　注意：
　　main函数需要返回0;
　　只使用ANSI C/ANSI C++ 标准;
　　不要调用依赖于编译环境或操作系统的特殊函数。
　　所有依赖的函数必须明确地在源文件中 #include <xxx>
　　不能通过工程设置而省略常用头文件。

　　提交程序时，注意选择所期望的语言类型和编译器类型。

Algorithm

第一次看到这个题目就想起了当初学数据结构时的中缀表达式计算，因此也是用栈来进行操作。上图：

AC

代码并没有完全通过，实在想不到哪里出问题了。。。应该是有特殊数据？

 1 /*
 2 - 有点像表达式求值问题
 3 - 就像中缀表达式计算一样 
 4 - 快慢指针 -- 不行 
 5 - 用栈模拟了一下, 好像行...
 6 - 但是出栈之后就必须计算出栈结果然后进栈 
 7 */
 8 #include<iostream>
 9 #include<algorithm>
10 #include<string>
11 #include<cstring>
12 #include<stack>
13 
14 using namespace std;
15 // xxx|xx|x
16 
17 // 深搜隐式的应用了栈, 而广搜则利用了队列 
18 // 37% 的数据 
19 int pos = 0;
20 int DFS(string s)
21 {
22     int ret = 0;
23     static int now = 0;
24     int len = s.size();
25     while(pos != len)
26     {
27         if(s.at(pos) == '('){
28             pos++;
29             ret += DFS(s);
30         }
31         else if(s.at(pos) == ')'){
32             pos++;
33             break;
34         }
35         else if(s.at(pos) == '|'){
36             pos++;
37             ret = max(ret, now);
38             now = 0;
39         }
40         else{
41             pos++;now++;
42         }
43     }
44     return max(ret, now);
45 }
46 
47 int re(string s)
48 {
49     // 定义栈 
50     stack<char> R;
51     // 这次考虑了特殊一点的数据 
52     // xxx|xx|x 
53     // 还是只通过了 75%  
54     s = "(" + s + ")";    
55     int len = s.size();
56     int k = 0;
57     while(k != len)
58     {
59         if(s.at(k) != ')')
60             R.push(s.at(k++));
61         else{
62             string temp = "";
63             while(R.top()!='(')
64             {
65                 temp.push_back(R.top());
66                 R.pop();
67             }
68             if(!R.empty()) R.pop(); // 左括号出栈 
69             int m = 0, t = 0;
70             int l =temp.size();
71             // cout<<"temp"<<temp<<endl; 
72             for(int i=0;i<l;i++){
73                 if(temp.at(i) != '|') t++;
74                 if(i == l-1 || temp.at(i) == '|'){
75                     m = max(m, t);
76                     t = 0;
77                 }
78             }
79             for(int i=0;i<m;i++)
80                 R.push('x');
81             k++;
82         }
83     }
84     
85     return R.size();
86 }
87 
88 int main()
89 {
90     string s;
91     while(cin>>s)
92     {
93         // cout<<re(s)<<endl;
94         cout<<DFS(s)<<endl; 
95         s = "";
96     }
97     return 0;
98 }

View Code

2019-02-21

18:39:09