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’ .
- if there is a closing delimiter that does not match with the opening delimiter:
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
- let opened be an empty stack
- for each index from 0 to length - 1:
- let character be
L[index]
- if character = '(' or character =
'['
or character ='{'
:- push character on opened
- otherwise if character = ')':
- if │opened│ > 0 and top of opened = '(':
- pop opened
- otherwise:
- let message be the character and the index of the character
- stop
- if │opened│ > 0 and top of opened = '(':
- otherwise if character = ']':
- if │opened│ > 0 and top of opened =
'['
:- pop opened
- otherwise:
- let message be the character and the index of the character
- stop
- if │opened│ > 0 and top of opened =
- otherwise if character = '}':
- if │opened│ > 0 and top of opened =
'{'
:- pop opened
- otherwise:
- let message be the character and the index of the character
- stop
- if │opened│ > 0 and top of opened =
- otherwise:
- do nothing
- let character be
- 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