Beyond Big O

One-pass string parser

One-pass string parser

Medium

Your task

  • Read one atom from a small input string and return its exact spelling.
  • For example, Route_7 stays Route_7, and 007 stays a string.
  • Do not evaluate or convert values.

Required API

  • ParseError.Error
    func (e *ParseError) Error() string
  • ParseSexp
    func ParseSexp(text string) (any, error)
  • ParseError.Code
    Code string
  • ParseError.Index
    Index int

Behavior

  • An atom contains one or more characters from [A-Za-z0-9_+-].
  • Ignore leading and trailing space, tab, carriage return and newline.
  • The input is ASCII and at most 4,096 characters long.
  • Parentheses are not supplied in this part.
  • Use one forward-moving cursor, without splitting or tokenizing the whole input, eval or a general parser.
  • Aim for O(n) time.
  • Each call starts fresh.
  • Use only the standard library.
  • Report the first violation reached, with a zero-based character index.
  • Empty or whitespace-only input is expected_expression at EOF (len(text)).
  • An unsupported character is invalid_character at its position.
  • After the atom and optional whitespace, another atom is trailing_input at its first character; an unsupported character is still invalid_character.
  • Stop there rather than scanning ahead.
  • On failure return no partial result.
  • Error messages are not graded.

Examples

The runner calls your functions directly; you do not need to parse JSON.

Example 1 · atom

Arguments
text
"  Route_7\t"
Expected return
"Route_7"
Test data
Input
"  Route_7\t"
Expected output
"Route_7"

Example 2 · extra root

Arguments
text
"a b"
Expected outcome
ParseError(code="trailing_input", index=2)
Test data
Input
"a b"
Expected output
ParseError(code="trailing_input", index=2)

Related guides

Editor options
Typing preferences

Saved in this browser.

Restoring local drafts…