removing brackets from input

[cront]

I have a problem to work on:

we will ask user to input anything and we will put that back onto the
standard output with all set of brackets removed. We will not remove any
single bracket e.g.

INPUT: comp.lang.(c++)
OUTPUT: comp.lang.

INPUT: comp.lang.(c++
OUTPUT: comp.lang.(c++

INPUT: Bjarn)e St)roustr(up)
OUTPUT: Bjarn)e St)roustr

we do not want to remove any single opening or closing bracket. We are
interested in only set of brackets.


MY IDEA:

I am not able to decide which container to use. I thought of using
a Veoctr and only pushing input onto it if I am sure that I will not
find any closing bracket for the opening one. But how will I know I am
inside of set of brackets or I am just reading a single bracket. I was
reading about Stacks and came up with this code but it removes every
parethesis and elements following after a single opening parenthesis,
and since it is a Stack, it reverses all the input:

#include <iostream>
#include <stack>
#include <string>


int main()
{
std::stack<char> strStack;
bool P_ON = false;
char in_char;
while( std::cin >> in_char )
{
if( in_char == '(' )
{
P_ON = true;
}

if ( in_char == ')')
{
P_ON = false;
}

if( P_ON == false && in_char != ')')
{
strStack.push( in_char );
}
else if( P_ON == false && in_char == ')' )
{
strStack.push( ' ' );
strStack.push( '*' );
strStack.push( ' ' );
/* a '*' with space son both side will represent a set of parentheseis
removed */
}
}

/* print the stack with desired elements removed*/
std::cout << "\n------------ STACK after elements removed ---------------\n";
while( strStack.empty() == false )
{
std::cout << strStack.top();
strStack.pop();
}

std::cout << std::endl;


return 0;
}

=========== OUTPUT ============
/home/arnuld/programming/C++ $ ./a.out
comp.lang.(c++)

------------ STACK after elements removed ---------------
* .gnal.pmoc



