Problem:
Description
Your task is to judge whether the input is a legal regular expression.
A regular expression is defined as follow:
1: 0 and 1 are both regular expressions.
2: If P and Q are regular expressions, PQ is a regular expression.
3: If P is a regular expression, (P) is a regular expression.
4: If P is a regular expression, P* is a regular expression.
5: If P and Q are regular expressions, P|Q is a regular expression.
Input
The input contains multiple testcases.
Each test case is a single line with a string not containing space.The length of the string is less than 100.
Sample Input
010101101*(11|0*)*)*111
Sample Output
yesyesno
Solution:
1 #include2 #include 3 #include 4 #include 5 std::string str; 6 7 int find(std::string s) 8 { 9 std::stack _SIndex;10 int i = 0;11 while (i < s.length()) {12 if (s[i] == '(') {13 _SIndex.push(i);14 }15 else if (s[i] == ')') {16 if (_SIndex.empty())17 return -1;18 else {19 _SIndex.pop();20 }21 }22 ++i;23 }24 25 if (_SIndex.size() == 1 ) {26 return _SIndex.top();27 }28 else return -1;29 }30 31 int regular(int s, int e) 32 {33 if (e < s) return 0;34 if (s == e) return (str[s] == '0' || str[e] == '1');35 if (str[e] == '*') {36 return regular(s, e-1);37 }38 else if (str[e] == ')') {39 std::string sub = str.substr(s, e-s);40 int pos = find(sub);41 if (pos == -1) return 0;42 else {43 if (pos > 0) {44 if (str[s+pos-1] == '|') {45 return regular(s, s+pos-2) && regular(s+pos+1, e-1);46 }47 return regular(s, s+pos-1) && regular(s+pos+1, e-1);48 }49 else return regular(s+1, e-1);50 }51 }52 else {53 if (str[e] == '0' || str[e] == '1') {54 if (str[e-1] == '|') return regular(s, e-2);55 else return regular(s, e-1);56 }57 else return 0;58 }59 }60 61 62 int main()63 {64 while (1) {65 std::getline(std::cin, str);66 if (str.length()) {67 if (regular( 0, str.length()-1)) {68 std::cout << "yes" << std::endl;69 }70 else std::cout << "no" << std::endl;71 }72 else break;73 }74 }