20

String Parsing & Expression Evaluation

Read text the way a compiler does: one cursor, a few states, and a stack when things nest.

intermediate~70 min5 simulations8 problems

▶ guided lesson⚡ 1-minute summary↻ 14 recall cards

before this: Java Arrays & Strings · Math & Numbers · Two Pointers · Stacks · Recursion

01 · why it exists

Why this exists, and the weight it carries

since1951–1959

Finite-state machine (a scanner with states)

Stephen C. Kleene; Michael O. Rabin & Dana Scott

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 solvedDeciding, 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.

its jobs today

  • Lexers: compilers, JSON readers and CSV parsers first cut text into tokens with a small state machine.
  • Regular expressions: compile the pattern once (Pattern.compile in Java), then match text against it — classic engines turn the pattern into a state machine.
  • App flows with legal moves only: an order screen goes placed → preparing → out for delivery → delivered, never backwards.

the weight it carries

Illustrative: a 1 MB JSON response, 10⁶ characters. A scanner with states reads each character once: 10⁶ steps and O(1) extra memory. A scanner that backs up and re-reads the current token at every character needs up to n²/2 = 5·10¹¹ steps on one long token.

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.

when · why · how

when
Text arrives character by character and a character's meaning depends on what came before it: a sign only before digits, digits after a '.', a quote after a backslash.
why
O(1) work per character → O(n) time and O(1) extra space, and each state has a small set of legal next characters that you can check one by one.
how
An int state plus a switch, or a table int[][] NEXT = new int[states][charClasses]; read with s.charAt(i) in one forward pass.

02 · plain english

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.

03 · remember

What you must know

  • 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.
  • 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.
  • Overflow before it happens: if (result > (Integer.MAX_VALUE - d) / 10) clamp; only then result = result * 10 + d.
  • Greedy value tables turn numbers into symbols: Roman numerals, lakh/crore words, h/m/s. Take the biggest value that fits, repeat.
  • 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.
  • No brackets, no stack: for + − * /, result holds the finished terms and last holds the term that * and / can still change.
  • In-place text tricks: reverse everything, then reverse each piece back (words here, the two parts of a rotation in Rotate Array).
  • Framing: to pack strings into one, write length#string. The reader jumps by the length, so a separator inside the data is harmless.
  • Greedy line filling gives the fewest lines. Spacing is arithmetic: spaces / gaps each, and the first spaces % gaps gaps get one more.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

atoi as a state machine

Spaces, one sign, digits, stop. The guard runs before every append, so the int never overflows.

loading simulation…
sim

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.

loading simulation…
sim

Precedence with two stacks

Values wait in nums, operators in ops. An operator runs only when something of lower or equal precedence, a ')' or the end arrives.

loading simulation…
sim

Length-prefixed framing

Encode writes len#text for each string; decode reads the header, then jumps over exactly len characters without looking at them.

loading simulation…
sim

Greedy line filling

Take words while they fit, then share the spare spaces with / and %. Every row of the grid is exactly maxWidth wide.

loading simulation…

05 · cost

Time & space, explained

The problems in this chapter (n = input length)
Brute forceOptimal timeOptimal extra spacewhy
String to Integer (atoi)O(n), copies the digitsO(n)O(1)Each character is read once. The guard replaces a long or BigInteger, so nothing is copied.
Roman to IntegerO(n), six rewritesO(n), n ≤ 15O(1)Peek one symbol ahead and add or subtract; the brute force builds six new strings first.
Integer to RomanO(1), additive + six rewritesO(1)O(1)At most 13 table rows and 15 symbols for any value 1..3999.
Reverse Words in a StringO(n²), prependingO(n)O(1) beyond the char[]Prepending copies the whole answer per word; reversing touches each character about twice.
Basic Calculator IIO(n²), collapsing a listO(n)O(1)ArrayList removals shift the tail; result + last never looks back.
Basic CalculatorO(n²), rewriting bracketsO(n)O(depth)Each rewrite rebuilds the string; the sign stack holds one pair per open bracket.
Text Justification (L lines, width W)O(L·W²), inserting spacesO(L·W)O(W) per lineStringBuilder.insert shifts the line every time; computing each gap's width writes each character once.
Encode and Decode Strings (N total chars)O(N), escapingO(N)O(N), the outputBoth are linear, but escaping inspects every character; length prefixes jump over the payload.
Two ways to evaluate infix with precedence
Two stacks (shunting-yard)Recursive descentwhy
TimeO(n)O(n)Each token is pushed and popped at most once, or read once by exactly one method.
Extra spaceO(n) on the heapO(depth) on the call stackVery deep nesting is safe in a Deque; recursion can throw StackOverflowError.
Unary minuspush 0 when no value comes before '-'factor := '-' factorBoth turn -x into 0 − x (or −x) without special cases elsewhere.
A new precedence level (e.g. ^)one more case in prec()one more method in the chainBoth are small changes; the recursive version reads like the grammar.

