Parsing Strings in One Pass
Read once, keep a little
A calculator reads " -0042abc" and has to decide what every character means. The spaces mean nothing, the minus means the number is negative, the zeros mean nothing yet, 4 and 2 build the value, and the a ends it. None of those decisions can be made from one character alone. Each depends on what came before.
That's parsing: one pass over the characters, carrying a small state that says what you've seen so far. The method from Introduction to Arrays works unchanged. Write the state as a sentence that's true after every character, like "depth is the number of open parentheses so far", and the code and the edge cases both follow from it.
Parentheses: a depth counter
With only one kind of bracket, one number tells you where you are: the depth, up one for each (, down one for each ).
Maximum Nesting Depth of the Parentheses is the largest depth the walk reaches:
def max_depth(s):
depth = best = 0 # depth: open parentheses so far; best: the deepest it has been
for c in s:
if c == "(":
depth += 1
best = max(best, depth)
elif c == ")":
depth -= 1
return best
It returned 3, 3, 3 for "(1+(2*3)+((8)/4))+1", "(1)+((2))+(((3)))", "()(())((()()))".
Remove Outermost Parentheses splits the string into top-level groups and drops each group's outer pair. A ( is outermost when it opens at depth 0; a ) is outermost when it brings the depth back to 0. So decide before raising the depth for (, and after lowering it for ):
Remove Outermost Parentheses on "(()())(())" — The current character is indigo; green characters are kept.
string removeOuterParentheses(const string& s) {
string out;
int depth = 0; // how many "(" are open before this character
for (char c : s) {
if (c == '(') {
if (depth > 0) out += c; // not the opening of a top-level group
depth++;
} else {
depth--;
if (depth > 0) out += c; // not the closing of a top-level group
}
}
return out;
}
def remove_outer_parentheses(s):
out, depth = [], 0 # depth: how many "(" are open before this character
for c in s:
if c == "(":
if depth > 0: # not the opening of a top-level group
out.append(c)
depth += 1
else:
depth -= 1
if depth > 0: # not the closing of a top-level group
out.append(c)
return "".join(out)
static String removeOuterParentheses(String s) {
StringBuilder out = new StringBuilder();
int depth = 0; // how many "(" are open before this character
for (char c : s.toCharArray()) {
if (c == '(') {
if (depth > 0) out.append(c); // not the opening of a top-level group
depth++;
} else {
depth--;
if (depth > 0) out.append(c); // not the closing of a top-level group
}
}
return out.toString();
}
function removeOuterParentheses(s) {
const out = [];
let depth = 0; // how many "(" are open before this character
for (const c of s) {
if (c === '(') {
if (depth > 0) out.push(c); // not the opening of a top-level group
depth++;
} else {
depth--;
if (depth > 0) out.push(c); // not the closing of a top-level group
}
}
return out.join('');
}
Each prints [()()()], [()()()()(())], [] and [(())] for "(()())(())", "(()())(())(()(()))", "()()" and "((()))". One pass, one number: O(n) time, O(n) for the output.
A counter is enough only for one kind of bracket. With (), [] and {} mixed, the order of the open ones matters, and that needs a stack (Stacks & Queues).
Roman numerals: look one symbol ahead
Roman to Integer: I is 1, V 5, X 10, L 50, C 100, D 500, M 1000, and the values add up, except that a smaller symbol written just before a larger one is subtracted: IV is 4, IX 9, XC 90, CM 900. So look one symbol ahead. If the next one is larger, this one subtracts; otherwise it adds:
def roman_to_int(s):
value = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
total = 0
for i, c in enumerate(s):
if i + 1 < len(s) and value[c] < value[s[i + 1]]: # smaller before larger: this one subtracts
total -= value[c]
else:
total += value[c]
return total
It returned 3, 58, 1994, 4 for "III", "LVIII", "MCMXCIV", "IV". Every number from 1 to 3,999 (every 7th, written out and read back) came back right.
String to Integer: four stages and one check
String to Integer (atoi) turns the start of a string into a 32-bit integer by four rules, in order:
- skip spaces, but only before anything else;
- read one sign, + or −, if there is one;
- read digits until the first character that isn't one;
- stop there, and clamp the answer to the range from −2^31 to 2^31 − 1.
The state is two things: the sign, and the value read so far. The hard part is stage 3's limit. value * 10 + d can pass 2^31 − 1, and in a 32-bit int it wraps around before you can notice. So check before multiplying: the next digit overflows exactly when value > (limit − d) / 10, where the limit is 2^31 − 1 for a plus and 2^31 for a minus.
Try the rules yourself below. Pick what atoi does with each character; a wrong pick is refused with the reason. The presets include the overflow and the two-sign trap.
int myAtoi(const string& s) {
int i = 0, n = s.size();
while (i < n && s[i] == ' ') i++; // 1. spaces, only before anything else
int sign = 1;
if (i < n && (s[i] == '+' || s[i] == '-')) { // 2. one sign at most
if (s[i] == '-') sign = -1;
i++;
}
long long limit = sign > 0 ? INT_MAX : 2147483648LL; // 2^31 - 1, or 2^31 for a minus
long long value = 0;
while (i < n && s[i] >= '0' && s[i] <= '9') { // 3. digits until the first non-digit
int d = s[i] - '0';
if (value > (limit - d) / 10) // value * 10 + d would pass the limit: check first
return sign > 0 ? INT_MAX : INT_MIN;
value = value * 10 + d;
i++;
}
return (int)(sign * value); // 4. anything else ends the number
}
def my_atoi(s):
i, n = 0, len(s)
while i < n and s[i] == " ": # 1. spaces, only before anything else
i += 1
sign = 1
if i < n and s[i] in "+-": # 2. one sign at most
sign = -1 if s[i] == "-" else 1
i += 1
limit = 2**31 - 1 if sign > 0 else 2**31 # the largest magnitude allowed for this sign
value = 0
while i < n and "0" <= s[i] <= "9": # 3. digits until the first non-digit
d = ord(s[i]) - ord("0")
if value > (limit - d) // 10: # value * 10 + d would pass the limit: check first
return sign * limit
value = value * 10 + d
i += 1
return sign * value # 4. anything else ends the number
static int myAtoi(String s) {
int i = 0, n = s.length();
while (i < n && s.charAt(i) == ' ') i++; // 1. spaces, only before anything else
int sign = 1;
if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) { // 2. one sign at most
if (s.charAt(i) == '-') sign = -1;
i++;
}
long limit = sign > 0 ? Integer.MAX_VALUE : 2147483648L; // 2^31 - 1, or 2^31 for a minus
long value = 0;
while (i < n && Character.isDigit(s.charAt(i))) { // 3. digits until the first non-digit
int d = s.charAt(i) - '0';
if (value > (limit - d) / 10) // value * 10 + d would pass the limit: check first
return sign > 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
value = value * 10 + d;
i++;
}
return (int) (sign * value); // 4. anything else ends the number
}
function myAtoi(s) {
let i = 0;
const n = s.length;
while (i < n && s[i] === ' ') i++; // 1. spaces, only before anything else
let sign = 1;
if (i < n && (s[i] === '+' || s[i] === '-')) { // 2. one sign at most
if (s[i] === '-') sign = -1;
i++;
}
const limit = sign > 0 ? 2 ** 31 - 1 : 2 ** 31; // the largest magnitude allowed for this sign
let value = 0;
while (i < n && s[i] >= '0' && s[i] <= '9') { // 3. digits until the first non-digit
const d = s.charCodeAt(i) - 48;
if (value > Math.floor((limit - d) / 10)) return sign * limit; // check before multiplying
value = value * 10 + d;
i++;
}
return sign * value || 0; // 4. anything else ends the number (and -0 is 0)
}
Each prints [42], [-42], [1337], [0], [0], [-2147483648], [2147483647], [0], [0] and [0] for "42", " -042", "1337c0d3", "0-1", "words and 987", "-91283472332", "2147483648", "+-12", " +0 123" and "". One pass: O(n) time, O(1) space. Every one of 1,500 random strings matched a reference parser.
Python's integers never overflow, so a Python atoi could clamp at the end instead. Checking before the multiply is still the version that works in every language.
Spotting it
Clues that a string wants a one-pass parser:
- one kind of bracket, and a question about nesting or groups: a depth counter;
- symbols whose meaning depends on their neighbour (Roman numerals, escape characters): look one ahead, or one behind;
- "convert", "parse", "read until", with rules about spaces, signs and limits: name the stages, and never go back to an earlier one;
- a 32-bit result: check the limit before each multiply.
And the near-misses:
- several kinds of brackets that must match in order: a stack (Stacks & Queues).
- expressions with precedence (Basic Calculator): a stack, or recursion, holds the pending operations.
- splitting into words or fields with simple separators: the language's split, used carefully, is simpler than a state machine.
Common mistakes
Changing the depth before deciding. depth += 1 if c == "(" else -1, then if depth > 0:
For a ( the check now sees the depth after it opens, so outermost openings are kept: "(()())(())" gave (()()(() instead of ()()(). Decide before raising, after lowering.
Subtracting the smaller Roman symbol only once. total += cur - prev
The smaller symbol was already added on the step before, so it has to come off twice. "IV" returned 5 and "MCMXCIV" 2105; the answers are 4 and 1994. Looking ahead avoids the problem.
Multiplying before checking the limit. value = value * 10 + d in a Java int
"2147483648" returned -2147483648 and "9999999999" 1410065407: the value wrapped around without any error. Check value > (limit - d) / 10 first.
Skipping spaces after the sign.
"- 42" returned -42; the answer is 0. Spaces only count before anything else.
Reading every sign. while s[i] in "+-"
"+-12" returned -12; the answer is 0. One sign at most.
Check yourself
Quiz
1 / 6Multiple choice
Multiple choice
Multiple choice
Multiple choice
Multiple choice
Multiple choice
Practice problems
From easier to harder:
- Maximum Nesting Depth of the Parentheses: the depth counter's largest value.
- Remove Outermost Parentheses: decide before raising, after lowering.
- Roman to Integer: look one symbol ahead.
- String to Integer (atoi): four stages, and the check before the multiply.
Next: Palindromes: Expand Around the Center.