AcWing 31. 表示数值的字符串

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 31. 表示数值的字符串原题链接困难

作者：

yxc , 2019-01-06 02:36:05 , 所有人可见 , 阅读 6641

35

9

算法

(模拟，字符串处理) $O(n)$

先去除行首和行尾空格；
行首如果有一个正负号，直接忽略；
如果字符串为空或只有一个'.'，则不是一个合法数；
循环整个字符串，去掉以下几种情况：
(1) '.'或'e'多于1个;
(2) '.'在'e'后面出现；
(3) 'e'后面或前面为空，或者'e'前面紧跟着'.'；
(4) 'e'后面紧跟着正负号，但正负号后面为空；
剩下的情况都合法；

时间复杂度分析：整个字符串只遍历一遍，所以时间复杂度是 $O(n)$ 。

C++ 代码

class Solution {
public:
    bool isNumber(string s) {
        int i = 0;
        while (i < s.size() && s[i] == ' ') i ++ ;
        int j = s.size() - 1;
        while (j >= 0 && s[j] == ' ') j -- ;
        if (i > j) return false;
        s = s.substr(i, j - i + 1);

        if (s[0] == '-' || s[0] == '+') s = s.substr(1);
        if (s.empty() || s[0] == '.' && s.size() == 1) return false;

        int dot = 0, e = 0;
        for (int i = 0; i < s.size(); i ++ )
        {
            if (s[i] >= '0' && s[i] <= '9');
            else if (s[i] == '.')
            {
                dot ++ ;
                if (e || dot > 1) return false;
            }
            else if (s[i] == 'e' || s[i] == 'E')
            {
                e ++ ;
                if (i + 1 == s.size() || !i || e > 1 || i == 1 && s[0] == '.') return false;
                if (s[i + 1] == '+' || s[i + 1] == '-')
                {
                    if (i + 2 == s.size()) return false;
                    i ++ ;
                }
            }
            else return false;
        }
        return true;
    }
};

25 评论

密集指针 2020-08-20 11:55

分享一种神奇的指针解法 核心思想为使用一个指针从前往后逐个检查字符串中的字符，合法的字符指针后移，否则不移动，同时使用一个标志变量记录从开始到当前位置的字符串是否为合法的数值，最终输出结果由指针是否移动到字符串末尾和标志变量的值决定
神奇的指针解法

yxc 2020-09-22 13:47

棒。

崔峰 2020-09-23 14:05

看完后手动回来点赞！！！

yxc 2020-10-12 13:10 回复了崔峰的评论

东边的西瓜皮 2021-04-01 18:08

分享一下文法描述的方法，https://www.acwing.com/solution/content/42734/

美琴 2023-10-01 08:22

#### 编译原理做法

"""
decimal:             unsigned-decimal
                     | sign unsigned-decimal
unsigned-decimal:    unsigned-integer . (special case)
                     | unsigned-exp-prefix
                     | unsigned-exp-prefix exp-sym exp-integer
unsigned-integer:    digit | digit unsigned-integer
unsigned-exp-prefix: unsigned-integer
                     | . unsigned-integer
                     | unsigned-integer . unsigned-integer
exp-integer:         unsigned-integer
                     | sign unsigned-integer
sign:                + | -
digit:               0-9
exp-sym:             e | E
"""

class Solution(object):
  def isNumber(self, s):
    """
    :type s: str
    :rtype: bool
    """
    self.s = s
    self.i = 0
    return self.decimal() and self.i == len(s)

  def decimal(self):
    self.sign();
    return self.unsigned_decimal()

  def unsigned_decimal(self):
    return self.unsigned_exp_prefix()

  def unsigned_exp_prefix(self):
    dot_before_digit = self.dot()
    t = self.unsigned_integer()

    if not dot_before_digit and self.dot():
      is_exp_prefix = self.unsigned_integer()
    else:
      is_exp_prefix = t

    if is_exp_prefix and self.exp_sym():
      return self.exp_integer()

    return t

  def unsigned_integer(self):
    if self.digit():
      self.unsigned_integer()
      return True
    return False

  def exp_integer(self):
    self.sign();
    return self.unsigned_integer()

  def peek(self):
    if self.i >= len(self.s):
      return "x"
    return self.s[self.i]

  def valid(self, checker):
    if checker(self.peek()):
      self.i += 1
      return True
    return False

  def dot(self):
    return self.valid(lambda c: c == '.')

  def sign(self):
    return self.valid(lambda c: c in '+-')

  def digit(self):
    return self.valid(lambda c: c in '0123456789')

  def exp_sym(self):
    return self.valid(lambda c: c in 'eE')

美琴 2023-10-01 04:30

#### 状态机做法

class Solution {
public:
  enum State {
    Empty,             // 空字符
    Sign,              // 正负号（前面无数字）
    Int,               // 整数内部
    Dot,               // 小数点（前面无数字）
    DotAfterInt,       // 小数点（前面有数字）
    Fraction,          // 小数内部
    ExpSymbol,         // 指数符号
    ExpSign,           // 指数正负号
    ExpInt,            // 指数内部
    SyntaxError,       // 格式错误
    Finish             // 解析成功
  };

  #define isSign(c) (c == '+' || c == '-')
  #define isExpSym(c) (c == 'e' || c == 'E')
  #define isDigit(c) (c >= '0' && c <= '9')

  bool isNumber(string s) {
    if (s.size() == 0) return false;

    auto t = Empty;
    int i = 0;
    while (t != SyntaxError && t != Finish) {
      char c = s[i];
      switch (t) {
        case Empty:
          if (isSign(c)) t = Sign;
          else if (isDigit(c)) t = Int;
          else if (c == '.') t = Dot;
          else t = SyntaxError;
          break;
        case Sign:
          if (isDigit(c)) t = Int;
          else if (c == '.') t = Dot;
          else t = SyntaxError;
          break;
        case Int:
          if (isDigit(c)) break;
          else if (c == '.') t = DotAfterInt;
          else if (isExpSym(c)) t = ExpSymbol;
          else t = SyntaxError;
          break;
        case Dot:
        case DotAfterInt:
          if (isDigit(c)) t = Fraction;
          else t = SyntaxError;
          break;
        case Fraction:
          if (isDigit(c)) break;
          else if (isExpSym(c)) t = ExpSymbol;
          else t = SyntaxError;
          break;
        case ExpSymbol:
          if (isSign(c)) t = ExpSign;
          else if (isDigit(c)) t = ExpInt;
          else t = SyntaxError;
          break;
        case ExpSign:
          if (isDigit(c)) t = ExpInt;
          else t = SyntaxError;
          break;
        case ExpInt:
          if (!isDigit(c)) t = SyntaxError;
          break;
      }

      if (++i == s.size()) {
        switch (t) {
          case Sign:
          case Dot:
          case ExpSymbol:
          case ExpSign:
            t = SyntaxError;
            break;
          default:
            t = Finish;
        }
      }
    }

    return t == Finish;
  }
};