It can be easily shown that, among all the strings of length 2, only the following 8 can be a possible substring of a valid formula:

• ((
• (0
• +(
• +0
• )+
• ))
• 0+
• 0)

Furthermore, one can uniquely determine the character by its two adjacent characters. By prepending 0+ and appending +0 to the original string, every unknown character can be uniquely determined in this way. The total time complexity is \(O(|T|)\).