Skip to main content
Added balanced-string tag
Link
DLosc
  • 39.2k
  • 5
  • 83
  • 141
Tweeted twitter.com/StackCodeGolf/status/940908592164691968
Source Link
Nissa
  • 3.6k
  • 1
  • 18
  • 45

Decode Factor Trees

In case you missed Encode Factor Trees, here is the definition of a Factor Tree:

  • The empty string is 1.
  • Concatenation represents multiplication.
  • A number n enclosed in parentheses (or any paired characters) represents the nth prime number, with 2 being the first prime number.
  • Note that this is done recursively: the nth prime is the factor tree for n in parentheses.
  • The factors of a number should be ordered from smallest to largest.

For example, here are the factor trees for 2 through 10:

()
(())
()()
((()))
()(())
(()())
()()()
(())(())
()((()))

This challenge uses a similar format; however, this challenge is to decode these structures.

Test Cases

Shamelessly stolen repurposed from the last challenge.

In addition to the 9 above…

()()((()))((())) => 100
(()(()(()))) => 101
(()())(((())))(()(())) => 1001
(((((((()))))))) => 5381
(()())((((()))))(()()(())(())) => 32767
()()()()()()()()()()()()()()() => 32768

Rules

  • The paired characters in the input are your choice of parentheses, brackets, braces, or angle brackets. I may allow other formats (e.g. XML tags) if asked.
  • You should be able to handle Factor Trees for any number from 2 to 215 or 32768.
  • Since this is , the shortest answer in bytes wins.