The article directories

    • What is deterministic, finite, machine
    • Watch a chestnut with me
      • The DFA diagram
      • DFA sample implementation code

DFA: Deterministic finite state machine This is clear if the state patterns in the design pattern are familiar. DFA is often used for sensitive word filtering.

What is deterministic, finite, machine

Ah, look at the name, it is easy to understand. First of all, it’s a machine for what? Let me tell you: a machine for pattern string filtering.

Often used to filter valid information from complex strings, such as sensitive words, lexical editing (used by compilers), etc. Of course, it’s common. Other people use it.

I love the feature. Deterministic, finite state, what can you think of? Figure, flow chart! Think again. What flow chart? Dynamic flowcharts, right? That’s natural.

Ordinary flow chart that process is locked, step by step is good, but the dynamic process is not the same, some people may not know what is called dynamic flow chart, do not know the normal, I just named. Dynamic linking, you know? That’s what it means.

In my opinion, the DFA mechanism is very suitable for the implementation of dynamic flow charts, especially complex dynamic flow charts. Of course, dynamic flowcharts can be written forcibly, but the code is a little fat.

Watch a chestnut with me

This is how I first came to know DFA, when I wrote it violently. Of course, the code was too fat for me to post it on that blog.

Implement an AToi function that converts a string to an integer.

First, the function discards useless leading whitespace characters as needed until the first non-whitespace character is found. The next conversion rule is as follows: If the first non-null character is a plus or minus sign, combine that character with as many consecutive numeric characters as possible to form a signed integer. If the first non-null character is a number, it is directly combined with successive numeric characters to form an integer. There may also be extra characters after the valid integer part of the string, so these characters can be ignored and should not affect the function. Note: If the first non-space character in the string is not a valid integer character, the string is empty, or the string contains only whitespace characters, then your function does not need to be converted, that is, it cannot be converted effectively. In any case, return if the function cannot be effectively converted0 。
Copy the code

Tip:

The whitespace in this case contains only the space character ' '. Suppose our environment can only store32A signed integer of bit size, then the value range is [−231.231 − 1]. If the value exceeds this range, returnINT_MAX (231 − 1) orINT_MIN(-231).Copy the code
The sample1: Enter:42"Output.42
Copy the code
The sample2Input:" -42"Output:- 42Explanation: The first non-whitespace character is a '-', which is a minus sign. We can combine the minus sign with all the consecutive numbers that follow, and we get- 42 。
Copy the code
The sample3: Enter:4193With words"4193Explanation: Conversion ends at number '3', because its next character is not a number.Copy the code
The sample4Enter: "Wordsand 987"Output.0Explanation: The first non-null character is' w ', but it is not a number or a plus or minus sign. Therefore, a valid transformation cannot be performed.Copy the code
The sample5: Enter:- 91283472332."Output.- 2147483648.Explanation: Numbers- 91283472332."More than32Bit range of signed integers. Therefore returnINT_MIN(-231).Copy the code

Source: LeetCode link: leetcode-cn.com/problems/st… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

The DFA diagram

Our program has a state S at each moment, enters a character C from the sequence at a time, and moves to the next state S ‘according to character C. So, all we need to do is create a table that maps from S and C to S ‘in all cases to solve the problem in the problem.

If you don’t understand the above picture, it doesn’t matter, I don’t understand it either. But here’s a chart you need to understand:



Right? The first column is the input, the first column is the status. The other part is what states are triggered by a particular input in a particular state.

For this table, a state of in_number means it’s ready to count, signed means it’s a sign, and end means it’s time to pack up and go.

So, how do I turn this table into code?

DFA sample implementation code

#include<iostream>

#include<vector>

using namespace std;

int DFA(vector<char>& cvec)
{
	vector<vector<int>> vec = { {0.1.2.3}, {3.3.2.3}, {3.3.2.3}, {3.3.3.3}};//DFA

	int stat = 0;// Real-time state, initialized to 0

	int ret = 0;	// Data record, let's initialize to 0
	int flag = 1;// Record positive and negative signs

	for (int sz = 0; sz < cvec.size(a); sz++) {// Here is the state machine go around
		if (isspace(cvec[sz]))
			stat = vec[stat][0];
		else if (cvec[sz] == '+' || cvec[sz] == The '-')
			stat = vec[stat][1];
		else if (isdigit(cvec[sz]))
			stat = vec[stat][2];
		else
			stat = 3;
		
		// The state machine runs out of state
		if (stat == 3)
			return ret * flag;
		else if (stat == 1)	// This is only one chance at most
		{
			if (cvec[sz] == The '-')
				flag = - 1;
		}
		else if (stat == 2) {}
			Stat == 3; stat == 3; stat == 3}}Copy the code