Untitled

Given an input  string made up of just left and right parantheses  i.e "(" and ")"  and square brackets i.e. "[" and "]" we are permitted to  perform just the following two types  of processes:

(i) Changing the orientation of a parenthesis or a square bracket. That is, we can change ‘(’ into ‘)’, ‘)’ into ‘(’, ‘[’ into ‘]’, or ‘]’ into ‘[’. The price for doing any of these is 1
.
(ii) Metamorphosing a parenthesis into a square bracket or the other way around, but not altering its orientation. That is, we can metamorphose ‘(’ into ‘[’, ‘)’ into ‘]’, ‘[’ into ‘(’, or ‘]’ into ‘)’. The price for doing any of these is 2.

Write a C++ program to determine  the minimum price of transforming a given string into a correct parenthesization. In the answer book you need to write the logic, algorithm, analysis of the time and space complexity of the algorithm and  illustration of the working of your algorithm with two examples. 

Marks / 50:   C++ code 25, Logic 5, Algorithm 10, Time and space complexity analysis: 5 marks, Illustration: 5 marks.

Illustrative example
Input
](
Output
4
Explanation:  If the input string is “](”, then we can get the correct parenthesization “[]” by two change processes and one metamorphosis process, with total cost 4