String Parsing & Expression Evaluation

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.

   #1
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.

   #2
3. { }template

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

   #3
4. O( )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.

   #4
5. !trap

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

   #5
6. !trap

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

   #6
7. ✦pro tip

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

   #7
8. ✦pro tip

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

   #8
9. { }template

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

   #9
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.

    #10

Shaky on a card? Open the chapter or flip its recall cards.