65.有效数字

LeetCode

条件判断

维护了三个状态

• 有 e|E 的时候，!hasE用于判断这是第一次遇到 e|E 这个字符，因为 e|E 只能有一个，hasNum表示遇到 e|E 的时候前面必须有一个数字

  后面一句 hasNum = false 排除了 +2e 以 e|E 结尾的情况

• 有 . 的时候，.一定在 e|E 的前面，所以判断!hasE，.只可能有一个，所以isFloat为false

var isNumber = function (s) {
  // 是否存在e,
  var hasE = false;
  var hasNum = false;
  var isFloat = false;
  for (let i = 0; i < s.length; i++) {
    var c = s[i];
    // 符号只能在首位，或者E|e 的后一位
    if (
      (c == "+" || c == "-") &&
      (i == 0 || s[i - 1] === "e" || s[i - 1] === "E")
    ) {
      //e只能有一个，e的前面必须是数字
    } else if ((c === "e" || c === "E") && !hasE && hasNum) {
      hasE = true;
      hasNum = false;
    } else if (c === "." && !isFloat && !hasE) {
      isFloat = true;
    } else if (/[0-9]/.test(c)) {
      hasNum = true;
    } else {
      return false;
    }
  }
  return hasNum;
};

有限状态机

确定有限状态自动机

一个有效数字可以分为一下几个部分 ：

• 符号位，即 + - 两种符号
• 整数部分，即由若干字符 0-9 组成的字符串
• 小数点
• 小数部分，其构成与整数部分相同
• 指数部分，其中包含开头的字符 e（大写小写均可）、可选的符号位，和整数部分

每个部分都不是必需的，但也受一些额外规则的制约：

• 如果符号位存在，其后面必须跟着数字或小数点。
• 小数点的前后两侧，至少有一侧是数字。

根据上面的分析可以把一个有效数字分为下面几个状态:

• 符号位
• 整数部分
• 左侧有整数的小数点
• 左侧无整数的小数点（根据前面的第二条额外规则，需要对左侧有无整数的两种小数点做区分）
• 小数部分
• 字符 e
• 指数部分的符号位
• 指数部分的整数部分

var isNumber = function (s) {
  const State = {
    STATE_INITIAL: "STATE_INITIAL", // 初始状态
    STATE_INT_SIGN: "STATE_INT_SIGN", // 符号位
    STATE_INTEGER: "STATE_INTEGER", //整数部分
    STATE_POINT: "STATE_POINT", // 左侧有整数的小数点
    STATE_POINT_WITHOUT_INT: "STATE_POINT_WITHOUT_INT", //左侧无整数的小数点
    STATE_FRACTION: "STATE_FRACTION", //小数部分
    STATE_EXP: "STATE_EXP", //字符e
    STATE_EXP_SIGN: "STATE_EXP_SIGN", //指数部分的符号位
    STATE_EXP_NUMBER: "STATE_EXP_NUMBER", //指数部分的整数部分
    STATE_END: "STATE_END", //结束状态
  };

  const CharType = {
    CHAR_NUMBER: "CHAR_NUMBER",
    CHAR_EXP: "CHAR_EXP",
    CHAR_POINT: "CHAR_POINT",
    CHAR_SIGN: "CHAR_SIGN",
    CHAR_ILLEGAL: "CHAR_ILLEGAL",
  };

  const toCharType = (ch) => {
    if (!isNaN(ch)) {
      return CharType.CHAR_NUMBER;
    } else if (ch.toLowerCase() === "e") {
      return CharType.CHAR_EXP;
    } else if (ch === ".") {
      return CharType.CHAR_POINT;
    } else if (ch === "+" || ch === "-") {
      return CharType.CHAR_SIGN;
    } else {
      return CharType.CHAR_ILLEGAL;
    }
  };

  const transfer = new Map();
  const initialMap = new Map();
  initialMap.set(CharType.CHAR_NUMBER, State.STATE_INTEGER);
  initialMap.set(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
  initialMap.set(CharType.CHAR_SIGN, State.STATE_INT_SIGN);
  transfer.set(State.STATE_INITIAL, initialMap);
  const intSignMap = new Map();
  intSignMap.set(CharType.CHAR_NUMBER, State.STATE_INTEGER);
  intSignMap.set(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
  transfer.set(State.STATE_INT_SIGN, intSignMap);
  const integerMap = new Map();
  integerMap.set(CharType.CHAR_NUMBER, State.STATE_INTEGER);
  integerMap.set(CharType.CHAR_EXP, State.STATE_EXP);
  integerMap.set(CharType.CHAR_POINT, State.STATE_POINT);
  transfer.set(State.STATE_INTEGER, integerMap);
  const pointMap = new Map();
  pointMap.set(CharType.CHAR_NUMBER, State.STATE_FRACTION);
  pointMap.set(CharType.CHAR_EXP, State.STATE_EXP);
  transfer.set(State.STATE_POINT, pointMap);
  const pointWithoutIntMap = new Map();
  pointWithoutIntMap.set(CharType.CHAR_NUMBER, State.STATE_FRACTION);
  transfer.set(State.STATE_POINT_WITHOUT_INT, pointWithoutIntMap);
  const fractionMap = new Map();
  fractionMap.set(CharType.CHAR_NUMBER, State.STATE_FRACTION);
  fractionMap.set(CharType.CHAR_EXP, State.STATE_EXP);
  transfer.set(State.STATE_FRACTION, fractionMap);
  const expMap = new Map();
  expMap.set(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
  expMap.set(CharType.CHAR_SIGN, State.STATE_EXP_SIGN);
  transfer.set(State.STATE_EXP, expMap);
  const expSignMap = new Map();
  expSignMap.set(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
  transfer.set(State.STATE_EXP_SIGN, expSignMap);
  const expNumberMap = new Map();
  expNumberMap.set(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
  transfer.set(State.STATE_EXP_NUMBER, expNumberMap);

  const length = s.length;
  let state = State.STATE_INITIAL;

  for (let i = 0; i < length; i++) {
    const type = toCharType(s[i]);
    if (!transfer.get(state).has(type)) {
      return false;
    } else {
      state = transfer.get(state).get(type);
    }
  }
  return (
    state === State.STATE_INTEGER ||
    state === State.STATE_POINT ||
    state === State.STATE_FRACTION ||
    state === State.STATE_EXP_NUMBER ||
    state === State.STATE_END
  );
};

函数式有限状态机

const start = (c) => {
  const type = toCharType(c);
  if (type === CharType.CHAR_NUMBER) return integer;
  if (type === CharType.CHAR_POINT) return pointWithoutInt;
  if (type === CharType.CHAR_SIGN) return intSign;
  return end;
};
const integer = (c) => {};
const pointWithoutInt = () => {};
const intSign = () => {};
const end = () => end;

打赏