C++ 构建用于检查给定整数是否为无符号的DFA程序

在这个问题中，我们需要使用DFA来检查给定的数字是否为无符号整数。我们需要使用二维数组来构建DFA来解决这个问题。

问题描述 - 给定长度为N的字符串str。通过构建DFA，我们需要检查str是否表示无符号整数。根据数字是否为无符号的，输出相应的“无符号整数”或“不是无符号整数”。

示例

输入 - str = “1729”

输出 - “无符号整数”

解释 - 由于数字不包含任何符号，它是一个无符号整数。

输入 - str = “-1729”

输出 - “不是无符号整数”

解释 - 数字以符号开头，所以它不是一个无符号整数。

算法

在开始解决方案之前，让我们了解如何构建DFA来查找无符号整数。

下面是一些无符号整数的例子：

1234
1234.4567
1234E+215
1234E-215
123.456e+215
123.456e+215

上述例子表明有符号整数可以包含数字、点、E/e、+或-，然后是数字。

现在，让我们构建DFA，如下所示：

C++ 构建用于检查给定整数是否为无符号的DFA程序

在上述DFA中，我们从第0个状态开始。数字可以以任何数字开头，并且可以包含多个数字，因为我们前进到第1个状态。
在第1个状态之后，如果我们获得其他字符，我们可以进入第2个状态，如果我们在十进制数中获得’。’，则可以进入第3个状态。
在第3个状态之后，我们至少需要1个或多个数字，并且我们可以进入第4个状态。
从第4个状态开始，如果我们获得其他字符以接受该数字，并且在获得E/e后获得第5个状态。
如果我们在E/e之后得到’+’或’-‘，我们可以进入第6个状态。这里，E/e代表指数；之后，我们需要写入正或负的幂。
之后，我们需要在数字中添加幂。因此，我们可以进入第8个状态。
如果我们从第8个状态获得任何字符，我们可以进入第9个状态。

现在，我们需要在代码中构建一个DFA。

在一个二维数组中，第一维表示当前状态，第二维表示字符类型，如下所示。

第0个索引是用于数字。
第1个索引是’+’或’-‘符号。
第2个索引是’。
第3个索引是其他字符。
第4个索引是’e/E’。

步骤

定义字符串digits并添加所有的数字。另外，定义sign、dot和ex变量，并用相应的值进行初始化。
定义数组dfa来存储状态和下一个状态。同时，定义constructDFA()函数来使用一个二维数组构建DFA。
在constructDFA()函数中，初始化数组为10，因为初始时所有的状态都是不可达的。
我们需要通过它们的下一个状态来更新数组的值。例如，初始时我们处于状态0，只有在字符串以数字开头时才能继续前进。所以，更新dfa[0][0] = 1。
在isUnsignedInt()函数中，首先执行constructDFA()函数来构建DFA。
将current_state变量初始化为0，用于跟踪状态。
开始遍历字符串。
现在，通过取二维数组中的值来更新current_state变量的值到下一个状态。例如，如果当前字符是数字，则更新current_state变量的值为dfa[current_state][0]。如果当前字符是+/-符号，则更新current_state变量的值为dfa[current_state][1]。
最后，如果current_state的值是1、4或8，说明给定的数字是一个有效的有符号整数。

示例

#include "bits/stdc++.h"
using namespace std;
string digits = "0123456789", sign = "+-";
string dot = ".", ex = "eE";
int dfa[11][5];
// function to construct DFA
void constructDFA() {
    // Initially, all states are unreachable from state 0, so connect all states to state 10 (dead state).
    for (int i = 0; i < 11; i++)
        for (int j = 0; j < 5; j++)
            dfa[i][j] = 10;
    // If the state is zero and we get a digit, then change the state to 1.
    dfa[0][0] = 1;
    // If the state is 1, and we get different characters, set the array value accordingly.
    dfa[1][0] = 1;
    dfa[1][2] = 3;
    dfa[1][3] = 2;
    dfa[1][4] = 6;
    // Also, Initialize the array value for states 3, 6, 7, 8.
    dfa[3][0] = 4;
    dfa[4][0] = 4;
    dfa[4][3] = 5;
    dfa[4][4] = 6;
    dfa[6][0] = 8;
    dfa[6][1] = 7;
    dfa[7][0] = 8;
    dfa[8][0] = 8;
    dfa[8][3] = 9;
}
// function to check if the given string is an unsigned integer or not
string isUnsinedInt(string s) {
    // Build the DFA
    constructDFA();
    // Initially, the current state is 0.
    int current_state = 0;
    // Traverse the string
    for (int i = 0; i < s.size(); i++) {
        // Check the type of the current character and change the state accordingly
        // If a digit occurs
        if (digits.find(s[i]) != digits.npos)
            // Change the state to 0.
            current_state = dfa[current_state][0];
        // If a sign occurs, change the state to 1.
        else if (sign.find(s[i]) != sign.npos)
            current_state = dfa[current_state][1];
        // If a dot occurs, change the state to 3.
        else if (dot.find(s[i]) != dot.npos)
            current_state = dfa[current_state][2];
        // If e/E or exponent sign occurs, change the state to 4.
        else if (ex.find(s[i]) != ex.npos)
            current_state = dfa[current_state][4];
        // If any other character occurs, change the state to 3.
        else
            current_state = dfa[current_state][3];
    }
    // If the current state is 1, 4, 8, then the number is an unsigned integer
    if (current_state == 1 || current_state == 4 || current_state == 8) {
       return "Unsigned integer";
    }
    else {
       return "Not an unsigned integer";
    }
}
int main() {
    string str = "1729";
    cout << "The given number is " << isUnsinedInt(str);
    return 0;
}

输出

The given number is Unsigned integer

时间复杂度 – O(N)，因为我们遍历字符串。

空间复杂度 – O(1)，因为我们使用恒定的空间来存储DFA状态。

在本教程中，我们构建了DFA来检查给定的字符串是否是无符号整数。此外，程序员可以通过给定的图像可视化DFA，并更好地理解DFA。之后，我们使用一个二维数组构建了相同的DFA。为了获得结果，我们根据当前字符将“current_state”的值更改为下一个状态。程序员可以尝试解决包含DFA构建的其他问题。