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}'
Top comments (0)