C++

Forum

 
C++ Primer exercise 9.52, std::stack

closed account (EwCjE3v7)
Before I start I would like to put out there that this is not my homework, I`m learning c++ myself

So I have the following exercise but have no way on doing it:
Use a stack to process parenthesized expressions. When you see an open parenthesis note that it was seen. When you see a close parenthesis after an open parenthesis, pop elements down to and inclusing the open parenthesis off the stack. push a value onto the stack to indicate that a parenthesized expression was repalaced



I wrote the following but it didnt work

Could someone please try the exercise or try to point me in the right way. Thank you :)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
int main()
{
	stack<char> sc;
	char input;
	bool opn_par = false;

	while (cin >> input) {
		if (input == '(')
			opn_par = true;
		else
			sc.push(input);

		if (input == ')' && opn_par == true) {
			char p = sc.top();

			while (p != '(') {
				sc.pop();
			}
		}
	}
}
ne555 (10692)
> this is not my homework, I`m learning c++ myself
It is your homework. http://en.wikipedia.org/wiki/Homework#Main_objectives_and_reasons_for_homework

> but it didnt work
http://www.cplusplus.com/forum/articles/40071/#msg218019


1
2
3
4
5
 
char p = sc.top();

while (p != '(') {
	sc.pop();
}
¿what do you think you are doing there?
closed account (EwCjE3v7)
@ne555

Well what I meant by "not homework" was that I have not been assigned it by a teacher, I`m learning C++ myself

Yea I should have abbreviated more, sorry bout that.

Oh I did something wrong there, I modified my code but I still get 
segmentation fault
.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
int main()
{
	stack<char> sc;
	char input;
	unsigned counter = 0;

	while (cin >> input) {
		if (input == '(')
			++counter;
		else
			sc.push(input);

		if (input == ')' && counter > 0) {
			char p = sc.top();
			
			while (counter != 0) {
				while (p != '(') {
					sc.pop();
				}
				if (p == '(') {
					--counter;
					sc.pop();
				}
			}
		}
	}
}


I just dont even really understand this exercise fully. Like does it want me to remove all parenthesized expressions i.e (hey) and but a value on it like 1, to show that there has been a parenthesized expression removed?
Yanson (885)
I just dont even really understand this exercise fully. Like does it want me to remove all parenthesized expressions i.e (hey) and but a value on it like 1, to show that there has been a parenthesized expression removed?

sounds right to me.

p is never going to equal '(' for one thing you never put '(' on the stack in the first place, but also because you don't update the value of p

EDIT
before you call pop it would be wise to make sure there is something to pop eg !sc.empty()
Last edited on
closed account (EwCjE3v7)
Thank you, I do not know what I was thinking in my previous codes but here is the updated and hopefully working one. However I still have one question. How do I go through all the elements of a std;:stack. The underlying type is std::deque right?

Can someone give me an example of printing out the elements of a std::stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
int main()
{
	stack<char> sc;
	char input;
	unsigned counter = 0;

	while (cin >> input) {
		if (input == '(')
			++counter;
		sc.push(input);
		if (input == ')' && counter > 0) {
			char p;
			
			while (counter != 0 && !sc.empty()) {

				p = sc.top();

				if (p == '(')
					--counter;

				sc.pop();
			}
			if (counter == 0)
				sc.push('1');
		}
	}
}
keskiverto (10365)
The idea of a stack is that you only see the top element. To print them out, you could:
1
2
3
4
 
while ( ! sc.empty() ) {
  std::cout << sc.top();
  sc.pop();
}

The side-effect is that the stack is empty after the operation.


Test your implementation with something like (()(()))()(()
Last edited on
closed account (EwCjE3v7)
Okay so I implemented that but I when I give it your input the output is: 
(((((((


But I do not know why, when p = (, it should decrement counter, pop it out and then put a 1 there. But it dosnt. I do not understand. Can someone explain please. Thank you

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
int main()
{
	stack<char> sc;
	char input;
	unsigned counter = 0;

	while (cin >> input) {
		if (input == '(')
			++counter;
		sc.push(input);
		if (input == ')' && counter > 0) {
			char p;
			
			while (counter != 0 && !sc.empty()) {

				p = sc.top();

				if (p == '(')
					--counter;

				sc.pop();
			}
			if (counter == 0)
				sc.push('1');
		}
			while (!sc.empty()) {
  				std::cout << sc.top();
  				sc.pop();
			}
	}
}
keskiverto (10365)
Matching pairs has three possibilites:
1
2
3
4
5
6
7
8
9
10
11
12
13
 
stack<char> sc;
char input;
while (cin >> input) {
  if ( '(' == input ) {
    sc.push(input);
  }
  else if ( ')' == input ) {
    if ( sc.empty() ) // unmatched )
    else sc.pop();
  }
}
if ( ! sc.empty() ) // unmatched (
else // all were matched

1. Every ( is matched by )
2. There is more ( than )
3. There is more ) than (

I cannot see directly, where your code goes haywire.
ne555 (10692)
> while (counter != 0 && !sc.empty())
Suppose that your stack is '(()', counter should be 2.
Your while condition will make you empty the stack.


Also, line 26 executes after every input, so you are destroying the stack at each step
closed account (EwCjE3v7)
Okay so I fixed the emptying the stack on every input but I do not know how to tackle the first problem:

>
while (counter != 0 && !sc.empty())
Suppose that your stack is '(()', counter should be 2.
Your while condition will make you empty the stack.


Any suggestions?

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
int main()
{
	stack<char> sc;
	char input;
	unsigned counter = 0;

	while (cin >> input) {
		if (input == '(')
			++counter;
		sc.push(input);
		if (input == ')' && counter > 0) {
			char p;
			
			while (counter != 0 && !sc.empty()) {

				p = sc.top();

				if (p == '(')
					--counter;

				sc.pop();
			}
			if (counter == 0)
				sc.push('1');
		}
	}
	while (!sc.empty()) {
  		cout << sc.top();
  		sc.pop();
	}
	cout << endl;
}
ne555 (10692)
When you see a close parenthesis (...), pop elements down to and including the open parenthesis off the stack.
Last edited on
keskiverto (10365)
My earlier example did consider only the parentheses and the three possible scenarios. Keeping the content obviously requires a bit more. Perhaps something like:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
stack<char> sc;
char input;
while (cin >> input) {
  if ( ')' == input ) {
    char out = 0;
    std::string word {""};
    while ( ! sc.empty ) {
      out = sc.top();
      sc.pop();
      if ( '(' == out ) break;
      word = out + word;
    }
    std::cout << word << '\n';
    if ( '(' != out ) {
      std::cout << "Unmatched ).\n";
      return 2;
    }
    sc.push( '1' );  // an expression was 'ere
  }
  else {
    sc.push(input);
  }
}

// outmost statements
std::string word {""};
while ( ! sc.empty ) {
  const char out { sc.top() };
  sc.pop();
  if ( '(' == out ) {
    std::cout << "Unmatched (.\n";
    return 1;
  }
  word = out + word;
}
std::cout << word << '\n';
closed account (EwCjE3v7)
Thank you guys for all your help. I appreciate it very much. I have copied your code keskiverto with just 1 modification, it defines the string once so we know that we have closed all the expressions. i.e input: (()) output: 11. So yep that`s it. Thank you guys

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
int main()
{
	stack<char> sc;
	string s;
	char input;

	while (cin >> input) {

		if (input == ')') {
			char p;

			while (!sc.empty()) {
				p = sc.top();
				sc.pop();
				if (p == '(') {
					break;
				}
				s = p + s;
			}
			if (p != '(') {
				cerr << "Unmatched )." << endl;
				return -1;
			}
			sc.push('1');
		} else
			sc.push(input);
	}
	while (!sc.empty()) {
		if (sc.top() == '(') {
			cerr << "Unmatched )." << endl;
			return -1;
		}
		s = sc.top() + s;
		sc.pop();
	}
	cout << s << endl;
}
Last edited on
cire (8284)
Here's another approach for you to play with. You can uncomment the code in the parens_balance function if you want some text that reflects the structure of the parenthetic expressions encountered.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
// http://ideone.com/urWb1n
#include <stack>
#include <string>
#include <iostream>
#include <array>
#include <iomanip>
#include <utility>

