資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究構建DFA以檢查給定整數是否為無符號整數的程式
在這個問題中，我們需要使用DFA來檢查給定的數字是否為無符號整數。我們需要使用二維陣列構建DFA來解決問題。
問題陳述 – 我們給定長度為N的字串str。透過構建DFA，我們需要檢查str是否表示無符號整數。在輸出中，根據數字是否為無符號整數列印“無符號整數”或“不是無符號整數”。
示例
輸入– str = "1729"
輸出– “無符號整數。”
解釋– 由於數字不包含任何符號，因此它是無符號整數。
輸入– str = “-1729”
輸出– “不是無符號整數。”
解釋– 該數字在開頭包含一個符號，因此它不是無符號整數。
方法1
在開始解決問題之前，讓我們瞭解如何構建DFA來查詢無符號整數。
以下是一些無符號整數的示例。
1234
1234.4567
1234E+215
1234E-215
123.456e+215
123.456e+215
以上示例表明，無符號整數可以包含數字、點、E/e、+ 或 -，以及再次出現的數字。
現在，讓我們構建DFA，如下所示。
在上面的DFA中，我們從第0個狀態開始。數字可以以任何數字開頭，幷包含多個數字，因為我們移動到第1個狀態。
在第1個狀態之後，如果我們得到其他字元，我們可以移動到第2個狀態；如果我們在十進位制數中得到“.”，則可以移動到第3個狀態。
在第3個狀態之後，我們需要至少1個或多個數字，然後我們可以移動到第4個狀態。
從第4個狀態，如果我們得到其他字元以接受數字，我們可以移動到第5個狀態；如果我們得到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。
用0初始化“current_state”變數以跟蹤狀態。
開始遍歷字串。
現在，透過從二維陣列中獲取值來將“current_state”的值更新為下一個狀態。例如，如果當前字元是數字，則使用dfa[current_state][0]更新“current_state”變數的值。如果當前字元是“+/-”符號，則使用dfa[current_state][1]更新current_state變數的值。
最後，如果“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構建的問題。
218 次瀏覽
