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

Top comments (0)