std::string quote(std::string s)
{
    return '"' + s + '"';
}

template <typename T>
T pop_top(std::stack<T>& stack)
{
    T result = stack.top();
    stack.pop();
    return result;
}

// returns a bool/index pair.  If .first is true, then the parens balance, and .second
// should be ignored.  If .first is false, then the parens don't balance, and .second
// is the "index" where the offending paren was found, or if more parens were required
// it is one past the end.
std::pair<bool, std::size_t> parens_balance(const std::string& s)
{
    unsigned left_paren_count = 0;
    unsigned right_paren_count = 0;
    // char expression = 'a' ;

    std::stack<char> stack;

    auto ss = s.begin();
    while (ss != s.end())
    {
        char ch = *ss++;

        if (ch == '(')
        {
            stack.push(ch);
            // stack.push(expression++);

            ++left_paren_count;
        }
        else if (ch == ')')
        {
            if (++right_paren_count > left_paren_count || stack.empty())
                return std::make_pair(false, ss - s.begin() - 1);

            // auto indent_level = left_paren_count - right_paren_count;

            while (!stack.empty() && (ch = pop_top(stack)) != '(')
                /*std::cout << std::string(indent_level, ' ') << ch << '\n'*/;
        }
    }

    std::size_t index = s.size();
    if (stack.empty() && left_paren_count < right_paren_count)
        --index;

    return std::make_pair(stack.empty() && left_paren_count == right_paren_count, index);
}

void report_unbalanced_parens(const std::string& expr, std::size_t index)
{
    std::cout << "Unbalanced parentheses detected in " << quote(expr) << ":\n\t";
    std::cout << expr << "\n\t";
    std::cout << std::string(index, ' ') << "^\n";
}

int main()
{
    std::array<std::string, 10> expressions = 
    { 
        "(()(()))()(()",        // invalid
        "(()(()))()(())",       // valid
        "()",                   // valid
        ")",                    // invalid
        "(",                    // invalid
        "()()()",               // valid
        "(((()))((())))",       // valid
        "))((",                 // invalid
        "())(",                 // invalid
        "(()(",                 // invalid
    };

    for (auto& expression : expressions)
    {
        auto ret = parens_balance(expression);
        if (ret.first)
            std::cout << quote(expression) << " has balanced parentheses.\n";
        else
            report_unbalanced_parens(expression, ret.second);

        std::cout << '\n';
    }
}
closed account (EwCjE3v7)
@cire Oh thank you for the code, I`ll run it but I cannot understand some of it. Templates and some other stuff.

Thanks for the code. I`ll save it and will check it out once I learn templates.
Topic archived. No new replies allowed.