TIP102 Unit 3 Session 2 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
token
containing pairs of mystical brackets ()
representing the structure of a mystical token.()
has a value of 1.AB
is the sum of their individual values.(A)
is twice the value of the token inside the brackets.Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use a stack to manage the nested structure of the token. As you iterate through the string, maintain a running score that accumulates the values based on the structure of the token.
1. Initialize an empty stack and a variable `score` set to 0.
2. Iterate over each character in the `token` string:
1. If the character is `'('`, push the current `score` onto the stack and reset `score` to 0.
2. If the character is `')'`, pop the top value from the stack and update `score` to be the sum of the popped value and the maximum of `2 * score` or 1.
3. After iterating through the string, return the final `score` as the value of the token.
⚠️ Common Mistakes
def token_value(token):
stack = []
score = 0
for char in token:
if char == '(':
stack.append(score)
score = 0
else:
score = stack.pop() + max(2 * score, 1)
return score
# Example usage
print(token_value("()")) # Output: 1
print(token_value("(())")) # Output: 2
print(token_value("()()")) # Output: 2