By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,395 Members | 2,537 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,395 IT Pros & Developers. It's quick & easy.

removing brackets from input

P: n/a
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<charstrStack;
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

Oct 20 '07 #1
Share this Question
Share on Google+
13 Replies


P: n/a
On Sat, 20 Oct 2007 10:39:55 +0500, cront wrote:
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<charstrStack;
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.
Oct 20 '07 #2

P: n/a
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.

On Oct 19, 10:43 pm, arnuld <NoS...@NoPain.comwrote:
On Sat, 20 Oct 2007 10:39:55 +0500, cront wrote:
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<charstrStack;
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.

Oct 20 '07 #3

P: n/a
On Oct 20, 1:39 pm, cront <cr...@rocketship.comwrote:
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<charstrStack;
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);
}

Oct 20 '07 #4

P: n/a
On Sat, 20 Oct 2007 07:28:18 +0000, wizetux wrote:
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 ;-)

Oct 20 '07 #5

P: n/a
On Sat, 20 Oct 2007 11:34:21 +0000, robin wrote:
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.

Oct 20 '07 #6

P: n/a
"cront" <cr***@rocketship.comwrote in message
news:pa****************************@rocketship.com ...
>On Sat, 20 Oct 2007 11:34:21 +0000, robin wrote:


>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.
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.
Oct 20 '07 #7

P: n/a
"Jim Langston" <ta*******@rocketmail.comwrote in message
news:CR*************@newsfe06.lga...
"cront" <cr***@rocketship.comwrote in message
news:pa****************************@rocketship.com ...
>>On Sat, 20 Oct 2007 11:34:21 +0000, robin wrote:


>>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.

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[i] == '(' )
Left = i;
else if ( Input[i] == ')' && 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::stringInput;
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[i] << " - Output: " <<
RemoveParens( Input[i] ) << "\n";

}
Oct 20 '07 #8

P: n/a
On Oct 21, 2:11 am, cront <cr...@rocketship.comwrote:
On Sat, 20 Oct 2007 11:34:21 +0000, robin wrote:
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.
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?

Oct 21 '07 #9

P: n/a
On Sun, 21 Oct 2007 03:31:26 +0000, robin wrote:
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
Oct 21 '07 #10

P: n/a

On Sat, 2007-10-20 at 10:43 +0500, arnuld wrote:
On Sat, 20 Oct 2007 10:39:55 +0500, cront wrote:
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<charstrStack;
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,Smake_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.

Oct 21 '07 #11

P: n/a
On Oct 20, 8:33 pm, "Jim Langston" <tazmas...@rocketmail.comwrote:
"cront" <cr...@rocketship.comwrote in message
news:pa****************************@rocketship.com ...
On Sat, 20 Oct 2007 11:34:21 +0000, robin wrote:
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.
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.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Oct 21 '07 #12

P: n/a

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,Smake_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,Smake_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.

Oct 21 '07 #13

P: n/a
"cront" <cr***@rocketship.comwrote in message
news:pa****************************@rocketship.com ...
>On Sun, 21 Oct 2007 03:31:26 +0000, robin wrote:
>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
Oh, you want to throw away anything inside of the parenthesis? That's a
simple change.

Where i have:

else if ( Input[i] == ')' && 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[i] == ')' && 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;
}
Oct 22 '07 #14

This discussion thread is closed

Replies have been disabled for this discussion.