/home/arnuld/programming/C++ $ ./a.out
comp.lan(g. (c++(using PAN)

------------ STACK after elements removed ---------------
* nal.pmoc

 

[arnuld]

I have a problem to work on:

we will ask user to input anything and we will put that back onto the
standard output with all set of brackets removed. We will not remove any
single bracket e.g.

INPUT: comp.lang.(c++)
OUTPUT: comp.lang.

.... [SNIP]........

#include <iostream>
#include <stack>
#include <string>


int main()
{
std::stack<char> strStack;
bool P_ON = false;
char in_char;
while( std::cin >> in_char )

HEY, that's my code (ugly though). Don't claim that you wrote it.

 

[wizetux]

The other way that you could do this is store the location in the
string in which the first occurrence of "(", and then continue. When
you come across the next ")", then just use the string.erase class
function to erase from the stored location to the current. Continue
until you get to the end of the original string.

we will ask user to input anything and we will put that back onto the
standard output with all set of brackets removed. We will not remove any
single bracket e.g.

INPUT: comp.lang.(c++)
OUTPUT: comp.lang.
.... [SNIP]........
#include <iostream>
#include <stack>
#include <string>

int main()
{
std::stack<char> strStack;
bool P_ON = false;
char in_char;
while( std::cin >> in_char )

HEY, that's my code (ugly though). Don't claim that you wrote it.

 

[robin]

I have a problem to work on:

we will ask user to input anything and we will put that back onto the
standard output with all set of brackets removed. We will not remove any
single bracket e.g.

INPUT: comp.lang.(c++)
OUTPUT: comp.lang.

INPUT: comp.lang.(c++
OUTPUT: comp.lang.(c++

INPUT: Bjarn)e St)roustr(up)
OUTPUT: Bjarn)e St)roustr

we do not want to remove any single opening or closing bracket. We are
interested in only set of brackets.

MY IDEA:

I am not able to decide which container to use. I thought of using
a Veoctr and only pushing input onto it if I am sure that I will not
find any closing bracket for the opening one. But how will I know I am
inside of set of brackets or I am just reading a single bracket. I was
reading about Stacks and came up with this code but it removes every
parethesis and elements following after a single opening parenthesis,
and since it is a Stack, it reverses all the input:

#include <iostream>
#include <stack>
#include <string>

int main()
{
std::stack<char> strStack;
bool P_ON = false;
char in_char;
while( std::cin >> in_char )
{
if( in_char == '(' )
{
P_ON = true;
}

if ( in_char == ')')
{
P_ON = false;
}

if( P_ON == false && in_char != ')')
{
strStack.push( in_char );
}
else if( P_ON == false && in_char == ')' )
{
strStack.push( ' ' );
strStack.push( '*' );
strStack.push( ' ' );
/* a '*' with space son both side will represent a set of parentheseis
removed */
}
}

/* print the stack with desired elements removed*/
std::cout << "\n------------ STACK after elements removed ---------------\n";
while( strStack.empty() == false )
{
std::cout << strStack.top();
strStack.pop();
}

std::cout << std::endl;

return 0;

}

=========== OUTPUT ============
/home/arnuld/programming/C++ $ ./a.out
comp.lang.(c++)

------------ STACK after elements removed ---------------
* .gnal.pmoc

/home/arnuld/programming/C++ $ ./a.out
comp.lan(g. (c++(using PAN)

------------ STACK after elements removed ---------------
* nal.pmoc

I'm not so clearly about what you want. In the case of "comp.lan(g. (c
++(using PAN)", is "comp.lan" the desired output, or "comp.lan(g. (c+
+" is?

If "comp.lan" is what you need, Wizetux's way should be able to work;
if you want the closest matching parentheses to be removed(the 2nd
output), I suggest using std::string::rfind(...) function to help.
"rfind()" function "searches a string in a backward direction for the
first occurrence of a substring that matches a specified sequence of
characters."

Here is my idea about the solution:

char ch(0);
string str;
while (cin >> ch)
{
if (')' == ch)
{
size_t pos = str.rfind('('); // find the last '(' in the
current string
if (string::npos != pos)
{
str.erase(pos, str.size()-pos);
continue;
}
}
str.push_back(ch);
}

 

[arnuld]

The other way that you could do this is store the location in the
string in which the first occurrence of "(", and then continue. When
you come across the next ")", then just use the string.erase class
function to erase from the stored location to the current. Continue
until you get to the end of the original string.

your solutio is ok for a single word because std:string read a word from
input what if this is the case:

INPUT: comp.lang.(c++ is the place) is in (USENET
OUTPUT: comp.lang. is in (USENET

string will not work because closing parenthesis is in another string
now BUT may be the OP is only concerned with the parenthesis in single
worda only, may be, may be not ;-)

 

[cront]

I'm not so clearly about what you want. In the case of "comp.lan(g. (c
++(using PAN)", is "comp.lan" the desired output, or "comp.lan(g. (c+ +"
is?

I want to remove the closest matching bracket-set.

 

[Jim Langston]

I want to remove the closest matching bracket-set.

What I would do, then, is simply start looking for a (. Once I found one,
start looking for a ). If I come across another (, save it's position
instead. Once I come acorss a ) I would remove both, then start over again.
Easier than trying to remove them all at once and it should take care of all
situations. Hmm.. even seems rather simple. I think I'll throw something
together real quick. Hope this isn't homework.

 

[Jim Langston]

What I would do, then, is simply start looking for a (. Once I found one,
start looking for a ). If I come across another (, save it's position
instead. Once I come acorss a ) I would remove both, then start over
again. Easier than trying to remove them all at once and it should take
care of all situations. Hmm.. even seems rather simple. I think I'll
throw something together real quick. Hope this isn't homework.

Output of the following program is:
Input: comp.lang.(c++) - Output: comp.lang.c++
Input: comp.lang.(c++ - Output: comp.lang.(c++
Input: Bjarn)e St)roustr(up) - Output: Bjarn)e St)roustrup
Input: This ((is) the) way (it (goes))) - Output: This is the way it goes)

#include <iostream>
#include <string>
#include <vector>

std::string RemoveParens( std::string Input )
{
bool Found = true;
while ( Found )
{
Found = false;
std::string::size_type Left = std::string::npos;
std::string::size_type Right = std::string::npos;
for ( std::string::size_type i = 0; i < Input.length(); ++i )
{
if ( Input == '(' )
Left = i;
else if ( Input == ')' && Left != std::string::npos )
{
Right = i - 1;
Input = Input.substr( 0, Left ) + Input.substr( Left + 1 );
Input = Input.substr( 0, Right ) + Input.substr( Right +
1 );
Left = std::string::npos;
Right = std::string::npos;
Found = true;
break;
}
}

}

return Input;
}

int main()
{
std::vector<std::string> Input;
Input.push_back("comp.lang.(c++)");
Input.push_back("comp.lang.(c++");
Input.push_back("Bjarn)e St)roustr(up)");
Input.push_back("This ((is) the) way (it (goes)))");

for ( int i = 0; i < Input.size(); ++i )
std::cout << "Input: " << Input << " - Output: " <<
RemoveParens( Input ) << "\n";

}

 

[robin]

I want to remove the closest matching bracket-set.

Oh, I got another question: what if there are enclosed bracket-set?

For example: what is the desired output for "a(b(c)d)"?

My above-mentioned solution would result in "a" as output. Is this
what you want?

 

[cront]

Oh, I got another question: what if there are enclosed bracket-set?

For example: what is the desired output for "a(b(c)d)"?

My above-mentioned solution would result in "a" as output. Is this
what you want?

yes, "a" should be the output but i did not get your these outputs:

Input: comp.lang.(c++)
Output: comp.lang.c++

it should output: comp.lang.


Input: comp.lang.(c++
Output: comp.lang.(c++

this is good.


Input: Bjarn)e St)roustr(up)
Output: Bjarn)e St)roustrup

It should output: Bjarn)e Str)roustr


Input: This ((is) the) way (it (goes)))
Output: This is the way it goes)

