Valid Number

Difficulty Level Hard
Frequently asked in Amazon Facebook LinkedIn Oracle
Math StringViews 2142

In the Valid Number problem we have given a string, check if it can be interpreted into a valid decimal number.

It is to be noted that, for a given string to be interpreted as a valid decimal number. It should contain the following characters:

  • Numbers 0-9
  • Exponent – “e”
  • Positive/negative sign – “+”/”-“
  • Decimal point – “.”

However, the order and context of these characters also matter for an input string to be a valid decimal number.

Example

Input:
0
 0.1 
abc
1 a
2e10
 -90e3   
 1e
e3
 6e-1
 99e2.5 
53.5e93
 --6 
-+3
95a54e53

Output:
Valid decimal number
Valid decimal number
Invalid decimal number
Invalid decimal number
Valid decimal number
Valid decimal number
Invalid decimal number
Invalid decimal number
Valid decimal number
Invalid decimal number
Valid decimal number
Invalid decimal number
Invalid decimal number
Invalid decimal number

Types of Solution for Valid Number

  1. String Processing
  2. Regex

String Processing

Approach

The idea is to traverse each of the input string characters and check if the following rules are followed:

  1. Skip all the leading and trailing spaces in the string.
  2. If a string consists of ‘e’/’E’,exponential symbol. Then, consider the input string [exp1]E[exp2] into two different parts, which are,
    • exp1 is the part of the string that comes before the exponential symbol.
    • exp2 is the part of the string that comes after the exponential symbol.
  3. exp1 should be either be an integer or decimal number (ex: 124.12 -> number followed by a dot, dot followed by a number).
  4. exp2 should be an integer.
  5. only two kinds of arithmetic symbols are permitted (which are ‘+’ and ‘-‘) and if there are any such symbols in the expression then they should be placed before exp1 and exp2.
  6. The expression cannot contain two consecutive arithmetic symbols.
  7. Any character apart from numbers, valid arithmetic symbols, or exponential symbol, if present in the input string, then the input string can’t be treated as a valid decimal number.
  8. if the string doesn’t consist of an exponential symbol, then only consider conditions 1,6 and 7.

If all the rules from 1-7 are satisfied, then an input string can be interpreted as a valid expression.

Implementation

C++ Program for Valid Number
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

bool isSpace(char c){ return c==' ';}       // check if given character is space
bool isSign(char c){ return c=='+'||c=='-';} // check if given character is valid sign
bool isDot(char c){ return c=='.';}         // check if given character is dot
bool isNum(char c){ return c<='9'&&c>='0';} // check if given character is valid number
bool isE(char c){ return c=='e'||c=='E';}   // check if given character is exponential sign

bool isNumber(string num)
{
    int i = 0;
    int length = num.length();
    
    bool hasNum = false;

    // Skip all the prefix spaces
    while (i<length && isSpace(num[i])) i++;

    // Check the next char if it's a +/- sign
    if (i<length && isSign(num[i])) i++;

    // Characters exceeding the sign should be a set of numbers
    while (i<length && isNum(num[i]) ) {hasNum = true; i++;}

    // After processing the number part, a dot('.') appears
    if (i<length && isDot(num[i])) i++;

    // Check the numbers after a dot '.'
    while (i<length && isNum(num[i])) {hasNum = true; i++;}

    // Check the 'e' / 'E'
    if (hasNum && i<length && isE(num[i])) 
    {
        hasNum = false; i++;
        // skip the sign after e/E
        if (i<length && isSign(num[i])) i++;
    }

    // Check the numbers after 'e' / 'E' and sign
    while (i<length && isNum(num[i])) {hasNum = true; i++;}

    // Skip all the trailing spaces
    while (i<length && isSpace(num[i])) i++;

    /* After processing the main decimal number and trailing spaces, 
    if more Characters are left then the number is not Valid or
    if the string doesn't consist of numbers*/
    return i == length && hasNum;
}

int main()
{
    int n = 14;
    string num;
    
    while(n--)
    {
        /* input should accept a string with whitespaces */
        getline(cin,num);
        if(isNumber(num))
        cout<<"Valid decimal number"<<endl;
        else
        cout<<"Invalid decimal number"<<endl;
    }
    
    return 0;
}
0
 0.1 
abc
1 a
2e10
 -90e3   
 1e
e3
 6e-1
 99e2.5 
53.5e93
 --6 
-+3
95a54e53
Valid decimal number
Valid decimal number
Invalid decimal number
Invalid decimal number
Valid decimal number
Valid decimal number
Invalid decimal number
Invalid decimal number
Valid decimal number
Invalid decimal number
Valid decimal number
Invalid decimal number
Invalid decimal number
Invalid decimal number
Java Program for Valid Number
import java.util.*;
import java.lang.*;
import java.io.*;


