Dada una string S que representa un número entero, la tarea es verificar si la string S dada representa un número entero sin signo o no mediante la construcción del DFA . Si la string dada representa un entero sin signo, imprima «Entero sin signo» . De lo contrario, imprima «No es un entero sin signo» .
Ejemplos:
Entrada: S = “+4554”
Salida: No es un entero sin signoEntrada: S = “1729”
Salida: entero sin signo
Enfoque: a continuación se muestran los estados de transición de DFA para el problema dado:
Siga los pasos a continuación para resolver el problema:
- Declare una función para compilar y conectar estados de DFA según las condiciones dadas. A continuación se muestra la representación de los estados de transición:
- 0 representa un dígito .
- 1 representa el signo «+/-« .
- 2 representa “.” o punto .
- 3 representa cualquier otro carácter .
- 4 representa el exponente (signo e/E) .
- Inicialice una variable, digamos currentState como 0 , que almacene el estado actual en el DFA.
- Atraviese la string S y, en función del estado actual y el carácter presente en el índice actual, decida el siguiente estado del DFA .
- Después de completar los pasos anteriores, si el valor de currentState es 1 , 4 u 8 , imprima «Entero sin signo » . De lo contrario, imprima «No es un entero sin signo» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include "bits/stdc++.h"
using namespace std;
string digits = "0123456789", sign = "+-";
string dot = ".", ex = "eE";
int dfa[11][5];
// Function to construct DFA as per the
// given conditions
void makeDFA()
{
// If at state 0 and a digit has
// occurred then set it to state 1
dfa[0][0] = 1;
// Similarly for all other states
dfa[1][0] = 1;
dfa[1][2] = 3;
dfa[1][3] = 2;
dfa[1][4] = 6;
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 build and connect
// the DFA states
void buildDFA()
{
// Connect all the states to the
// dead state
for (int i = 0; i < 11; i++)
for (int j = 0; j < 5; j++)
dfa[i][j] = 10;
// Function call to make DFA as
// per the given conditions
makeDFA();
}
// Function call to check whether an
// integer in the form of string is
// unsigned integer or not
void checkDFA(string s)
{
// Build the DFA
buildDFA();
// Stores the current state
int currentstate = 0;
// Traverse the string
for (int i = 0; i < s.size(); i++) {
if (digits.find(s[i])
!= digits.npos)
// If at a certain state a
// digit occurs then change
// the current state according
// to the DFA
currentstate
= dfa[currentstate][0];
// Or +/- sign
else if (sign.find(s[i])
!= sign.npos)
currentstate
= dfa[currentstate][1];
// Or decimal occurred
else if (dot.find(s[i])
!= dot.npos)
currentstate
= dfa[currentstate][2];
// Or any other character
else if (ex.find(s[i])
!= ex.npos)
currentstate
= dfa[currentstate][4];
// Or e/E or exponent sign
else
currentstate
= dfa[currentstate][3];
}
// State 1, 4, 8 will give
// the final answer
if (currentstate == 1
|| currentstate == 4
|| currentstate == 8) {
cout << "Unsigned integer";
}
else {
cout << "Not an unsigned integer";
}
}
// Driver Code
int main()
{
string S = "1729";
checkDFA(S);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
static String digits = "0123456789", sign = "+-";
static String dot = ".", ex = "eE";
static int dfa[][] = new int[11][5];
// Function to construct DFA as per the
// given conditions
static void makeDFA()
{
// If at state 0 and a digit has
// occurred then set it to state 1
dfa[0][0] = 1;
// Similarly for all other states
dfa[1][0] = 1;
dfa[1][2] = 3;
dfa[1][3] = 2;
dfa[1][4] = 6;
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 build and connect
// the DFA states
static void buildDFA()
{
// Connect all the states to the
// dead state
for(int i = 0; i < 11; i++)
for(int j = 0; j < 5; j++)
dfa[i][j] = 10;
// Function call to make DFA as
// per the given conditions
makeDFA();
}
// Function call to check whether an
// integer in the form of string is
// unsigned integer or not
static void checkDFA(String s)
{
// Build the DFA
buildDFA();
// Stores the current state
int currentstate = 0;
// Traverse the string
for(int i = 0; i < s.length(); i++)
{
if (digits.indexOf(s.charAt(i)) != -1)
// If at a certain state a
// digit occurs then change
// the current state according
// to the DFA
currentstate = dfa[currentstate][0];
// Or +/- sign
else if (sign.indexOf(s.charAt(i)) != -1)
currentstate = dfa[currentstate][1];
// Or decimal occurred
else if (dot.indexOf(s.charAt(i)) != -1)
currentstate = dfa[currentstate][2];
// Or any other character
else if (ex.indexOf(s.charAt(i)) != -1)
currentstate = dfa[currentstate][4];
// Or e/E or exponent sign
else
currentstate = dfa[currentstate][3];
}
// State 1, 4, 8 will give
// the final answer
if (currentstate == 1 || currentstate == 4 ||
currentstate == 8)
{
System.out.println("Unsigned integer");
}
else
{
System.out.println("Not an unsigned integer");
}
}
// Driver Code
public static void main(String[] args)
{
String S = "1729";
checkDFA(S);
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach
digits,sign = "0123456789", "+-"
dot, ex = ".", "eE"
dfa = [[0 for i in range(5)] for i in range(11)]
# Function to construct DFA as per the
# given conditions
def makeDFA():
global dfa
# If at state 0 and a digit has
# occurred then set it to state 1
dfa[0][0] = 1
# Similarly for all other states
dfa[1][0] = 1
dfa[1][2] = 3
dfa[1][3] = 2
dfa[1][4] = 6
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 build and connect
# the DFA states
def buildDFA():
global dfa
# Connect all the states to the
# dead state
for i in range(11):
for j in range(5):
dfa[i][j] = 10
# Function call to make DFA as
# per the given conditions
makeDFA()
# Function call to check whether an
# integer in the form of is
# unsigned integer or not
def checkDFA(s):
# Build the DFA
buildDFA()
# Stores the current state
currentstate = 0
# Traverse the string
for i in range(len(s)):
if (s[i] in digits):
# If at a certain state a
# digit occurs then change
# the current state according
# to the DFA
currentstate = dfa[currentstate][0]
# Or +/- sign
elif (s[i] in sign):
currentstate = dfa[currentstate][1]
# Or decimal occurred
elif (s[i] in dot):
currentstate = dfa[currentstate][2]
# Or any other character
elif (s[i] in ex):
currentstate = dfa[currentstate][4]
# Or e/E or exponent sign
else:
currentstate = dfa[currentstate][3]
# State 1, 4, 8 will give
# the final answer
if (currentstate == 1 or currentstate == 4 or currentstate == 8):
print("Unsigned integer")
else:
print("Not an unsigned integer")
# Driver Code
if __name__ == '__main__':
S = "1729"
checkDFA(S)
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG{
static string digits = "0123456789", sign = "+-";
static string dot = ".", ex = "eE";
static int[,] dfa = new int[11, 5];
// Function to construct DFA as per the
// given conditions
static void makeDFA()
{
// If at state 0 and a digit has
// occurred then set it to state 1
dfa[0, 0] = 1;
// Similarly for all other states
dfa[1, 0] = 1;
dfa[1, 2] = 3;
dfa[1, 3] = 2;
dfa[1, 4] = 6;
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 build and connect
// the DFA states
static void buildDFA()
{
// Connect all the states to the
// dead state
for(int i = 0; i < 11; i++)
for(int j = 0; j < 5; j++)
dfa[i, j] = 10;
// Function call to make DFA as
// per the given conditions
makeDFA();
}
// Function call to check whether an
// integer in the form of string is
// unsigned integer or not
static void checkDFA(string s)
{
// Build the DFA
buildDFA();
// Stores the current state
int currentstate = 0;
// Traverse the string
for(int i = 0; i < s.Length; i++)
{
if (digits.IndexOf(s[i]) != -1)
// If at a certain state a
// digit occurs then change
// the current state according
// to the DFA
currentstate = dfa[currentstate, 0];
// Or +/- sign
else if (sign.IndexOf(s[i]) != -1)
currentstate = dfa[currentstate, 1];
// Or decimal occurred
else if (dot.IndexOf(s[i]) != -1)
currentstate = dfa[currentstate, 2];
// Or any other character
else if (ex.IndexOf(s[i]) != -1)
currentstate = dfa[currentstate, 4];
// Or e/E or exponent sign
else
currentstate = dfa[currentstate, 3];
}
// State 1, 4, 8 will give
// the final answer
if (currentstate == 1 || currentstate == 4 ||
currentstate == 8)
{
Console.WriteLine("Unsigned integer");
}
else
{
Console.WriteLine("Not an unsigned integer");
}
}
// Driver Code
public static void Main(string[] args)
{
string S = "1729";
checkDFA(S);
}
}
// This code is contributed by ukasp
Javascript
<script>
// JavaScript program for the above approach
let digits = "0123456789", sign = "+-";
let dot = ".", ex = "eE";
let dfa = new Array(11);
for(let i=0;i<11;i++)
{
dfa[i]=new Array(5);
}
// Function to construct DFA as per the
// given conditions
function makeDFA()
{
// If at state 0 and a digit has
// occurred then set it to state 1
dfa[0][0] = 1;
// Similarly for all other states
dfa[1][0] = 1;
dfa[1][2] = 3;
dfa[1][3] = 2;
dfa[1][4] = 6;
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 build and connect
// the DFA states
function buildDFA()
{
// Connect all the states to the
// dead state
for(let i = 0; i < 11; i++)
for(let j = 0; j < 5; j++)
dfa[i][j] = 10;
// Function call to make DFA as
// per the given conditions
makeDFA();
}
// Function call to check whether an
// integer in the form of string is
// unsigned integer or not
function checkDFA(s)
{
// Build the DFA
buildDFA();
// Stores the current state
let currentstate = 0;
// Traverse the string
for(let i = 0; i < s.length; i++)
{
if (digits.indexOf(s[i]) != -1)
// If at a certain state a
// digit occurs then change
// the current state according
// to the DFA
currentstate = dfa[currentstate][0];
// Or +/- sign
else if (sign.indexOf(s[i]) != -1)
currentstate = dfa[currentstate][1];
// Or decimal occurred
else if (dot.indexOf(s[i]) != -1)
currentstate = dfa[currentstate][2];
// Or any other character
else if (ex.indexOf(s[i]) != -1)
currentstate = dfa[currentstate][4];
// Or e/E or exponent sign
else
currentstate = dfa[currentstate][3];
}
// State 1, 4, 8 will give
// the final answer
if (currentstate == 1 || currentstate == 4 ||
currentstate == 8)
{
document.write("Unsigned integer<br>");
}
else
{
document.write("Not an unsigned integer");
}
}
// Driver Code
let S = "1729";
checkDFA(S);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Unsigned integer
Complejidad de Tiempo: O(N)
Espacio Auxiliar: O(1), ya que no se ha tomado espacio extra.
Publicación traducida automáticamente
Artículo escrito por abhijeet010304 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA