DEV Community

HHMathewChan
HHMathewChan

Posted on • Originally published at rebirthwithcode.tech

My Solution to Delimiter Soup from kattis

Problem

  • Whenever a programmer starts to learn a Lisp,
    • they think that there are too many parentheses in it.
  • Sophia thinks there are too few,
    • so she is making a programming language with only parentheses.
  • To spice it up a bit, she is also adding square brackets (‘[]’) and curly braces (‘{}’) to the language.

  • Right now, she is struggling to make people use it for production code.

  • Obviously, it has to be because of the bad error messages you get when you mess up the delimiters!

  • Right now, you only get the error message ‘syntax error’ when you mess them up.

  • Any opening delimiter must be closed by the same type of delimiter: ‘(’ is closed with ‘)’, [ is closed by ] etc.

  • Sophia wants to improve the error message so that you at least get some help finding out where it all went wrong.

Input

  • The input consists of two lines.
    • The first line contains an integer |L|, the length of the next line.
    • The next line contains L, the program you want to validate.

Output

  • Output

    • the character and the 0-indexed location
    • of the first closing delimiter
      • that does not match with the opening delimiter.
  • If there are no errors, or there are more opening delimiters than closing delimiters,

    • print ‘ok so far’ instead.

Limits

  • $1 ≤ L ≤ 200$
  • L contains only the characters ()[]{} and spaces
  • L does not start with a space character

My solution

problem definition

  • Function: validate program
  • Inputs: length, an integer that is the length of the L
    • L, a string contain the program to validate
  • Precondition:
    • $1 ≤ length ≤ 200$
    • L contains only the characters ()[]{} and spaces
    • L does not start with a space character
  • Output:
    • message, a string
  • Postcondition:
    • if there is a closing delimiter that does not match with the opening delimiter:
      • message contain the the first closing delimiter and its index
    • If there are no errors, or there are more opening delimiters than closing delimiters:
      • message contain 'ok so far’ .

Test table

  • The test table
validate_program_tests = [
    # case,            length,  L,                           expected
    ['ok for length 1',     1,  '[',                          'ok so far'],
    ['] at 0',              1,  ']',                          '] 0'],
    ['] at 7',              8,  '([] [] ]',                    '] 7'],
    ['ok for length is 13', 13, '(([] [[]] ())',               'ok so far'],
    ['] at 20',             21, '[ { { () () () () } ]',       '] 20'],
    ['ok for length is 27', 27, '[ { [[()]] (({})) } ] () {}', 'ok so far'],
    [') at 8',              19, '[[]] () ) [] {{}} {',          ') 8'],
]
Enter fullscreen mode Exit fullscreen mode

Outline of the algorithm

  • create a empty stack for the delimiters opened so far and not yet matched. Iterate over L for length times and process each character. If it's an open delimiter, push it on the stack. If it's a closing delimiter and the stack is empty or the top item isn't a matching opening delimiter, print that character and the index of the character, and stop. Otherwise, the delimiters match, so pop the opening delimiter from stack. If the end of L is reached, print "ok so far".

Algorithm

  1. let opened be an empty stack
  2. for each index from 0 to length - 1:
    1. let character be L[index]
    2. if character = '(' or character = '[' or  character = '{':
      1. push character on opened
    3. otherwise if character = ')':
      1. if │opened│ > 0 and top of opened = '(':
        1. pop opened
      2. otherwise:
        1. let message be the character and the index of the character
        2. stop
    4. otherwise if character = ']':
      1. if │opened│ > 0 and top of opened = '[':
        1. pop opened
      2. otherwise:
        1. let message be the character and the index of the character
        2. stop
    5. otherwise if character = '}':
      1. if │opened│ > 0 and top of opened = '{':
        1. pop opened
      2. otherwise:
        1. let message be the character and the index of the character
        2. stop
    6. otherwise:
      1. do nothing
  3. let message be 'ok so far'

Complexity

  • The stack is implemented using the list data type in python
  • Step 1. Θ(1)
  • Step 2, the loop has different case, state later
    • Step 2.1 Θ(1)
    • Step 2.2 Θ(1)
      • Step 2.2.1 Θ(1)
    • Step 2.3 Θ(1)
      • Step 2.3.1
      • get the length of stack is Θ(1) as Python's list implementation stores the length of the list as a separate attribute
      • so the complexity of step 2.3.1 would be Θ(1 + 1 + 1) = Θ(1)
        • Step 2.3.1.1 Θ(1)
      • Step 2.3.2
        • Step 2.3.2.1 Θ(1)
        • Step 2.3.2.2 Θ(1)
    • The overall complexity of step 2.3 is Θ(1)
    • The complexity of Step 2.4 , Step 2.5 and Step 2.6 is the same as step 2.3 = Θ(1)
  • Step 3 Θ(1)
  • The best case for step 2 is the first character is a closing delimiter, the loop will execute 1 time, so the complexity would be Θ(1)
  • The worst case for step 2 is it need to loop through the whole L , so the complexity would be Θ(|L|)
  • Since the largest factor that contribute to the complexity is step 2, and the best case of step 2 is a small input that can be ignore so the complexity of the whole program would be Θ(|L|)

The code

  • The code
def delimiter_soup(length, L):
    opened = []
    for index in range(length):
        char = L[index]
        if char in '([{':
            opened.append(char)
        elif char == ')':
            if len(opened) > 0 and opened[-1] == '(':
                opened.pop()
            else:
                return char + ' ' + str(index)
        elif char == ']':
            if len(opened) > 0 and opened[-1] == '[':
                opened.pop()
            else:
                return char + ' ' + str(index)
        elif char == '}':
            if len(opened) > 0 and opened[-1] == '{':
                opened.pop()
            else:
                return char + ' ' + str(index)
        else:
            pass
    return 'ok so far'
Enter fullscreen mode Exit fullscreen mode
  • The extra part add to answer in Kattis
length = int(input())
L = input()
print(delimiter_soup(length, L))
Enter fullscreen mode Exit fullscreen mode

Additional

  • some alternation
char + ' ' + str(index)
# can be replace as follow using f-string
f'{char}{index}'
Enter fullscreen mode Exit fullscreen mode

Source

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more