# Untitled

unknown

plain_text

a year ago

1.3 kB

10

Indexable

Never

^{}

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