LC: 439. Ternary Expression Parser - spiralgo/algorithms GitHub Wiki

439. Ternary Expression Parser

The Essence:

It's important to notice that ternary expressions can form nested expressions, such as "T?T?1:2:F?4:T?5:3", equivalent to "T?(T?1:2):(F?4:(T?5:3))". Trying to parse the expression from left to right would only create complexity. Trying from the opposite direction, however, can allow parsing of individual ternary expressions, eventually building up the whole solution by divided-and-solved parts.

Details:

Nice the expression is nested, it can be interpreted as DFS-like graph problem too. The problem solver can then use a stack to keep track of expression's value from left to right, eventually popping and comparing the first and second values.

The code can be found here.