A common problem for compilers and text editors is to determine if the parenthes

Question

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 "((())())()" contains properly nested pairs of parentheses, but the string ")()(" does not, and the string "())" does not contain properly matching parentheses.

a)Give an algorithm that returns true if a string contains properly nested and balanced parentheses,and false otherwise.Use a stack to keep track of the number of left parentheses seen so far.Hint:At no time while scanning a legal string from left to right will you have encountered more right parentheses than left parentheses.

b)Give an algorithm that returns the position in the string of the first offending parenthesis if the string is not properly nested and balanced.That is,if an excess right parenthesis 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.Use a stack to keep track of the number and positions of left parentheses seen so far.

Explanation / Answer

please rate - thanks

hope this is what you are looking for,

you actually gave the algorithm, so I gave the code

when get a(push ( into stack, when get a ) pop the stack

if stack empty not balanced. or if get to string end, and stack not empty not balanced

#include<iostream>
using namespace std;
char pop(char[], int& );
void push(char[],int&,int, char) ;
bool checkinput(string,int,char[]);
int main()
{ int maxsize=20;
char stack[maxsize];
string input;
bool good;
cout<<"Enter the string who's parenthesis you want checked: ";
cin>>input;
good=checkinput(input,maxsize,stack);
if(good)
    cout<<"valid parenthesis ";
else
     cout<<"invalid parenthesis ";
system("pause");
return 0;
}
bool checkinput(string input,int maxsize,char stack[])
{char m=' ';
char opens='(';
char closes=')';
int n=0,i=0,j;
while(input[i]!='')
   {if(input[i]==opens)
            push(stack,n,maxsize,input[i]);
        else
            if(input[i]==closes)
                 { m=pop(stack,n);
                     if(m!=opens)
                        return false;
                      
                  }
     
    i++;
    }
if(n==0)
   return true;
else
    return false;
}   
char pop(char a[], int& n)
{if (n <= 0)
        {cout<<"Stack underflow ";
          return 'x';
          }
   n--;
   return a[n];
}
void push(char a[], int& n, int maxsize, char val)
{if (n >= maxsize)
        {cout<<"Stack overflow - program aborted ";
          system("pause");
          system("exit");
          }
   a[n] = val;
   n++;
   return;
}

---------------------------------------------------------

when get a(push ( and it's position into the stack, when get a ) pop the stack and the position

if stack empty not balanced at position 0. or if get to string end, and stack not empty not balanced, pop stack and get position of where error is

note now push pushes 2 items, pop pops 2 items

#include<iostream>
using namespace std;
char pop(char[], int&,int& );
void push(char[],int&,int, char,int) ;
int checkinput(string,int,char[]);
int main()
{ int maxsize=20;
char stack[maxsize];
string input;
int good;
cout<<"Enter the string who's parenthesis you want checked: ";
cin>>input;
good=checkinput(input,maxsize,stack);
if(good==-1)
    cout<<"valid parenthesis ";
else
     cout<<"invalid parenthesis position "<<good<<" ";
system("pause");
return 0;
}
int checkinput(string input,int maxsize,char stack[])
{char m=' ';
char opens='(';
char closes=')';
int n=0,i=0,j;
while(input[i]!='')
   {if(input[i]==opens)
            push(stack,n,maxsize,input[i],i);
        else
            if(input[i]==closes)
                 { m=pop(stack,n,j);
                     if(m!=opens)
                        return j;                      
                  }     
    i++;
    }
if(n==0)
   return -1;
m=pop(stack,n,j);
return j;
}   
char pop(char a[], int& n,int& pos)
{if (n <= 0)
        {cout<<"Stack underflow ";
          return 'x';
          }
   n--;
   pos=a[n];
   n--;
   return a[n];
}
void push(char a[], int& n, int maxsize, char val,int pos)
{if (n >= maxsize-1)
        {cout<<"Stack overflow - program aborted ";
          system("pause");
          system("exit");
          }
   a[n] = val;
   n++;
   a[n]=pos;
   n++;
   return;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.