Is the Number Valid

Problem Statement

Given an input string, determine if it makes a valid number or not. For simplicity, assume that white spaces are not present in the input.

4.325 is a valid number.
1.1.1 is NOT a valid number.
222 is a valid number.
22. is NOT a valid number.
0.1 is a valid number.
22.22. is NOT a valid number.
1. is NOT a valid number.

Hint

• Use state machine

Try it yourself

bool is_number_valid(string s) {
//TODO: Write - Your - Code
return false;
}

Solution

enum STATE { START, INTEGER, DECIMAL, UNKNOWN, AFTER_DECIMAL};

STATE get_next_state(STATE current_state, char ch) {
switch(current_state) {
case START:
case INTEGER: {
if (ch == '.') {
return DECIMAL;
} else if (ch >= '0' && ch <= '9') {
return INTEGER;
} else {
return UNKNOWN;
}
break;
}

case DECIMAL:
if (ch >= '0' && ch <= '9') {
return AFTER_DECIMAL;
} else {
return UNKNOWN;
}
break;

case AFTER_DECIMAL:
if (ch >= '0' && ch <= '9') {
return AFTER_DECIMAL;
} else {
return UNKNOWN;
}
break;

case UNKNOWN:
return UNKNOWN;
}
return UNKNOWN;
}

bool is_number_valid(const string s) {
int i = 0;
if (s[i] == '+' || s[i] == '-') {
i++;
}
STATE current_state = START;
while (s[i] != '\0') {
current_state = get_next_state(current_state, s[i]);
if (current_state == UNKNOWN) {
return false;
}
i++;
}

if (current_state == DECIMAL)
return false;

return true;
}

void test(const string s, bool expected) {
bool is_valid = is_number_valid(s);
if (is_valid) {
cout << s << " is valid." << endl;
} else {
cout << s << " is not valid." << endl;
}
}

int main(int argc, char* argv[]) {
test("4.325", true);
test("4.325a", false);
test("x4.325", false);
test("4.32.5", false);
test("4325", true);
test("1.", false);
test("1.1.", false);
test("1.1.1", false);
test("1.1.1.", false);
test("+1.1.", false);
test("+1.1", true);
test("-1.1.", false);
test("-1.1", true);
test("", true);
}

Solution Explanation

Linear, O(n).

Constant, O(1).

Solution Breakdown

We’ll use the state machine below to check if a number is valid or not. The initial state is ‘Start’. We’ll process each character to identify the next state. The input string is not a valid number if we reach an UNKNOWN state at any point or if it ends in a DECIMAL.

We are not looking at the sign (+ or -) at the start of a number in the state machine. If there is a sign at the start of the input string, we start processing the string for the state machine after that sign character.

Learn in-demand tech skills in half the time