MediumNo. 0439LeetCode Premium
Ternary Expression Parser — LeetCode 439 Python Solution
- Pattern
- Stack
- Topics
- Stack, Recursion, String
- Reading time
- 4 min
- Source
- leetcode.com
The problem
Given a string expression representing arbitrarily nested ternary expressions, evaluate the expression, and return the result of it. You can always assume that the given expression is valid and only contains digits, '?', ':', 'T', and 'F' where 'T' is true and 'F' is false.
Example
- Input
- expression = "T?2:3"
- Output
- "2"
- Explanation
- If true, then result is 2; otherwise result is 3.
Python solution
class Solution:
def parseTernary(self, expression: str) -> str:
stk = []
cond = False
for c in expression[::-1]:
if c == ':':
continue
if c == '?':
cond = True
else:
if cond:
if c == 'T':
x = stk.pop()
stk.pop()
stk.append(x)
else:
stk.pop()
cond = False
else:
stk.append(c)
return stk[0]Complexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Stack
When the most recent unresolved thing is the one that matters, use a stack. LeetCode 439. Ternary Expression Parser is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.
The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0224 | Basic Calculator | Hard |
| 0394 | Decode String | Medium |
| 1106 | Parsing A Boolean Expression | Hard |
| 0020 | Valid Parentheses | Easy |
| 0071 | Simplify Path | Medium |
| 0143 | Reorder List | Medium |
Frequently asked questions
- How hard is LeetCode 439. Ternary Expression Parser?
LeetCode 439. Ternary Expression Parser is rated Medium on LeetCode.
- What is the time complexity of LeetCode 439. Ternary Expression Parser?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 439. Ternary Expression Parser?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 439. Ternary Expression Parser cover?
LeetCode 439. Ternary Expression Parser is tagged Stack, Recursion and String on LeetCode.
- Is LeetCode 439. Ternary Expression Parser a premium problem?
Yes. LeetCode 439. Ternary Expression Parser is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.