1
\$\begingroup\$

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
\$\endgroup\$
2

3 Answers 3

3
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ In the question's initial revision, I was under the impression score2() was from some user on LeetCode. \$\endgroup\$
    – greybeard
    Mar 6 at 14:41
  • \$\begingroup\$ 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? \$\endgroup\$
    – jason
    Mar 7 at 14:13
  • \$\begingroup\$ 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? \$\endgroup\$
    – jason
    Mar 7 at 16:52
  • \$\begingroup\$ (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. \$\endgroup\$
    – greybeard
    Mar 7 at 21:20
  • \$\begingroup\$ 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. \$\endgroup\$
    – greybeard
    Mar 7 at 22:05
2
\$\begingroup\$

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"))
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ When Tim Peters wrote reindent a quarter century ago, it was nice enough. Nowadays I would prefer to run the better supported black. \$\endgroup\$
    – J_H
    Mar 6 at 22:35
  • \$\begingroup\$ @J_H: Thanks for the recommendation. \$\endgroup\$
    – toolic
    Mar 6 at 23:21
  • \$\begingroup\$ 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. \$\endgroup\$
    – greybeard
    Mar 7 at 6:54
  • \$\begingroup\$ @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? \$\endgroup\$
    – jason
    Mar 7 at 14:02
  • \$\begingroup\$ @jason: I have no further suggestions at this time, nor do I have any advice regarding your other queries. \$\endgroup\$
    – toolic
    Mar 7 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.