You are given a restaurant menu stored as plain text, where indentation represents a hierarchy of categories and items. Implement logic to convert between this text format and a tree data structure.
|
character:
<type>|<id>|<name>|<price>
where:
type
is a string label such as
CATEGORY
,
FOOD
, or
SIDE
(you should not assume only these three types; treat it as an arbitrary string).
id
is a unique identifier string for this item.
name
is free text that does not contain the
|
character.
price
is a decimal number (e.g.,
5.99
), or the literal
-
if the item does not have a price (e.g., a category).
Example input:
CATEGORY|c1|Burgers|-
FOOD|f1|Classic Burger|5.99
SIDE|s1|Fries|1.99
FOOD|f2|Veggie Burger|6.49
CATEGORY|c2|Drinks|-
FOOD|f3|Cola|1.50
FOOD|f4|Water|1.00
This example represents a hierarchy like category > food > side, but in general the depth and item types can vary.
Define a data structure MenuItem (language-agnostic) with at least the following fields:
type
: string
id
: string
name
: string
price
: nullable/optional number (null if the text price is
-
)
children
: an ordered list/array of
MenuItem
representing nested items
Top-level menu items are those with zero indentation.
parseMenu(text)
) that takes the menu text string and returns the corresponding tree: a list/array of top-level
MenuItem
nodes, each with properly populated
children
.
serializeMenu(items)
) that takes the tree (the list/array of top-level
MenuItem
nodes) and returns a canonical text representation in exactly the same format as described above.
The serializer must:
|
as the field separator.
-
for items whose
price
is null/absent.
children
.
You may assume the input text is always a valid, well-formed tree (no cycles, consistent indentation, and at least one top-level item).
Design your parsing and serialization logic to run in O(N) time and O(N) extra space, where N is the number of menu items (lines) in the input.