String angka bisa berisi sign, titik desimal, dan exponent. Posisi ketiganya menentukan apakah string itu valid. Aku mencoba empat pendekatan sebelum akhirnya memilih yang paling jelas.
Parser harus menerima "2", "-0.1", "4.", dan "2e10", tapi menolak "abc", "1e", dan "99e2.5". Aturannya cukup kecil untuk membandingkan regex, parser, state machine, dan empat boolean flag.
Format angka yang valid
Grammar input-nya punya dua kelompok contoh:
Yang ini harus lolos:
- Integer biasa: "2", "0089"
- Angka dengan sign: "-0.1", "+3.14"
- Angka desimal: "4.", "-.9", ".1"
- Angka dengan exponent: "2e10", "-90E3", "3e+7"
Yang ini nggak boleh lolos:
- "abc": nggak ada digit sama sekali
- "1e": exponent tanpa digit
- "99e2.5": nggak boleh ada desimal setelah exponent
- "--6": banyak sign sekaligus nggak masuk akal
- "1a", "e3", "95a54e53": campuran karakter yang valid dan nggak valid
Percobaan pertama: Regex
Aku mulai dengan regular expression karena format ini kelihatan seperti masalah pattern matching.
function isValidNumberNaive(s) {
const pattern = /^\s*[+-]?(\d+\.?\d*|\.\d+)([eE][+-]?\d+)?\s*$/;
return pattern.test(s);
}
Pattern ini cocok dengan contoh-contoh awal. Kalau diurai, pattern-nya seperti ini:
^\s*: Lewati whitespace di awal[+-]?: Plus atau minus yang opsional(\d+\.?\d*|\.\d+): Bagian angka (digit dengan desimal opsional, ATAU desimal dengan digit)([eE][+-]?\d+)?: Bagian exponent yang opsional\s*$: Lewati whitespace di akhir
Pattern-nya ringkas, tapi aturannya susah diperiksa. Kalau requirement-nya berubah, aku harus memeriksa ulang setiap quantifier dan alternatifnya. Match yang gagal juga bakal susah didiagnosis.
Analisis Performa: Pendekatan Regex
Pattern yang pendek nggak menjamin scan yang linear. V8 menjelaskan bagaimana engine backtracking mereka mencoba alternatif lain setelah match gagal.
Time Complexity: Berpotensi O(n²) karena backtracking
Di pattern ini, \d+ dan \d* sama-sama bisa memakan deretan digit yang sama kalau titik desimal opsionalnya nggak ada. Deretan digit yang panjang lalu diikuti karakter yang nggak valid bisa bikin engine mencoba ulang banyak cara membagi digit-digit itu. Optimasi engine atau algoritma matching yang lain bisa mengubah perilaku ini.
Space Complexity: Tergantung engine
Pattern yang dioper ke .test() ukurannya konstan, tapi itu nggak menentukan working memory dari matcher-nya. Engine-nya mungkin menyimpan state backtracking.
Percobaan kedua: Parsing eksplisit
Lalu aku menulis grammar yang sama sebagai langkah-langkah parsing yang eksplisit:
function isValidNumberBetter(s) {
// Step 1: Skip leading whitespace
let i = 0;
while (i < s.length && s[i] === " ") i++;
if (i >= s.length) return false;
// Step 2: Check for optional sign
if (s[i] === "+" || s[i] === "-") i++;
let hasNumber = false;
let hasDot = false;
// Step 3: Parse digits before decimal
while (i < s.length && /[0-9]/.test(s[i])) {
hasNumber = true;
i++;
}
// Step 4: Parse optional decimal part
if (i < s.length && s[i] === ".") {
hasDot = true;
i++;
while (i < s.length && /[0-9]/.test(s[i])) {
hasNumber = true;
i++;
}
}
// Step 5: We need at least one digit
if (!hasNumber) return false;
// Step 6: Parse optional exponent
if (i < s.length && (s[i] === "e" || s[i] === "E")) {
i++;
if (i < s.length && (s[i] === "+" || s[i] === "-")) i++;
let exponentHasNumber = false;
while (i < s.length && /[0-9]/.test(s[i])) {
exponentHasNumber = true;
i++;
}
if (!exponentHasNumber) return false;
}
// Step 7: Skip trailing whitespace
while (i < s.length && s[i] === " ") i++;
return i === s.length;
}
Parser-nya pertama melewati spasi dan membaca sign yang opsional. Lalu dia mem-parse angka, bagian desimal, dan exponent. Pengecekan terakhir menolak karakter yang masih tersisa. Contoh-contohnya lolos, tapi menurut aku fase-fase yang terpisah ini susah diikuti sebagai satu aturan validasi.
Analisis Performa: Pendekatan Step by Step
Time Complexity: O(n)
- Aku pakai satu index
iyang bergerak dari awal sampai akhir string - Setiap karakter diperiksa tepat satu kali
- Nggak ada nested loop yang bakal melipatgandakan kerjanya
- Loop while-nya berurutan, bukan nested
Space Complexity: O(1)
- Aku cuma pakai beberapa variabel boolean (
hasNumber,hasDot) dan integer (i) - Ukurannya nggak bertambah seiring ukuran input. Space-nya konstan
- Nggak ada array atau struktur data yang membesar seiring input
Percobaan ketiga: State machine
State machine mewakili bagian input yang udah dibaca parser. Setiap karakter memindahkannya ke state yang diizinkan atau membuat input nggak valid. Cuma state tertentu yang boleh menjadi akhir angka valid.
function isValidNumberOptimized(s) {
// Define all possible states
const State = {
START: 0, // Initial state
SIGN: 1, // Just read a sign
INTEGER: 2, // Reading integer digits
DOT: 3, // Just read a dot
DECIMAL: 4, // Reading decimal digits
EXPONENT: 5, // Just read exponent
EXPONENT_SIGN: 6, // Reading exponent sign
EXPONENT_NUMBER: 7, // Reading exponent digits
END: 8, // Valid ending state
};
// Define state transitions
const transitions = {
[State.START]: {
digit: State.INTEGER,
"+": State.SIGN,
"-": State.SIGN,
".": State.DOT,
" ": State.START,
},
[State.SIGN]: {
digit: State.INTEGER,
".": State.DOT,
},
[State.INTEGER]: {
digit: State.INTEGER,
".": State.DECIMAL,
e: State.EXPONENT,
E: State.EXPONENT,
" ": State.END,
},
[State.DOT]: {
digit: State.DECIMAL,
},
[State.DECIMAL]: {
digit: State.DECIMAL,
e: State.EXPONENT,
E: State.EXPONENT,
" ": State.END,
},
[State.EXPONENT]: {
digit: State.EXPONENT_NUMBER,
"+": State.EXPONENT_SIGN,
"-": State.EXPONENT_SIGN,
},
[State.EXPONENT_SIGN]: {
digit: State.EXPONENT_NUMBER,
},
[State.EXPONENT_NUMBER]: {
digit: State.EXPONENT_NUMBER,
" ": State.END,
},
[State.END]: {
" ": State.END,
},
};
let currentState = State.START;
// Process each character
for (let char of s) {
let charType = "";
// Categorize the character
if (char >= "0" && char <= "9") {
charType = "digit";
} else if (char === "+" || char === "-") {
charType = char;
} else if (char === ".") {
charType = ".";
} else if (char === "e" || char === "E") {
charType = "e";
} else if (char === " ") {
charType = " ";
} else {
return false;
}
// Check if transition is valid
if (
!transitions[currentState] ||
!Object.prototype.hasOwnProperty.call(transitions[currentState], charType)
) {
return false;
}
// Move to next state
currentState = transitions[currentState][charType];
}
// Check if we ended in a valid state
return [
State.INTEGER,
State.DECIMAL,
State.EXPONENT_NUMBER,
State.END,
].includes(currentState);
}
Tabel ini membuat transisi yang diizinkan jadi eksplisit. Setiap state merepresentasikan apa yang udah muncul sejauh ini, dan setiap transisi menentukan apa yang boleh datang berikutnya.
Untuk grammar ini, menurutku tabel transisi lebih sulit dirawat daripada parser eksplisit. Untuk mencari penyebab input ditolak, aku harus mengikuti klasifikasi karakter sekaligus transisinya.
Analisis Performa: Pendekatan State Machine
Time Complexity: O(n)
- Aku memproses setiap karakter tepat satu kali di for loop utama
- Setiap kategorisasi karakter dan transisi state itu O(1)
- Pengecekan state akhir dengan
.includes()itu O(1) karena cuma mengecek array tetap berisi 4 state - Secara keseluruhan: n karakter × operasi O(1) = O(n)
Space Complexity: O(1)
- Object
Statedan objecttransitionsukurannya konstan (9 state, jumlah transisi tetap) currentStateadalah numbercharTypeadalah string, tapi panjangnya terbatas (maksimal "EXPONENT_NUMBER", yang konstan)- Walaupun aku membuat object-object ini sekali, ukurannya nggak bertambah seiring ukuran input
Tradeoff:
- Kelebihan: Transisi yang eksplisit dan himpunan state yang tetap
- Kekurangan: Kode dan indirection yang lebih banyak dari yang dibutuhkan grammar ini, dengan kegagalan yang tersebar di seluruh tabel transisi
- Kapan berguna: Kalau aturan validasinya punya cukup banyak state sampai tabel transisi bikin aturannya lebih jelas
Scan-nya tetap O(n). Perbandingan ini nggak menyertakan benchmark runtime, jadi keputusannya bergantung pada readability dan seberapa banyak state yang dibutuhkan aturannya.
Solusi akhir: Boolean flags
Implementasi akhirnya melacak empat fakta tentang input dengan boolean flags. Cara ini bikin aturannya tetap kelihatan tanpa tabel transisi dari percobaan sebelumnya.
function isValidNumber(s) {
// Remove leading and trailing whitespace
s = s.trim();
// Track what we've seen with simple boolean flags
let seenDigit = false; // Have we seen any digits?
let seenDot = false; // Have we seen a decimal point?
let seenE = false; // Have we seen an exponent?
let digitAfterE = true; // Do we have digits after the exponent?
for (let i = 0; i < s.length; i++) {
const currentChar = s[i];
if (/[0-9]/.test(currentChar)) {
// Found a digit
seenDigit = true;
if (seenE) {
// If we're after an exponent, mark that we have digits
digitAfterE = true;
}
} else if (currentChar === "+" || currentChar === "-") {
// Sign can only appear at start or right after 'e'/'E'
if (i > 0 && s[i - 1] !== "e" && s[i - 1] !== "E") {
return false;
}
} else if (currentChar === ".") {
// Can't have multiple dots or dots after exponent
if (seenDot || seenE) return false;
seenDot = true;
} else if (currentChar === "e" || currentChar === "E") {
// Can't have multiple exponents or exponent without digits
if (seenE || !seenDigit) return false;
seenE = true;
digitAfterE = false; // Reset flag for exponent part
} else {
// Any other character is invalid
return false;
}
}
// Valid if: we saw digits AND (no exponent OR digits after exponent)
return seenDigit && digitAfterE;
}
Setiap flag mencatat satu kondisi, jadi aku bisa menelusuri input yang ditolak ke pengecekan yang gagal. Loop memproses input sekali.
Analisis Performa: Pendekatan Boolean Flags (Solusi Akhir)
Time Complexity: O(n)
- Aku mengiterasi setiap karakter tepat satu kali dengan for loop
- Semua operasi di dalam loop itu O(1): perbandingan, assignment, pengecekan boolean
- Operasi
.trim()itu O(n), tapi itu tertutupi oleh loop utama yang juga O(n) - Total: O(n) + O(n) = O(n)
Space Complexity: O(n) di implementasi ini
- State parser-nya pakai 4 variabel boolean dan satu index loop, jadi bagian itu O(1)
s.trim()bisa mengalokasikan salinan input yang udah dinormalisasi, yang butuh O(n) extra space di worst case- Trim berbasis index bisa menjaga state parser dan extra space keseluruhannya tetap O(1), tapi itu bukan implementasi yang ditunjukkan di sini
Yang dijamin versi ini:
- Linear time: Kamu nggak bisa lebih baik dari O(n) karena kamu perlu memeriksa setiap karakter
- State parser yang terbatas: Flag dan index loop tetap O(1), walaupun
trim()bikin implementasi ini butuh O(n) extra space di worst case
Ringkasan Perbandingan Kompleksitas
| Pendekatan | Time Complexity | Space Complexity | Maintainability |
|---|---|---|---|
| Regex | Berpotensi O(n²) karena backtracking | Tergantung engine | Rendah |
| Step-by-step | O(n) | O(1) | Sedang |
| State machine | O(n) | O(1) | Rendah |
| Boolean flags | O(n) | O(n) | Tinggi |
Pendekatan-pendekatan ini berbeda dalam cara merepresentasikan grammar dan mengalokasikan memori. Pendekatan boolean flags punya state parser yang paling jelas, sementara pemanggilan trim() di dalamnya menambah O(n) extra space di worst case.
Tes input valid dan nggak valid
Contoh-contoh ini mencakup bentuk valid dan nggak valid yang utama:
const testCases = [
{ input: "0", expected: true },
{ input: "e", expected: false },
{ input: ".", expected: false },
{ input: " 0 ", expected: true },
{ input: " 0.1 ", expected: true },
{ input: "2e10", expected: true },
{ input: "abc", expected: false },
{ input: "1a", expected: false },
{ input: "1e", expected: false },
{ input: "99e2.5", expected: false },
];
testCases.forEach(({ input, expected }) => {
const result = isValidNumber(input);
console.log(
`"${input}" -> ${result} (expected ${expected}) ${
result === expected ? "✓" : "✗"
}`
);
});
Kasus exponent menunjukkan kenapa setiap flag punya tugas terpisah:
Contoh 1: "2e10" (harusnya valid)
- Awal: seenDigit=false, seenDot=false, seenE=false, digitAfterE=true
- '2' → seenDigit = true
- 'e' → seenE = true, digitAfterE = false (di-reset untuk exponent)
- '1' → seenDigit = true, digitAfterE = true (ketemu digit setelah exponent)
- '0' → seenDigit = true, digitAfterE = true
- Akhir: seenDigit=true AND digitAfterE=true → return true ✓
Contoh 2: "1e" (harusnya nggak valid)
- Awal: seenDigit=false, seenDot=false, seenE=false, digitAfterE=true
- '1' → seenDigit = true
- 'e' → seenE = true, digitAfterE = false (di-reset untuk exponent)
- Akhir: seenDigit=true AND digitAfterE=false → return false ✗
Contoh 3: "99e2.5" (harusnya nggak valid)
- Awal: seenDigit=false, seenDot=false, seenE=false, digitAfterE=true
- '9' → seenDigit = true
- '9' → seenDigit = true
- 'e' → seenE = true, digitAfterE = false
- '2' → seenDigit = true, digitAfterE = true
- '.' → langsung return false (nggak boleh ada desimal setelah exponent) ✗
Untuk grammar ini, aku akan mempertahankan versi boolean flags. Aku bisa mengikuti alasan setiap penolakan tanpa menelusuri tabel transisi, sementara biaya memori trim() tetap tercatat dalam analisis kompleksitas.

Memuat komentar...