It should output: This way

 

[Tristan Wibberley]

I have a problem to work on:

we will ask user to input anything and we will put that back onto the
standard output with all set of brackets removed. We will not remove any
single bracket e.g.

INPUT: comp.lang.(c++)
OUTPUT: comp.lang.

.... [SNIP]........

#include <iostream>
#include <stack>
#include <string>


int main()
{
std::stack<char> strStack;
bool P_ON = false;
char in_char;
while( std::cin >> in_char )

HEY, that's my code (ugly though). Don't claim that you wrote it.

He/She even included this at the bottom:

=========== OUTPUT ============
/home/arnuld/programming/C++ $ ./a.out
comp.lang.(c++)

Your home directory?

Here's my quick attempt, not thoroughly checked and it's 6AM here so
there might be a few issues. run it then enter a line.

#include <istream>
#include <ostream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

/* second equal is a predicate that compares ".second" of the pair
** that it is created with to ".second" of the pair passed to
** it's operator(). Use it as a predicate to standard algorithms
*/
template<typename F, typename S>
struct second_equal
: public unary_function<const pair<F,S>, bool>
{
const pair<F,S>& target;
explicit second_equal(const pair<F,S>& target)
: target(target) {}
bool operator() (const pair<F,S>& src) const {
return src.second == target.second;
}
};

/* helper to make a second_equal predicate
** make_second_equal(some_pair) will create a predicate that
** can be passed to a standard algorithm
*/
template<typename F, typename S>
second_equal<F,S> make_second_equal(const pair<F,S>& target) {
return second_equal<F,S>(target);
}

int main()
{
vector<pair<string::iterator, unsigned int> > opens;
vector<pair<string::iterator, unsigned int> > closes;

string input;
getline(cin, input);

// get all the opens and closes in parallel
// save the nest-level
unsigned int n = 0;
for (string::iterator i = input.begin();
i != input.end(); ++i) {
switch (*i) {
case '(':
opens.push_back(make_pair(i, n++));
break;
case ')':
if (n != 0) closes.push_back(make_pair(i,--n));
break;
}
}

string output;

typedef vector<pair<string::iterator,
unsigned int> >::iterator iter;
string::iterator i = input.begin();

iter c = closes.begin();
for (iter o = opens.begin();
o != opens.end() && c != closes.end(); ++o) {
// skip any open braces that are in the pair found
// last time
if (o->first > c->first) continue;

copy(i, o->first, back_inserter(output));

iter match = find_if(c, closes.end(), make_second_equal(*o));
if (match == closes.end()) {
i = o->first;
continue;
}

c = match+1;
i = match->first+1;
}

copy(i, input.end(), back_inserter(output));
cout << output << endl;

}


--
Tristan Wibberley

Any opinion expressed is mine (or else I'm playing devils advocate for
the sake of a good argument). My employer had nothing to do with this
communication.

 

[James Kanze]

What I would do, then, is simply start looking for a (. Once
I found one, start looking for a ). If I come across another
(, save it's position instead. Once I come acorss a ) I would
remove both, then start over again. Easier than trying to
remove them all at once and it should take care of all
situations. Hmm.. even seems rather simple. I think I'll
throw something together real quick. Hope this isn't
homework.

This is easily solved by recursion, something like:

std::string
inputParen(
std::istream& source )
{
std::string result( 1, '(' ) ;
char ch ;
while ( source.get( ch ) && ch != ')' ) {
if ( ch == '(' ) {
result += inputParen( source ) ;
} else {
result += ch ;
}
}
return ch == ')' ? std::string() : result ;
}

std::string
input(
std::istream& source )
{
std::string result ;
char ch ;
while ( source.get( ch ) ) {
if ( ch == '(' ) {
result += inputParen( source ) ;
} else {
result += ch ;
}
}
return result ;
}

No need to explicitly memorize any positions anywhere.

Anytime someone mentions something like "matching parentheses",
recursion should automatically come to mind. Recursion is an
exact match for nested matching.

 

[Tristan Wibberley]

On Sun, 2007-10-21 at 05:20 +0000, I wrote:

....

Here's my quick attempt, not thoroughly checked and it's 6AM here so
there might be a few issues. run it then enter a line.

Bad, terrible, shameful.

This has a significant bug fixed (and is a bit more descriptive),
compare "foo(bar(baz)boo)a(bob(bip)goo)uuu"

#include <istream>
#include <ostream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

/* second equal is a predicate that compares ".second" of the pair
** that it is created with to ".second" of the pair passed to
** it's operator(). Use it as a predicate to standard algorithms
*/
template<typename F, typename S>
struct second_equal
: public unary_function<const pair<F,S>, bool>
{
const pair<F,S>& target;
explicit second_equal(const pair<F,S>& target) : target(target) {}
bool operator() (const pair<F,S>& src) const {
return src.second == target.second;
}
};

/* helper to make a second_equal predicate
** make_second_equal(some_pair) will create a predicate that
** can be passed to a standard algorithm
*/
template<typename F, typename S>
second_equal<F,S> make_second_equal(const pair<F,S>& target) {
return second_equal<F,S>(target);
}


/* first greater is a predicate that compares ".first" of the pair
** that it is created with to ".first" of the pair passed to
** it's operator(). Use it as a predicate to standard algorithms
*/
template<typename F, typename S>
struct first_greater
: public unary_function<const pair<F,S>, bool>
{
const pair<F,S>& target;
explicit first_greater(const pair<F,S>& target) : target(target) {}
bool operator() (const pair<F,S>& src) const {
return src.first > target.first;
}
};

/* helper to make a first_greater predicate
** make_first_greater(some_pair) will create a predicate that
** can be passed to a standard algorithm
*/
template<typename F, typename S>
first_greater<F,S> make_first_greater(const pair<F,S>& target) {
return first_greater<F,S>(target);
}


int main()
{
vector<pair<string::iterator, unsigned int> > opens;
vector<pair<string::iterator, unsigned int> > closes;

string input;
getline(cin, input);

// get all the opens and closes in parallel
// save the nest-level
unsigned int n = 0;
for (string::iterator i = input.begin();
i != input.end(); ++i) {
switch (*i) {
case '(':
opens.push_back(make_pair(i, n++));
break;
case ')':
if (n!=0) closes.push_back(make_pair(i,--n));
break;
}
}

string output;

typedef vector<pair<string::iterator,
unsigned int> >::iterator iter;
string::iterator i = input.begin();

iter c = closes.begin();
iter o = opens.begin();
while (o != opens.end() && c != closes.end()) {

c = find_if(c, closes.end(), make_first_greater(*o));
iter match = find_if(c, closes.end(), make_second_equal(*o));

if (match != closes.end()) {
c = match;
copy(i, o->first, back_inserter(output));
i = c->first+1;
o = find_if(o, opens.end(), make_first_greater(*c));
} else {
++o;
}
}

copy(i, input.end(), back_inserter(output));
cout << output << endl;

}


--
Tristan Wibberley

Any opinion expressed is mine (or else I'm playing devils advocate for
the sake of a good argument). My employer had nothing to do with this
communication.

 

[Jim Langston]

yes, "a" should be the output but i did not get your these outputs:

Input: comp.lang.(c++)
Output: comp.lang.c++

it should output: comp.lang.


Input: comp.lang.(c++
Output: comp.lang.(c++

this is good.


Input: Bjarn)e St)roustr(up)
Output: Bjarn)e St)roustrup

It should output: Bjarn)e Str)roustr


Input: This ((is) the) way (it (goes)))
Output: This is the way it goes)

It should output: This way

Oh, you want to throw away anything inside of the parenthesis? That's a
simple change.

Where i have:

else if ( Input == ')' && Left != std::string::npos )
{
Right = i - 1;
Input = Input.substr( 0, Left ) + Input.substr( Left + 1 );
Input = Input.substr( 0, Right ) + Input.substr( Right +
1 );
Left = std::string::npos;
Right = std::string::npos;
Found = true;
break;
}

which gets rid of only the parenthsis, just change it to (untested code, may
be off by one)

else if ( Input == ')' && Left != std::string::npos )
{
Right = i;
Input = Input.substr( 0, Left ) + Input.substr( Right );
Left = std::string::npos;
Right = std::string::npos;
Found = true;
break;
}