06 · java

Raw vs Collections Framework

Scanning: a cursor vs split

javaone index, one passjava.util.*
/** "12+ 345*(6-7)" → [12, +, 345, *, (, 6, -, 7, )]. One index walks the string once. */static List<String> tokens(String s) {    List<String> out = new ArrayList<>();    int i = 0;    while (i < s.length()) {        char c = s.charAt(i);        if (c == ' ') {            i++;                                        // spaces only separate tokens        } else if (c >= '0' && c <= '9') {            int start = i;            while (i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9') i++; // a whole number            out.add(s.substring(start, i));        } else {            out.add(String.valueOf(c));                 // an operator or a bracket is one char            i++;        }    }    return out;}
  • The cursor version reads a whole number with an inner while and never needs separators: 12+ 345*(6-7) works.
  • split("\\s+") only works when every token is separated by spaces: 12+345*6 comes back as one token.
  • split takes a regex and makes a new String per piece. The split traps (split("."), trailing empty strings) are in the Java Arrays & Strings chapter.
  • Test digits with c >= '0' && c <= '9'. Character.isDigit also says yes to other scripts' digits, like Devanagari '५'.

Reading a number: your own loop vs Integer.parseInt

javaloop + overflow guard (atoi)
class Solution {    public int myAtoi(String s) {        int i = 0, n = s.length();        while (i < n && s.charAt(i) == ' ') i++; // state 1: skip leading spaces        int sign = 1;        if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) { // state 2: at most one sign            sign = s.charAt(i) == '-' ? -1 : 1;            i++;        }        int result = 0;        while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') { // state 3: digits            int d = s.charAt(i) - '0';            if (result > (Integer.MAX_VALUE - d) / 10) { // result * 10 + d would pass 2^31 - 1                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;            }            result = result * 10 + d;            i++;        }        return sign * result; // any other character ends the number    }}
  • result > (Integer.MAX_VALUE - d) / 10 is exactly the condition for result * 10 + d > 2³¹ − 1, checked before anything can wrap.
  • Integer.parseInt is strict: a space, a letter or an out-of-range value throws NumberFormatException. It accepts a leading '+' (since Java 7) or '-'.
  • Because it reads digits with Character.digit, Integer.parseInt("१२") returns 12 — your own loop decides what counts as a digit.
  • Math.multiplyExact / Math.addExact are another option: they throw ArithmeticException on overflow instead of wrapping.

Precedence: two stacks vs recursive descent

javashunting-yard (two stacks)java.util.*
/** + - * / and brackets on non-negative ints; a '-' at the start or right after '(' is unary. */static int evaluate(String s) {    Deque<Integer> nums = new ArrayDeque<>(); // values waiting for an operator    Deque<Character> ops = new ArrayDeque<>(); // operators waiting for their right operand    boolean expectValue = true; // true at the start and right after '('    for (int i = 0; i < s.length(); i++) {        char c = s.charAt(i);        if (c == ' ') continue;        if (c >= '0' && c <= '9') {            int num = 0;            while (i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9') num = num * 10 + (s.charAt(i++) - '0');            i--; // the for loop will step past the last digit            nums.push(num);            expectValue = false;        } else if (c == '(') {            ops.push(c); // a wall: nothing inside may reach past it            expectValue = true;        } else if (c == ')') {            while (ops.peek() != '(') apply(nums, ops.pop()); // finish the group            ops.pop(); // drop the '(' itself            expectValue = false;        } else {            if (expectValue) nums.push(0); // unary minus: "-x" is "0 - x"            // Before c waits, run every operator on the stack that binds at least as tightly.            while (!ops.isEmpty() && ops.peek() != '(' && prec(ops.peek()) >= prec(c)) {                apply(nums, ops.pop());            }            ops.push(c);            expectValue = true;        }    }    while (!ops.isEmpty()) apply(nums, ops.pop());    return nums.pop();} static int prec(char op) {    return op == '*' || op == '/' ? 2 : 1;} static void apply(Deque<Integer> nums, char op) {    int b = nums.pop(), a = nums.pop(); // the right operand comes off first    nums.push(switch (op) {        case '+' -> a + b;        case '-' -> a - b;        case '*' -> a * b;        default -> a / b;    });}
  • Two stacks: before pushing an operator, apply every waiting operator with precedence ≥ it. The = keeps 8 − 3 − 2 left to right.
  • ( is a wall on the ops stack; ) applies operators back to it. At the end, apply whatever is left.
  • Recursive descent: each grammar rule is a method. Lower rules bind tighter — term handles * and /, so it runs inside expr's + and −.
  • Use Deque<Integer> / Deque<Character> (ArrayDeque), never the legacy Stack class — see the Stacks chapter.

Number systems: a greedy value table

javatwo parallel arrays
class Solution {    // The 7 symbols plus the 6 subtractive pairs, biggest first.    private static final int[] VALUES = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};    private static final String[] SYMBOLS = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};     public String intToRoman(int num) {        StringBuilder sb = new StringBuilder();        for (int k = 0; k < VALUES.length; k++) {            while (num >= VALUES[k]) { // the biggest value that still fits                sb.append(SYMBOLS[k]);                num -= VALUES[k];            }        }        return sb.toString();    }}
  • Order matters: the table must go from the biggest value to the smallest.
  • floorEntry(num) returns the entry with the largest key ≤ num in O(log k) — a greedy table lookup in one call.
  • new TreeMap<>(Map.ofEntries(…)) sorts the table by key once. The arrays version is faster and is what interviewers expect.

Framing: your own length prefix vs DataOutputStream.writeUTF

javalen#text in a Stringjava.util.*
class Codec {    /** ["hi", "", "a#3"] → "2#hi0#3#a#3". Each string travels with its own length in front. */    public String encode(List<String> strs) {        StringBuilder sb = new StringBuilder();        for (String s : strs) {            sb.append(s.length()).append('#').append(s); // header "len#", then the raw text        }        return sb.toString();    }     public List<String> decode(String s) {        List<String> out = new ArrayList<>();        int i = 0; // always the start of a header        while (i < s.length()) {            int hash = s.indexOf('#', i); // a header is digits then '#': the first '#' ends it            int len = Integer.parseInt(s.substring(i, hash));            out.add(s.substring(hash + 1, hash + 1 + len)); // take exactly len chars, '#' or not            i = hash + 1 + len; // jump straight to the next header        }        return out;    }}
  • Decode finds the header with indexOf('#', i): headers are only digits, so the first # after i must end the header.
  • writeUTF writes two bytes of length, then the string in modified UTF-8. The length counts bytes: '₹' takes 3.
  • Two bytes can count up to 65,535, so a string whose encoding needs more bytes than that makes writeUTF throw UTFDataFormatException.
  • try (DataOutputStream out = …) closes the stream for you, even if a write throws.
Java API you will actually use
calldoescost
s.charAt(i)Read one char — the scanner's basic moveO(1)
c >= '0' && c <= '9' · c - '0'ASCII digit test, and its value 0–9O(1)
Character.isDigit(c) / isLetter(c)Unicode-aware tests (also true for '५')O(1)
Integer.parseInt(s) / Long.parseLong(s)Strict parse; throws NumberFormatException on spaces, junk or overflowO(len)
Math.addExact(a, b) / multiplyExact(a, b)Throw ArithmeticException on overflow instead of wrappingO(1)
s.indexOf(ch, from)First index of ch at or after from, or −1O(n)
s.substring(a, b)A new String with chars a..b−1O(b − a)
s.trim().split("\\s+")Words separated by runs of whitespace (trim first)O(n)
String.join(" ", words)Join with exactly one separatorO(total length)
" ".repeat(k)k spaces (Java 11+)O(k)
sb.append(x) / sb.insert(i, c)Append at the end / insert in the middle (shifts the rest)O(1) amortized / O(n)
new String(chars, 0, n)Build a String from the first n chars of a char[]O(n)
map.floorEntry(k)TreeMap: the entry with the largest key ≤ kO(log size)
out.writeUTF(s) / in.readUTF()2-byte length + modified UTF-8 bytes, and backO(len)

Numbers and operators from an expression

→ Index + while loop over digits

Handles 12+3 with no spaces; split can't.

Words separated by any number of spaces

→ s.trim().split("\\s+")

Short and clear when the pieces are all the same kind; trim first or you get an empty first word.

Text you trust to be a valid int

→ Integer.parseInt

Strict and fast; catch NumberFormatException where the text enters your program.

A forgiving atoi-style parse that clamps

→ Your own loop + overflow guard

parseInt won't skip leading spaces or stop at junk, and it throws instead of clamping.

Infix with precedence and brackets

→ Two stacks, or expr / term / factor

Both O(n). Recursion reads like the grammar; stacks never overflow the call stack.

+ − * / without brackets

→ result + last (no stack)

Only the current term can still change, so one variable replaces the stack.

Many strings inside one string or byte stream

→ Length prefix (len#s) or writeUTF

No escaping, and any character is safe.

A number in units from a fixed table

→ Parallel arrays biggest-first, or TreeMap.floorEntry

O(table size) per number, and adding a unit is one more row.

07 · recognise

Spot the pattern

"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

"Reverse the words" or "rotate" text in place

Reverse everything, then reverse each piece back

"Exactly maxWidth characters per line", word wrap

Greedy line filling, then spaces / gaps and spaces % gaps

"Encode a list of strings into one string", "serialize"

Length-prefix framing (len#s), never a bare delimiter

Something like k[...] or (...) that nests

A stack of saved contexts, or recursion with a shared index (Stacks chapter)

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

  • Reading one digit at a time: 12+3 becomes 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.
  • Character.isDigit accepts '५' and other Unicode digits, and then c - '0' is garbage. Compare with '0' and '9'.
  • charAt(i) without checking i < n first: a lone "-" or a number at the very end throws StringIndexOutOfBoundsException.
  • Forgetting the last number: in a one-pass calculator nothing comes after it, so commit at i == n − 1 or after the loop.
  • Popping only operators of higher precedence: 8 − 3 − 2 then becomes 8 − (3 − 2) = 7. Equal precedence must pop too.
  • s.split(" ") on text with repeated spaces returns empty strings; a leading space gives an empty first word.
  • Joining strings with a delimiter you hope never appears: some input always contains it.

tricks

  • Before coding, write the states or the grammar in 3 lines. The code is then a translation, and the interviewer can follow it.
  • Keep one cursor i that only moves forward. If a helper reads a number, let it advance i (or return where it stopped).
  • Test the boring inputs aloud: empty, only spaces, only a sign, a number at the very end, 2147483647 and 2147483648.
  • For calculators, say the rule out loud: "* and / change the current term; + and − start a new one."
  • In an interview, ask before you code: unary minus? spaces? brackets? truncating division? clamp or throw on overflow?
  • Chalo, dry-run karte hain: trace 3+5*2-8/3 in the result + last sim before writing a single line.

09 · why & how

Questions you might be too shy to ask

Why not just use split everywhere?

split is great when every piece is separated the same way and you treat them all alike, like words in a sentence. It can't tokenise 12+3*4 (there are no separators), it makes a new String per piece, and its argument is a regex — in a regex . means "any character", so every character becomes a separator and "a.b".split(".") returns an empty array (you need split("\\.")). A cursor loop is O(n), allocates nothing extra and follows any rule you need.

How does num = num * 10 + (c - '0') turn "345" into the number 345?

A char is stored as a number: '0' is 48, '1' is 49, … '9' is 57. So '3' - '0' is 51 − 48 = 3, the digit's value — while (int) '3' would give 51. Then each new digit pushes the old ones one place left: 0 → 0 × 10 + 3 = 3 → 3 × 10 + 4 = 34 → 34 × 10 + 5 = 345. Simple hai: multiply by 10 to make room, then add the new digit.

Why must i < n come first in while (i < n && s.charAt(i) == ' ')?

&& stops as soon as its left side is false, so s.charAt(i) never runs once i == n. Swap the two sides and, at the end of the text, the loop reads s.charAt(n), which throws StringIndexOutOfBoundsException. Inputs like " " (only spaces) or "-" (a sign, then nothing) hit this straight away. Rule: bounds check first, then look at the character.

Should I read with s.charAt(i), or convert with toCharArray() first?

For reading, charAt(i) is enough: it is O(1) and copies nothing. toCharArray() makes an O(n) copy, which you need only when you must change characters — like Reverse Words, because a String can't be changed. So: just reading → charAt; swapping or overwriting → char[].

Why does LeetCode's atoi clamp instead of throwing like Integer.parseInt?

Its rules look like the C library's, and older versions of the problem said "similar to C/C++'s atoi". The closest match is C's strtol: it skips leading whitespace, reads an optional sign and digits, and on overflow returns LONG_MAX or LONG_MIN (and sets errno to ERANGE). Plain C atoi has undefined behaviour on overflow. Java's Integer.parseInt chose to be strict and throw. In an interview, ask which behaviour they want.

The atoi guard fires at 2147483648 — but −2147483648 is a valid int. Does the guard break it?

No. We build the digits as a positive number and apply the sign only at the end. For "-2147483648", the last digit 8 trips the guard (214748364 > (2147483647 − 8) / 10 = 214748363), and because the sign is negative we return Integer.MIN_VALUE. That is exactly −2147483648 — the right answer, just reached through the clamp. Dhyan do: that's why the guard never needs a long.

Two stacks or recursion for a calculator — which should I write?

The one you can explain without stopping. Recursive descent (expr → term → factor) reads like the grammar and handles unary minus naturally. Two stacks never risk a StackOverflowError on deep nesting. For LC 224 (only + − and brackets) the sign stack is shortest; for LC 227 (no brackets) result + last is shortest.

In Basic Calculator II, why does op start as '+', and why do we apply the old operator when we reach a new one?

When you reach an operator, the number just before it is finally complete — and the operator that belongs to that number is the one before it, saved in op. The first number has no operator in front, so we pretend it had a '+'. Dry-run "3+5*2": at +, num 3 with op + → last = 3. At *, num 5 with op + → result = 3, last = 5. At the last character, num 2 with op * → last = 10. Answer: result + last = 13.

Why is "14-3/2" 13 and not 12? How does Java divide negative numbers?

Java's integer / drops the fraction toward zero: 3 / 2 is 1 and -3 / 2 is −1, not −2. In the one-pass calculator the term is stored as last = -3, then last / 2 gives −1, and 14 + (−1) = 13 — exactly what LeetCode asks for. If you ever need rounding down instead, that is Math.floorDiv(-3, 2), which gives −2.

What is a state machine, really?

A fixed set of states plus a rule: (current state, next character) → next state. atoi has four: start, sign, digits, end. Interview answers usually write it as if-statements; the table form next[state][charClass] makes every case visible, which helps on harder ones like Valid Number (LC 65).

Is the greedy Roman conversion always right? Greedy fails for coin change.

For this table, yes: it lists all 13 building blocks of standard numerals (the pairs included), biggest first, so the biggest piece that fits is always the next piece of the answer. Greedy is not safe for every table: with coins {1, 3, 4}, greedy pays 6 as 4 + 1 + 1, but 3 + 3 uses fewer coins — see Coin Change in Dynamic Programming.

Why does Reverse Words need a char[] in Java?

Java Strings are immutable, so you can't swap characters inside one. toCharArray() gives a copy you can change — O(n) space. The follow-up "O(1) extra space" means "beyond that array" in Java; say so in the interview.

How is a length prefix different from escaping?

Escaping marks special characters inside the data (a real # becomes ##), so the reader must inspect every character. A length prefix says how many characters follow, so the reader jumps over the data without looking at it. Both are O(n); length prefixes are simpler, and they're what Protocol Buffers and DataOutputStream.writeUTF use.

In decode, why substring(hash + 1, hash + 1 + len)? I always get the + 1 wrong.

hash is the index of the '#', so the text starts one place later, at hash + 1. substring(a, b) takes b − a characters (the end index is excluded), so b = a + len takes exactly len. Example "5#Hello": hash = 1, and substring(2, 7) is "Hello". The next header starts at that same end index, hash + 1 + len = 7.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run.

  1. #13
    Roman to Integermust-do
    EasyBloombergMicrosoftGoogleTCSAmazon+1
  2. #12
    Integer to Roman
    MediumAdobeTCSWalmartMicrosoftAmazon+1
  3. #151
    Reverse Words in a Stringmust-do
    MediumAppleMicrosoftBloombergAmazonGoogle+1
  4. #8
    String to Integer (atoi)must-do
    MediumNetflixBloombergMetaAmazonMicrosoft+1
  5. #227
    Basic Calculator IImust-do
    MediumMetaByteDance / TikTokAirbnbAmazonBloomberg+1
  6. #224
    Basic Calculatormust-do
    HardUberAmazonMicrosoftGoogleMeta+1
  7. #271
    Encode and Decode Stringsmust-doLeetCode Premium
    MediumGoogleAmazonMeta
  8. #68
    Text Justification
    HardAirbnbByteDance / TikTokUberAtlassianLinkedIn+1

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

  1. #150
    Evaluate Reverse Polish Notation
    Mediumin Stacks

    Shunting-yard's output is postfix; this is the evaluator that runs it with one operand stack.

  2. #394
    Decode String
    Mediumin Stacks

    Parsing with a cursor plus a stack of saved contexts: multi-digit counts and nested k[...] groups.

  3. #71
    Simplify Path
    Mediumin Stacks

    Tokenise on '/', then let '..' pop — a parser and a stack working together.

  4. #7
    Reverse Integer
    Mediumin Math & Numbers

    The same overflow guard as atoi, checked before rev * 10 + d.

  5. #43
    Multiply Strings
    Mediumin Math & Numbers

    Arithmetic on digit strings, one character at a time — no parseInt allowed.

  6. #189
    Rotate Array
    Mediumin Arrays & Strings

    The three-reversal trick behind in-place Reverse Words.

  7. #297
    Serialize and Deserialize Binary Tree
    Hardin Traversals

    Framing a whole tree into one string: separators plus null markers, read back with a cursor.

11 · revise

The whole chapter on one screen

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

  1. what it is

    Parsing = one index walks the text once. Read a whole token (number, word, operator), decide what it means from what came before, move on.

  2. use it when

    "Implement atoi", "evaluate this expression", "encode a list into one string", "justify text", "convert numerals" → a scanner, a few states, maybe a stack.

  3. template

    while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') num = num * 10 + (s.charAt(i++) - '0'); — read the whole number.

  4. cost

    Each character is read once → O(n). Stacks for brackets or precedence: O(n) space worst case; a recursive parser uses O(depth) call stack.

  5. trap

    Overflow: check result > (MAX - d) / 10 before result * 10 + d. After the multiply it has already wrapped.

  6. trap

    Character.isDigit('५') is true. In parsers test c >= '0' && c <= '9', or other scripts' digits slip in and c - '0' is garbage.

  7. pro tip

    Precedence with two stacks: before pushing an operator, apply every waiting one with precedence ≥ it. Or write expr → term → factor.

  8. pro tip

    No brackets? result = finished terms, last = the term * and / can still change. On + or −, bank last.

  9. template

    Framing: sb.append(s.length()).append('#').append(s). The reader jumps by the length, so a # in the data never confuses it.

  10. what it is

    Greedy table (Roman, lakh/crore, h:m:s): biggest value that fits, repeat. Greedy lines: take words while they fit, then spaces / gaps, spaces % gaps.

12 · recall

Flip, remember, repeat

card 1 / 14
recall

atoi: in what order are the parts of the input read?

tap or Space to flip ↻

Question 1: atoi: in what order are the parts of the input read?

13 · check yourself

Quick quiz

  1. What does atoi return for " -0012a42"?

  2. result ≥ 0. Which check correctly stops overflow before `result = result * 10 + d`?

  3. What is MCDXLIV?

  4. Two-stack evaluation of 8 - 3 - 2. The second '-' arrives while the first is on the ops stack. What happens?

  5. Basic Calculator II: what is "14-3/2"?

  6. A 16-wide line holds "example", "of", "text" (13 letters, 2 gaps). The gap widths are…

  7. Decode the length-prefixed string "3#a#b0#1##".

  8. Reverse Words in place on "the sky": after reversing the whole char[] you have…

  9. A recursive-descent parser (expr → term → factor) reads an expression nested 500 brackets deep. About how deep does the call stack go?

0/0 correct · 9 left

14 · learn more

A second teacher, if you want one