class TutorialCup
{
    static boolean isSpace(char c){ return c==' ';}       // check if given character is space
    static boolean isSign(char c){ return c=='+'||c=='-';} // check if given character is valid sign
    static boolean isDot(char c){ return c=='.';}         // check if given character is dot
    static boolean isNum(char c){ return c<='9'&&c>='0';} // check if given character is valid number
    static boolean isE(char c){ return c=='e'||c=='E';}   // check if given character is exponential sign
  
  static boolean isNumber(String num)
    {
        int i = 0;
        int length = num.length();
        
        boolean hasNum = false;
    
        // Skip all the prefix spaces
        while (i<length && isSpace(num.charAt(i))) i++;
    
        // Check the next char if it's a +/- sign
        if (i<length && isSign(num.charAt(i))) i++;
    
        // Characters exceeding the sign should be a set of numbers
        while (i<length && isNum(num.charAt(i))) {hasNum = true; i++;}
    
        // After processing the number part, a dot('.') appears
        if (i<length && isDot(num.charAt(i))) i++;
    
        // Check the numbers after a dot '.'
        while (i<length && isNum(num.charAt(i))) {hasNum = true; i++;}
    
        // Check the 'e' / 'E'
        if (hasNum && i<length && isE(num.charAt(i))) 
        {
            hasNum = false; i++;
            // skip the sign after e/E
            if (i<length && isSign(num.charAt(i))) i++;
        }
    
        // Check the numbers after 'e' / 'E' and sign
        while (i<length && isNum(num.charAt(i))) {hasNum = true; i++;}
    
        // Skip all the trailing spaces
        while (i<length && isSpace(num.charAt(i))) i++;
    
        /* After processing the main decimal number and trailing spaces, 
        if more Characters are left then the number is not Valid or
        if the string doesn't consist of numbers*/
        return i == length && hasNum;
    }
  
  public static void main (String[] args) throws java.lang.Exception
  {
    int n = 14;
        String num;
        
        Scanner sc = new Scanner(System.in);
        while(n-- > 0)
        {
            /* input should accept a string with whitespaces */
            num = sc.nextLine();
            if(isNumber(num))
            System.out.println("Valid decimal number");
            else
            System.out.println("Invalid decimal number");
        }
  }
}
0
 0.1 
abc
1 a
2e10
 -90e3   
 1e
e3
 6e-1
 99e2.5 
53.5e93
 --6 
-+3
95a54e53
Valid decimal number
Valid decimal number
Invalid decimal number
Invalid decimal number
Valid decimal number
Valid decimal number
Invalid decimal number
Invalid decimal number
Valid decimal number
Invalid decimal number
Valid decimal number
Invalid decimal number
Invalid decimal number
Invalid decimal number

Complexity Analysis

  1. Time Complexity : T(n) = O(n), n = length of the input string.
  2. Space Complexity : A(n) = O(1)

Regex

Approach

A valid decimal number string has a fixed pattern of valid characters as discussed in the approach section of the string processing section. Therefore, we can define a regex for a valid decimal string and match it with the input string to check the validity of the input string as a decimal number.

Implementation

Java Program
import java.util.*;
import java.lang.*;
import java.io.*;

class TutorialCup
{
  static boolean isNumber(String num)
    {
        // trim the leading and trailing spaces and match the input string with a predefined regex
        return num.trim().matches("[+-]?(\\d+(\\.\\d*)?|\\.\\d+)(e[+-]?\\d+)?");
    }
  
  public static void main (String[] args) throws java.lang.Exception
  {
    int n = 14;
        String num;
        
        Scanner sc = new Scanner(System.in);
        while(n-- > 0)
        {
            /* input should accept a string with whitespaces */
            num = sc.nextLine();
            if(isNumber(num))
            System.out.println("Valid decimal number");
            else
            System.out.println("Invalid decimal number");
        }
  }
}
0
 0.1 
abc
1 a
2e10
 -90e3   
 1e
e3
 6e-1
 99e2.5 
53.5e93
 --6 
-+3
95a54e53
Valid decimal number
Valid decimal number
Invalid decimal number
Invalid decimal number
Valid decimal number
Valid decimal number
Invalid decimal number
Invalid decimal number
Valid decimal number
Invalid decimal number
Valid decimal number
Invalid decimal number
Invalid decimal number
Invalid decimal number

Complexity Analysis

  1. Time Complexity : T(n) = O(n), n = length of the input string.
  2. Space Complexity : A(n) = O(1)

References

Translate ยป