In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of November 23rd
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #06 exercise sheet]
(this problem is an adaptation from a ToPAS'2010 problem)
It's St Anthony's Day in the kingdom of expressions, and the parentheses (), brackets [] and braces {} are thrilled to be getting married. However, they still need to find their date. The grooms will wait in orderly fashion for their brides and, in order not to create too much confusion, will leave as soon as they arrive. As they are modern people, they will even use a computer program to control this process.
Given an expression that might contain parentheses, brackets and braces, your task is to check if the expression is well formed in terms of pairs of (), [] and {} (the brides and grooms).
The input will consist of a single line containing an expression E. The only characters on this line will be digits (0 to 9), lower case letters (a to z), operators (+, -, *, /) and parentheses (), brackets [] or braces {}.
If all the pairs are well matched, you should print the type of each pair - (), [] or {} - and the respective opening and closing positions in the expressions (starting at 0). One line should be printed for each pair, in the order of closure (the second number is strictly ascending).
If any of the pairs are badly matched, you should only print a line saying "badly matched pairs".
If the expression contains no parentheses, brackets or braces, you should print a line saying "no brides and grooms to marry".
There is no need to validate the expression other than the matching of parentheses, brackets and braces.
In the output, the integer positions are separated from the pair type by a space, but the parentheses, brackets or curly braces have no separator between them.
The following limits are guaranteed in all the test cases that will be given to your program:
1 ≤ |E| ≤ 1000 | Number of characters in the expression |
Example Input 1 | Example Output 1 |
3(x+2)-4{x+[2y-(27-z)+8w]}-1 |
() 1 5 () 15 20 [] 11 24 {} 8 25 |
Example Input 2 | Example Output 2 |
2(x+3] |
badly matched pairs |
Example Input 3 | Example Output 3 |
2(x+3)+2) |
badly matched pairs |
Example Input 4 | Example Output 4 |
2x+4y+7 |
no brides and grooms to marry |