← Parsing · guided lesson
String Parsing & Expression Evaluation
the story
Finite-state machine (a scanner with states)
Every tool here exists because something was too slow or broke without it. Here is what.
In a 1951 RAND memo, logician Stephen Kleene studied which patterns of input a machine with a fixed, finite memory can recognise. His "regular events" are the idea behind today's regular expressions; the memo was printed in Automata Studies in 1956. In 1959 Michael Rabin and Dana Scott published "Finite Automata and Their Decision Problems": a finite set of states, and a rule that picks the next state from the current state and the next symbol. The paper also introduced machines that may guess — nondeterministic automata. It won them the 1976 Turing Award. In 1968 Ken Thompson published a way to compile a regular expression into machine code for fast text search.
the problem it solved
Deciding, one character at a time and with a fixed amount of memory, whether input matches a pattern — and splitting it into pieces along the way.
why it matters: without it
Parsers would become deep if-else ladders that accept bad input like "+-12" or "1 2" — or re-read text again and again.
sources: Kleene — Representation of Events in Nerve Nets and Finite Automata (RAND RM-704, 1951) ↗ · Rabin & Scott — Finite Automata and Their Decision Problems (IBM J. Res. Dev., 1959) ↗ · Heidelberg Laureate Forum — Michael O. Rabin (1976 Turing Award citation) ↗ · Thompson — Regular expression search algorithm (CACM, 1968) ↗
also in this chapter: Greedy value table (Roman numerals and other number systems) · Two stacks for precedence (Dijkstra's shunting-yard) · Recursive descent (one method per grammar rule) · Length-prefixed framing · Greedy line filling (and Knuth–Plass, its optimal cousin)
the idea
The idea in 30 seconds
Parsing means walking the text once with an index and deciding what each character means from what came before it.
Small inputs need a few states (spaces → sign → digits). Formulas need precedence: two stacks, or one method per grammar rule.
When many strings must travel as one, write each one's length in front of it. Then no character inside can fool the reader.
picture this
Type =2+3*4 into an Excel cell and it shows 14, not 20: * binds tighter than +. To get that right while reading left to right, a parser must hold the + aside until the * is done. Every parser in this chapter works like that: one cursor, a little memory of what is waiting, and rules for when it may run.
watch it
atoi as a state machine
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
atoi as a state machine
Spaces, one sign, digits, stop. The guard runs before every append, so the int never overflows.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
A greedy value table
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
A greedy value table
13 rows, biggest first. The six subtractive pairs live in the table, so 'take the biggest that fits' always writes a standard numeral.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 9
Read it once. Say it out loud once. Bas.
One cursor, one pass. Keep an index i, read s.charAt(i), move forward. Read whole tokens: a number is num = num * 10 + (c - '0') in a loop, not one digit.
key idea 2 of 9
Read it once. Say it out loud once. Bas.
States. When a character's meaning depends on what came before it (a sign only before digits), you are writing a finite-state machine — as if-statements or as a table.
key idea 3 of 9
Read it once. Say it out loud once. Bas.
Overflow before it happens: if (result > (Integer.MAX_VALUE - d) / 10) clamp; only then result = result * 10 + d.
key idea 4 of 9
Read it once. Say it out loud once. Bas.
Greedy value tables turn numbers into symbols: Roman numerals, lakh/crore words, h/m/s. Take the biggest value that fits, repeat.
key idea 5 of 9
Read it once. Say it out loud once. Bas.
Precedence with two stacks (Dijkstra's shunting-yard): an operator waits on a stack until an operator of lower or equal precedence, or a ), arrives. Or use recursive descent: expr → term → factor.
key idea 6 of 9
Read it once. Say it out loud once. Bas.
No brackets, no stack: for + − * /, result holds the finished terms and last holds the term that * and / can still change.
key idea 7 of 9
Read it once. Say it out loud once. Bas.
In-place text tricks: reverse everything, then reverse each piece back (words here, the two parts of a rotation in Rotate Array).
key idea 8 of 9
Read it once. Say it out loud once. Bas.
Framing: to pack strings into one, write length#string. The reader jumps by the length, so a separator inside the data is harmless.
key idea 9 of 9
Read it once. Say it out loud once. Bas.
Greedy line filling gives the fewest lines. Spacing is arithmetic: spaces / gaps each, and the first spaces % gaps gaps get one more.
spot the pattern
When you see this, think this
"Implement atoi", "parse this number", "is this a valid number"
A small state machine: spaces → sign → digits (→ '.' → exponent), with an overflow guard
"Evaluate the expression" with + − * / and maybe brackets
Two stacks (shunting-yard), result + last when there are no brackets, or recursive descent
Only + and − with brackets and a unary minus
Running total + a stack of (result, sign) pairs
Roman numerals, "amount in words", seconds → h:m:s
Greedy value table, biggest first
+4 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Reading one digit at a time:
12+3becomes 1, 2, +, 3. Loop over all the digits of a number. - Checking overflow after
result * 10 + d: by then the int has already wrapped round.
quick check
One question. No pressure.
What does atoi return for " -0012a42"?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Roman to Integer
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
atoi: in what order are the parts of the input read?
Question 1: atoi: in what order are the parts of the input read?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.