Skip to content

Latest commit

 

History

History
 
 

439.Ternary-Expression-Parser

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

439.Ternary-Expression-Parser

此题粗看很复杂,实际很明晰。

需要最早解析的字符串,其实是已经形成标准型a?X:Y的这五个连续字符。所以在第一次出现这五个连续字符之前的字符,都可以不断存进一个栈里供后续处理。

具体的算法是,当发现?字符,表明这可能是一组标准型的head。所以把a?之前的字符串扔进栈里,然后重置curRes并顺着a?继续向后探索。如果还有出现类似?的标记,则重复之前的入栈操作;反之,如果之后curRes集齐五个字符,则说明这五个字符是类似a?X:Y的标准型,可以被解析变为一个字符。此时考虑一下栈里的栈顶元素,如果栈顶元素加上当前的这一个字符(curRes),又构成五个字符的话,可以进一步解析;如此重复直至栈顶无法提供凑齐五个字符的string,此时curRes需要顺着expression继续探索下去。

最终返回的是当前的字符串,即curRes。

Leetcode Link