死去的编译原理开始攻击我...检查状态的时候还是那样痛苦...。用了有限自动机的方法,一遍扫描。
这是代码使用的NFA,把它转化成DFA矩阵就好了。没啥好说的。
#define PM 0
#define DOT 1
#define NUM 2
#define EXP 3
#define TERMIN 4
#define ERR -1
#define PASS -2
class Solution
{
public:
bool validNumber(string s)
{
short statu = 0, sym = ERR;
bool start = false, over = false;;
for (char ch : s)
{
//空格
if(ch == ' '){
//没开始,跳过
if(!start) continue;
//开始了但没结束,认为结束了
if(!over) over = true;
continue;
}
if(over) return false; //在认为结束之后遇到非空格,错误的
if(!start) start = true;//不是空格,如果没开始,则开始
sym = get_type(ch);
cout << ch << " " << statu << " " << sym ;
// 错误字符
if (sym == ERR)
return false;
statu = switch_matrix[statu][sym];
cout<<" switch to "<<statu << endl;
if (statu == ERR)
return false;
}
if (switch_matrix[statu][TERMIN] == PASS)
return true;
return false;
}
private:
short get_type(char x)
{
if (x == '+' || x == '-')
return PM;
if (x <= '9' && x >= '0')
return NUM;
if (x == 'e' || x == 'E')
return EXP;
if (x == '.')
return DOT;
return ERR;
}
short const switch_matrix[8][5] =
{
// P,dot,N,T
1, 2, 3, ERR, ERR,
ERR, 2, 3, ERR, ERR,
ERR, ERR, 4, ERR, ERR,
ERR, 4, 3, 5, PASS,
ERR, ERR, 4, 5, PASS,
7, ERR, 6, ERR, ERR,
ERR, ERR, 6, ERR, PASS,
ERR, ERR, 6, ERR, ERR
};
};
一开始忽略了空格,然后本来想要往往上面那张图再加blank,对,我都把DFA写出来了。(这个图改过很多遍不要在乎可能错误的细节因为我也没跑过)
然后我发现矩阵多了很没有必要的一行,只要加俩boolean就可以做到的事儿为什么要浪费内存呢。
goto矩阵看起来是稀疏的,可以考虑压缩存储。看到这里可以去复习一下矩阵压缩存储了。随便找了个->点击链接复习噢~
我死去的数据结构和分布式计算开始攻击我,疯狂被攻击!!!!!!!!呜呜呜!