# LeetCode 856: Score of Parentheses

Given a balanced parentheses string s, return the score of the string.
The score of a balanced parentheses string is based on the following rule:
- "()" has score 1.
- AB has score A + B, where A and B are balanced parentheses strings.
- (A) has score 2 * A, where A is a balanced parentheses string.

Based on the Python solution given below, I have a question. What advice would you give me for improvement?

The following is my solution:

def score(s):
depth = 0
prev_depth = 0
stack = []

for i, char in enumerate(s):
if char == ")":
depth -= 1

if stack and prev_depth == depth and stack[-1][1] == depth:
value, target_depth = stack.pop()
while stack and stack[-1][1] == target_depth:
value += stack.pop()[0]
stack.append((1 + value, depth))
elif prev_depth == depth:
stack.append((1, depth))
else:
if stack:
value = 0
while stack and stack[-1][1] != depth:
value += stack.pop()[0]
stack.append((2 * value, depth))

continue

prev_depth = depth
depth += 1

total = sum(a for a, _ in stack)
return total

• You can access the history of you question and the rolled-back edit (to be posted as a new question instead) in the revision history.
– Mast
Mar 7 at 17:05

## 3 Answers

It is not documented what the score() function is good for.

You use the identifier _ for something you get, but don't use in for a, _ in stack - fine.
i in for i, char in enumerate(s) goes unused too; here I find the alternative for char in s more compelling.

"The ')'-handling" is longish; at the continue I have to check the circumstances to reach the code following.
As the code does not document the idea implemented, I have to guess/"reverse engineer" - and I don't understand why values are not accumulated right away, at least "per depth".
(I think you are implementing a flattened stack of lists of summands.)

Code the way you think about problem and solution.
Don't let it bother you others find solutions that look simpler, require more thought to conceive or understand.
Never mind not knowing the approach/solution you think best - or someone else claims best.

• In the question's initial revision, I was under the impression score2() was from some user on LeetCode. Mar 6 at 14:41
• any recommendation about the logic implemented by the score function? one thing ive realized is that every single solution to all the problems i have managed to solved is too exhaustive(meaning implementing unnecessary stuff or twisted thinking and taking caring of many useless things AND do not use constraint in the problem description) and messy and ugly which question me about my problem solving and thinking clearly ability. any suggestion about how to improve problem solving and thinking clearly in general? Mar 7 at 14:13
• about constraint/info in the problem desc. the problem desc states pair () is 1 and otherwise sum is multiplied by 2. now i realized i could use this info with my own depth(and not previous depth) tracking method to design a better algorithm. is this also what you mean by I don't understand why values are not accumulated right away, at least "per depth". and what this blindness to simple fact and info indicate about ones problem solving and thinking habits? Mar 7 at 16:52
• (thinking this a matter of software development more than coding:) recommendation about the logic to implement for any task specified: there are extremes: 1) sticking to the specification like glue - useful in arguing at least the results are right: basis for tests. 2) the most simple thing - often not obvious, may require a solid insight into the task. 3) the solution that puts least demand on some resource - difficult enough, doesn't get easier when considering more than one type of resource, including developer time. Mar 7 at 21:20
• Start with 1), documenting what you think. Take notes on simplifications coming to mind, postpone them and complete 1). Test whether the results are as expected. Go for simpler next, but guess return for the time you invest every now and then. You have the impression there is room for improvement in how you approach problems - great: you are able to take a step back. Don't worry, practise while not pressing it. Mar 7 at 22:05

Your code is not explicitly looking for '(' characters, which makes it fragile.

score("((((abcd))))")
8
score("(a(((bc)))d)")
5
score("(a(b(())c)d)")
4
score("(((()))abcd)")
5


Perhaps the problem explicitly states the string can only contain ( and ) characters. Perhaps it doesn't. We don't know. All we know is that we are promised the parenthesis are balanced.

An elif char == '(': would go a long way towards both understandability and robustness.

#### Obligatory 1-line solution

Because one-line solutions rock (and assuming the string only contains ( and ) characters):

def score(s: str):
return eval(s.replace(")(", ")+(").replace("()", "1").replace(")", ")*2"))


## Lint check

pylint identified a few issues, some of which were mentioned in the other answer.

## Indentation

A 2-space indent level makes ths code hard to understand. The standard is 4 spaces per indent level. I used reindent.py to automatically indent the code.

## Naming

The variable named s would be more meaningful as something like input_string:

def score(input_string):
depth = 0
prev_depth = 0
stack = []

for char in input_string:


## Input checking

I realize this code is meant for a programming challenge, but if you wanted it to be stand-alone, you would also add some checking of the input string to make sure it is valid.

## Documentation

Elaborating on the other answer, a docstring at the top of the file with some description of the input and a few example input/output pairs would be helpful to the user.

• When Tim Peters wrote reindent a quarter century ago, it was nice enough. Nowadays I would prefer to run the better supported black.
– J_H
Mar 6 at 22:35
• @J_H: Thanks for the recommendation. Mar 6 at 23:21
• docstring at [top of file] allows help to help on a module; a function docstring is a piece of documentation that would require active effort to separate from its function. Mar 7 at 6:54
• @toolic do you have any suggestion about the logic just implement? also based on the given code, how do you evaluate the author in terms of experience level and problem solving maturity? is there any resources or some kinda practice that can improve problem solving ability and thinking clearly? Mar 7 at 14:02
• @jason: I have no further suggestions at this time, nor do I have any advice regarding your other queries. Mar 7 at 14:43