This week's book giveaway is in the OCAJP 8 forum. We're giving away four copies of OCA Java SE 8 Programmer I Study Guide and have Edward Finegan & Robert Liguori on-line! See this thread for details.
Neither of your two "regular expressions" problems are really very well-suited to regular expressions. They're really both simple state-machine type parsing problems, both simple enough to solve with an ad-hoc lexical analyzer, but each non-trivial enough to justify using something like ANTLR instead if you wanted to.
If you plug that into Kevin's code, you'll be able to retrive the keys via group(1) and the values via group(2). This works on the one line of sample data you provided, but YMMV. For instance, if you decide you need another level of parenthesis nesting, the regex will become about twice as ugly. I really think you're better off using a dedicated parser for this one.
Regular expressions are not well suited for parsing nested parentheses. You will need a slightly more complicated parser that can count how many "levels" there are in the nesting. If you want to investigate this further on your own, you should google for "context free language", "context free grammar", or "push down automata" as these are the theoretical foundations for doing such parsing.