In this homework, you are asked to decode a secret message.
A message has N characters, and each character can be decoded by one line of ciphertext. A line of ciphertext only contains characters '(' and ')', and you need to find the length of longest valid parentheses substring for each line. After finding the length, you will need to Divide by 2 and Mod 26 to change it into the character. Finally, you need to output the secret message grouping by the characters.
Hint: Implement a stack class
Notice: Any kind of STL is not allowed in this homework. (string is allowed)
Rules of valid parentheses string:
A string is considered valid if every opening parenthesis '(' has a corresponding closing parenthesis ')' and is in the correct order.
Example:
(()()()()) is considered valid, each '(' has a corresponding ')' in the correct order.
((((()) is considered not valid, because some '(' has no corresponding ')'.
))(( is considered not valid, because the order is wrong.
Encode into character:
If the input ciphertext is ()())))))(()()())(())()((()((), the longest valid parentheses substring is (()()())(())() and its length is 14. You will need to Divide by 2 and Mod 26.
14 / 2 = 7
7 % 26 = 7
According to the character table below, you will get the character ‘h’.
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
a |
b |
c |
d |
e |
f |
g |
h |
i |
j |
k |
l |
m |
|
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
|
n |
o |
p |
q |
r |
s |
t |
u |
v |
w |
x |
y |
z |
Notice:
Your code needs to be submitted to NTHU OJ and eeclass before the deadline.
Please zip your code as studentID.zip and submit to eeclass HW2.(eg, 108062218.zip)
The first line has one number, N, indicating the length of secret message.
The next N lines are ciphertext that only contains characters '(' and ')'.
Constraint:
0 < N < 10000
0 < length of ciphertext < 100000
Print the secret message grouping by the characters you got.
Note that you need to print ‘\n’ at the end of the output.