My Solution to Delimiter Soup from kattis
Tags: python, challenge, kattis
Published: 2023-06-19 16:45:32

## 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
```python
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
```python
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
```python
length = int(input())
L = input()
print(delimiter_soup(length, L))
```
## Additional

- some alternation
```python
char + ' ' + str(index)
# can be replace as follow using f-string
f'{char}{index}'
```
## Source
- [Delimiter Soup – Kattis, Kattis](https://open.kattis.com/problems/delimitersoup)