Chinaunix首页 | 论坛 | 博客
  • 博客访问: 104418
  • 博文数量: 41
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 407
  • 用 户 组: 普通用户
  • 注册时间: 2013-06-27 13:42
文章分类

全部博文(41)

文章存档

2016年(1)

2015年(18)

2014年(22)

我的朋友

分类: C/C++

2015-02-10 01:32:52

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.


本题5星级接近6星级的题目,本题是十分麻烦的题目,情况是非常多,网上也很多方法,其中最有效,优雅的方法是有限状态自动机(Finite automata machine)。其他一般方法都会十分复杂,而代码不能算优雅。为此我也曾经专门修了一个automata的知识。

只要设计好Finite Automata Machine之后,写程序就可以很优雅,很简单了。

但是,问题是要构造一个Finite Automata也是十分麻烦的事情,我画了一张A4纸,像蜘蛛网一样的,故此就不贴出来了,也搞了一两个小时,要多练练automata才能快起来吧


注释一下本题分多少状态吧:

0初始无输入或者只有space的状态
1输入了数字之后的状态
2前面无数字,只输入了Dot的状态
3输入了符号状态
4前面有数字和有dot的状态
5'e' or 'E'输入后的状态
6输入e之后输入Sign的状态
7输入e后输入数字的状态
8前面有有效数输入之后,输入space的状态

共9种状态了,难设计的是6,7,8状态。

分好之后就好办了,设计出根据输入进行状态转换就OK了。


这里的输入可以分:

INVALID,  // 0 Include: Alphas, '(', '&' ans so on
SPACE,  // 1
SIGN, // 2 '+','-'
DIGIT,  // 3 numbers
DOT, // 4 '.'
EXPONENT,  // 5 'e' 'E'

然后就是画蜘蛛网吧,什么状态可以转换到什么状态的。


下面代码也注释出来了,参照了Leetcode论坛上的代码写的:

点击(此处)折叠或打开

  1. class Solution {
  2. public:
  3.     bool isNumber(const char *s) {
  4.         enum InputType {
  5.             INVALID,        // 0 Include: Alphas, '(', '&' ans so on
  6.             SPACE,        // 1
  7.             SIGN,        // 2 '+','-'
  8.             DIGIT,        // 3 numbers
  9.             DOT,            // 4 '.'
  10.             EXPONENT,        // 5 'e' 'E'
  11.         };
  12.         int transTable[][6] = {
  13.         //0INVA,1SPA,2SIG,3DI,4DO,5E
  14.             -1, 0, 3, 1, 2, -1,//0初始无输入或者只有space的状态
  15.             -1, 8, -1, 1, 4, 5,//1输入了数字之后的状态
  16.             -1, -1, -1, 4, -1, -1,//2前面无数字,只输入了Dot的状态
  17.             -1, -1, -1, 1, 2, -1,//3输入了符号状态
  18.             -1, 8, -1, 4, -1, 5,//4前面有数字和有dot的状态
  19.             -1, -1, 6, 7, -1, -1,//5'e' or 'E'输入后的状态
  20.             -1, -1, -1, 7, -1, -1,//6输入e之后输入Sign的状态
  21.             -1, 8, -1, 7, -1, -1,//7输入e后输入数字的状态
  22.             -1, 8, -1, -1, -1, -1,//8前面有有效数输入之后,输入space的状态
  23.         };
  24.         int state = 0;
  25.         while (*s)
  26.         {
  27.             InputType input = INVALID;
  28.             if (*s == ' ') input = SPACE;
  29.             else if (*s == '+' || *s == '-') input = SIGN;
  30.             else if (isdigit(*s)) input = DIGIT;
  31.             else if (*s == '.') input = DOT;
  32.             else if (*s == 'e' || *s == 'E') input = EXPONENT;
  33.             state = transTable[state][input];
  34.             if (state == -1) return false;
  35.             ++s;
  36.         }
  37.         return state == 1 || state == 4 || state == 7 || state == 8;
  38.     }
  39. };


阅读(301) | 评论(0) | 转发(0) |
0

上一篇:String例题分析

下一篇:LinkedList例题分析

给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册