Problem 1:17 points A common problem for compilers and text editors is to determ
ID: 3584995 • Letter: P
Question
Problem 1:17 points A common problem for compilers and text editors is to determine if the parentheses (or other brackets) in a string are balanced and properly nested. For example, the string "'0000" contains properly nested pairs of parentheses, but the string"00" does not; and the string "O)" does not contain properly matching parentheses. (a) 2 points] Give an algorithm that returns true if a string contains properly nested and balanced parentheses, and false if otherwise. Hint: At no time while scanning a legal string from left to right will you have encountered more right parentheses than left parentheses. (b) 13 points] Give an algorithm that returns the position in the string of the first offending d balanced. That is, if an excess right parenthesis parenthesis if the string is not properly nested an is found, return its position; if there are too many left parentheses, return the position of the first excess left parenthesis. Return -1 if the string is properly balanced and nested. (c) 2 points] Find the complexity of the two algorithms in part (a) and (b)Explanation / Answer
Code:
Please go through the code, have merged the code for the part(b) in this one only as its just a minor extension to the part(a).
Time Complexity: As we can see that the IsParanthesesBalanced() method has single for loop with conditional block so worst case complexity is O(N), where N is length of the string entered. Same is true for the part b as well.
Space complexity is O(N) in worst case for storing chars in stack.
Code------
#include<iostream>
#include<stack>
#include<string>
using namespace std;
// Function to check whether two characters have matching opening and closing of bracket type.
bool ArePair(char opening,char closing)
{
if(opening == '(' && closing == ')') return true;
else if(opening == '{' && closing == '}') return true;
else if(opening == '[' && closing == ']') return true;
return false;
}
bool IsParanthesesBalanced(string exp)
{
stack<char> S;
for(int i =0;i<exp.length();i++)
{
if(exp[i] == '(' || exp[i] == '{' || exp[i] == '[')
S.push(exp[i]);
else if(exp[i] == ')' || exp[i] == '}' || exp[i] == ']')
{
if(S.empty() || !ArePair(S.top(),exp[i])){
cout<<"voilated at instance: "<<i+1<<" ";
return false;
//uncomemnt below comment for part(b), and comment the above part.
//return i+1;
//return type of the method changes to int
}
else
S.pop();
}
}
return S.empty() ? true:false;
//return S.empty()? -1:S.size();
}
int main()
{
/*Code to test the function IsParanthesesBalanced*/
string expression;
cout<<"Enter paranthesis expression: ";
cin>>expression;
if(IsParanthesesBalanced(expression))
cout<<"Balanced ";
else
cout<<"Not Balanced ";
//Uncomment this part and comment the above for part(b).
/* if(IsParanthesesBalanced(expression)==-1)
cout<<"Balanced Expression ";
else
cout<<"Balancing voilated at: "<<IsParanthesesBalanced(expression);
*/
}