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'],
]

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'

• The extra part add to answer in Kattis

length = int(input())
L = input()
print(delimiter_soup(length, L))

Additional

• some alternation

char + ' ' + str(index)
# can be replace as follow using f-string
f'{char}{index}'

Source

• Delimiter Soup – Kattis, Kattis