# DFA Parse Integer

## [Valid Number](https://leetcode.com/problems/valid-number/)

这题看一眼就会发现要考虑的各种奇葩 case 实在是太多了。。。对于这类需要 parse 的同时考虑 N 多种不同状态的字符串处理问题，就老老实实用 DFA (Deterministic Finite Automata) 吧，要不会被折磨疯的。

### 记得先把输入字符 trim 一下，免得前后空格不好处理。

### 状态列表，每一个独立状态用一个 char 表示；

* **s : 还未看到 + / - 号的起始状态**
* **S : 已看到符号的起始状态**
* **N : 读到数字了，还没遇到 '.' 或 'e'**
* **d : 首次碰到 '.'，后面还没有遇到数字**
* **D : 已碰到 '.' 并且后面有数字**
* **e : 首次碰到 'e'，后面还没有数字**
* **E : 已碰到 'e' 并且后面有数字**
* **F : 违法状态，一定为 false;**

### DFA 结构如图\~ 所有没画出来的边都是 'F'，以双圈结束(小写字母)的也都是 'F'.

![](https://2030049235-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MUt7Y8-dUQcwNZkL6dz%2Fsync%2Ff3efcc5fe2b4091ca8b2756b6e4daed81738fe21.jpg?generation=1614792531597563\&alt=media)

```java
public class Solution {
    public boolean isNumber(String s) {
        s = s.trim();
        int N = s.length();

        char curState = 's';
        for(int i = 0; i < N; i++){
            curState = transition(curState, s.charAt(i));
            if(curState == 'F') return false;
        }

        return (curState == 'd' || curState == 's' || curState == 'e') ? false: true;
    }

    private char transition(char curState, char chr){
        switch(curState){
            case 's':
                if(chr == '-' || chr == '+') return 'S';
                else if(Character.isDigit(chr)) return 'N';
                else if(chr == '.') return 'd';
            case 'S':
                if(Character.isDigit(chr)) return 'N';
                else if(chr == '.') return 'd';
                else return 'F';
            case 'N':
                if(Character.isDigit(chr)) return 'N';
                else if(chr == '.') return 'D';
                else if(chr == 'e') return 'e';
                else return 'F';
            case 'd':
                if(Character.isDigit(chr)) return 'D';
                else return 'F';
            case 'D':
                if(Character.isDigit(chr)) return 'D';
                else if(chr == 'e') return 'e';
                else return 'F';
            case 'e':
                if(chr == '-' || chr == '+') return 'e';
                else if(Character.isDigit(chr)) return 'E';
                else return 'F';
            case 'E':
                if(Character.isDigit(chr)) return 'E';
                else return 'F';
            case 'F':
                return 'F';
            default:
                return 'F';
        }
    }
}
```

## [String to Integer (atoi)](https://leetcode.com/problems/string-to-integer-atoi/)

一个意思，就是 DFA 结构稍微变了点。

### 检查 overflow 简便方法：

* **next = cur \* 10 + newVal;**
* **if(next / 10 != cur), overflow.**

```java
public class Solution {
    public int myAtoi(String str) {
        str = str.trim();

        int num = 0;
        int sign = 1;
        char curState = 's';

        for(int i = 0; i < str.length(); i++){
            curState = transition(curState, str.charAt(i));
            if(curState == 'N') sign = -1;
            if(curState == 'F') return num * sign;

            if(curState == 'S'){
                int val = (int) str.charAt(i) - '0';
                int next = num * 10 + val;
                if(next / 10 != num) return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
                num = next;
            }
        }
        if(curState == 's' || curState == 'P' || curState == 'N') return 0;

        return num * sign;
    }

    private char transition(char curState, char cur){
        switch(curState){
            case 's':
                if(cur == '+') return 'P';
                else if(cur == '-') return 'N';
                else if(Character.isDigit(cur)) return 'S';
                else return 'F';
            case 'S':
                if(Character.isDigit(cur)) return 'S';
                else return 'F';
            case 'N':
                if(Character.isDigit(cur)) return 'S';
                else return 'F';
            case 'P':
                if(Character.isDigit(cur)) return 'S';
                else return 'F';
            default:
                return 'F';
        }
    }
}
```

## [Reverse Integer](https://leetcode.com/problems/reverse-integer/)

刷题刷到现在我才深切体会到当初 bloomberg 面试题是多么的傻逼。。

```java
public class Solution {
    public int reverse(int x) {
        int num = 0;

        while(x != 0){
            int val = x % 10;
            int next = num * 10 + val;
            if(next / 10 != num) return 0;
            num = next;
            x /= 10;
        }

        return num;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/linkedin_mian_jing/dfa_parse_integer.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.