Daily bit(e) of C++ | Number validator
Daily bit(e) of C++ #70, Common C++ interview problem: number validator
Today we will look at a common C++ interview problem: Number validator.
Given a potential number as a string, determine whether the string contains (only) a valid decimal number.
The format for a number is (in this order):
decimal number or integer
optional: “e” or “E” followed by an integer
An integer is:
optional: sign “+-”
one or more digits (leading zeroes are OK)
A decimal number is:
optional: sign “+-”
one of the following formats:
one or more digits followed by “.”
one or more digits followed by “.” followed by one or more digits
“.” followed by one or more digits
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/KoKsnvveY.
Solution
As is typical with this type of problem, there is very little to discuss from the algorithmic standpoint, only that we should strive to process the input in one pass.
The main test with these types of problems is problem decomposition and diligence. Fortunately, the problem specification is complete and hints at potential problem decomposition.
One fairly easy way to process a string in one pass in C++ is using iterators, and we can start with the most repeated phrase in the specification: “one or more digits”.
We try to parse a number and return an iterator after the parsed part. This has two benefits: we can easily detect failure on the calling site and easily continue parsing.
Parsing an integer is then simply a matter of adding an optional sign:
The code for parsing the entire decimal is the most complex part of the problem, as we have the three potential formats around the decimal separator and an optional exponent part:
Finally, to return a boolean answer, we need to check whether we have parsed the entirety of the input:
