C++

Forum

 
 
Balanced parentheses - linked list and stack problem

tina2014 (10)
I have to make a code, that checks if parentheses are balanced using stack and linked list.
Here is the code that my friend made for me , without explaining(i did 'pairs' part and things with loops). Can anyone explain what is happening under 'int pop' and 'check' parts? I have problems with understanding this part of c++ (stacks and l.lists that are implemented), and i don't have anyone who can explain it and who have time. I've tried many things, but i really don't understand 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
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
 
  #include<iostream>
    #include <string>
    using namespace std;
     
    struct node 
    {
       char data;
       node *link;
    };
    
    int pop(node *&stack)  //removing an element
    {
    	char result;
      	node *top=new node;
        top=stack;
        result=top->data;
        stack=top->link;	
    	delete top; 
        return result; 
    }
    
    bool Pairs(char openP,char closedP)
    {
    if(openP == '(' && closedP == ')') return true;
    else if(openP == '{' && closedP == '}') return true;
    else if(openP == '[' && closedP == ']') return true;
    else return false;
    }
     
    bool Check(string exp) 
    {
       int i=0;
       node *stack=NULL;
       	while(exp[i]) 
       	{
        	if(exp[i]=='(' || exp[i]=='[') 
    	       {
    				node *neww=new stack;
    			  	neww->data=exp[i];
    				neww->link=stack;  
    			  	stack=neww; 
    			}
          	if(exp[i]==')' || exp[i]==']')
    	      {
    	         if(stack==NULL)
    	        	return 0; 
    	         else if (Pairs(pop(stack), exp[i])==0)  
    	           	return 0;							
    	      }
          	i++;
       	}
       	if(stack==NULL)
    		return 1;
      	else
        	return 0;
    } 
     
    int main()
    {
      	string exp;
     	cout<<"Enter parentheses:\n";
    	cin>>exp;
     	if(Check(exp)!=0)
        	cout<<"P. are  balanced";
      	else 
        	cout<<"P. are not balanced";  
     	return 0;
    }


EDIT:
does anyone know any other way to improve those parts? make code easier to understand?
Last edited on
MiiNiPaa (8886)
Basically it uses stack to store opening braces it encounters and when it sees closing brace it checks if top of the stack (last encountered opening brace) matches it. If so, top brace is removed from stack (braces "destroy" each other). If braces does not match or if there is no opening brace for closing, or if there is unmatched opening braces, function returns false. Otherwise it returns true.

However most of the code is custom stack handling. it is better to use standard container for that.
Improved 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
33
34
35
36
37
38
39
 
#include<iostream>
#include<string>
#include<stack>


bool balanced(std::string input)
{
    static const std::string op_braces = "({[";
    static const std::string cl_braces = ")}]";

    std::stack<char> braces;
    for(auto c: input) {
        auto pos = std::string::npos;
        if (op_braces.find(c) != std::string::npos) {
            braces.push(c);
        } else if ( (pos = cl_braces.find(c)) != std::string::npos ) {
            if (braces.empty())
                return false;
            if (braces.top() == op_braces[pos])
                braces.pop();
            else
                return false;
        }
    }
    if (!braces.empty())
        return false;
    return true;
}


int main ()
{
    std::string input;
    std::getline(std::cin, input);
    std::cout << "That expression " << (balanced(input) ? "contains" :
                                                          "does not contain") <<
                 " matching group symbols\n";

}
tina2014 (10)
Thank you for your reply, but i need to use this part as struct, node and so on.
I see that i wasn't quite clear with my question, so i need help with explenation for following parts:

1
2
3
4
5
6
7
8
9
10
 
int pop(node *&stack)  //node that points to address of a stack?
{
    char result;
    node *top=new node; //how can i explain this?
    top=stack; //why are we equalizing top with stack?
    result=top->data;//i dont understand
    stack=top->link;//dont understand   
    delete top; 
    return result; 
}


and 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
bool Check(string exp) 
{
   int i=0;
   node *stack=NULL;
    while(exp[i]) 
    {
        if(exp[i]=='(' || exp[i]=='[') 
           {
                node *neww=new stack;//dont understand
                neww->data=exp[i];//dont understand
                neww->link=stack; //-II- 
                stack=neww; //-II-
            }
        if(exp[i]==')' || exp[i]==']')
          {
             if(stack==NULL)
                return 0; 
             else if (Pairs(pop(stack), exp[i])==0) //what does mean this part in parentheses? 
                return 0;                           
          }
        i++;
    }

code works as it should :/
MiiNiPaa (8886)
int pop(node *&stack) it is a function taking pointer to node by reference (that means it can change that pointer) and returns integer.

node *top=new node; Memory leak. We are declaring pointer to node, allocating memory for node and assigning pointer to freshly allocated memory to top
http://www.cplusplus.com/doc/tutorial/dynamic/

top=stack;We are assigning stack pointer to top. Now they both points to the same object

Previous two lines should be: node* top = stack;

result=top->data; Accessing data member of node object held in top. and storing it in result variable
http://www.cplusplus.com/doc/tutorial/classes/ (Pointers to classes)

stack=top->link; Extracting pointer to the next element and assigning stack variable to it, effectively removing top element from stack


node *neww=new stack mistake, should be node* neww = new node; creates node object in memory and assigning its address to neww pointer.

neww->data=exp[i]; storing brace character in data field.

neww->link=stack; Make link member point to therest of the stack
stack=neww; And make pointe to the beginning of stack point to the new node.

(Pairs(pop(stack), exp[i])==0) It takes top value from stack, removing it (pop(stack)) and i'th character from string (exp[i]) which is one of the closing braces due to previous if; passes them to the Pairs function (which checks if pairs match) and compares result to 0 ("if pairs really match")


I must warn that those C-like stack manipulations have several sources of memory leaks.
tina2014 (10)
ok, great, thanks! now it's a bit clearer to me :)
is it possible to make it in any other way? as i said, we must use nodes, linked list, stack and all of that..
i'm learning now and i want to understand other ways too..
thanks in advance!
MiiNiPaa (8886)
My code does use stack. It is just neatly encapsulated inside class, hiding internals, giving comfortable interface and eliminating most user errors.

If you absolutely need to implement your own stack, you can:
1) make your own class (C++ way)
2) Use current approack (C way) but move lines 38-41 in its own push() function. Also add clear() function to lear content and free memory.
2a) I would switch from single linked list to array for the sake of simplicity and safety.
tina2014 (10)
can i make something like:

1
2
3
4
5
6
7
 
int push(node* &top)
{
node *stack= new node;
stack->data=exp[i];
top=stack;
top->next=NULL
}


before 'int pop'
and than in while loop something like:

1
2
3
4
5
6
 
while(exp[i]) 
    {
        if(exp[i]=='(' || exp[i]=='[') 
           {
                (Pairs(push(stack), exp[i])==0)
            }


probably, not, but as i said, i have big problems with this part :S
MiiNiPaa (8886)
Your push function should be:
1
2
3
4
5
6
7
 
void push(node*& stack, char value)
{
    node* new_node = new node;
    new_node->data = value;
    new_node->link = stack;  
    stack = new_node;
}

And usage:
35
36
37
38
39
 
//...
if(exp[i]=='(' || exp[i]=='[') {
    push(stack, exp[i]);
}
//...
Last edited on
tina2014 (10)
EDIT:
what's the difference between node*& stack and node *&stack?

furthermore, is this than ok?

1
2
3
4
5
6
7
 
void pop(node *&top, char data)
{
node* toDelete = top;
data = top->data;
top = top->link;
delete toDelete;
}


i found this in script from class
would it be ok? and how do i change than code in while loop for pop part?
Last edited on
MiiNiPaa (8886)
what's the difference between node*& stack and node *&stack?
In space location. Functionally there is no difference.

furthermore, is this than ok?
Your pop function in current code is returning popped value. I have already told you how to modify your pop() function to eliminate memory leak.
You will have to define top() function and modify your code if you want your pop() function to be void.

tina2014 (10)
and when i would have something like this

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
void push(node*& stack, char value)
{
    node* new_node = new node;
    new_node->data = value;
    new_node->link = stack;  
    stack = new_node;
}

char pop(node *&stack)
{
node *toDelete = stack;
char result = stack->data;
stack=stack->link;
delete toDelete;
return result;
}


why void function?
MiiNiPaa (8886)
Yes, it is correct.

why void function?
If you are talking about push() function it is because it does not need to return anything.
If you are talking about my remark in previous post, there is two good reasons that standard library stack separates top() from pop(), both are not applicable in your situation however. http://cpptruths.blogspot.ru/2005/10/why-does-stdstackpop-returns-void.html

Now you only need clear() function which will free all memory used by stack and call it before you return from your check function.
tina2014 (10)
i'm affraid that we didn't learn clear function :/
can you explain it in short?

btw, how can i write this part in some other way?

else if (Pairs(pop(stack), exp[i])==0)

Thank you very very much for your help, i really appreciate it!
MiiNiPaa (8886)
can you explain it in short?
1
2
3
4
5
6
7
8
 
void clear(node*& stack)
{
    while(stack) {
        node* top = stack;
        stack = stack->link;
        delete top;
    }
}
Place calls to clear() in every place where stack is not empty when you return (between lines 47-48 and 54-55 in your original code)
how can i write this part in some other way?
47
48
49
50
51
 
else {
    char top_brace = pop(stack);
    if ( !Pairs(top_brace, exp[i]) )
        return 0;
}
tina2014 (10)
ok, i need your help for one last time, i promise :)
i don't know how would i explain this to someone, i mostly understand code, but i don't know how to explain it in words.. if you have time, i would be gratefull :)

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
 
#include<iostream>
#include <string>
using namespace std;
     
    struct node //we make stucture 'node'
    {
       char data; //type char, name data
       node *link; //node that points to link? why?
    };
    
   void push(node*& stack, char value)//ok, void because push function doesn't need to return anything
{
    node* new_node = new node; //we are declaring pointer to node
    new_node->data = value;//whats happening here?
    new_node->link = stack;  //and here?
    stack = new_node;//and here?
}

char pop(node *&stack)//for removing 
{
node *toDelete = stack;//we are saving the head
char result = stack->data;//saving the data at the top of the stack
stack=stack->link;//we make the next node in the stack - the new head
delete toDelete;//we delete it
return result;//why do we have to return the result?
}
    bool Pairs(char openP,char closedP)//ok, even i understand this part :D
    {
    if(openP == '(' && closedP == ')') return true;
    else if(openP == '{' && closedP == '}') return true;
    else if(openP == '[' && closedP == ']') return true;
    else return false;
    }
     
    bool Check(string exp) 
    {
       int i=0;//why do we equal i with 0?
       node *stack=NULL;//this checks if stack is empty or?
       	while(exp[i]) //how would you say this in words, i get it but dont know how to explain to someone else
       	{
        	if(exp[i]=='(' || exp[i]=='[')
			{
			push(stack, exp[i]);//this to, in words..?
			}
          	if(exp[i]==')' || exp[i]==']')
    	      {
    	         if(stack==NULL)//why?
    	        	return 0; 
    	         else 
				 {
					char top_brace = pop(stack);//in words?
					if ( !Pairs(top_brace, exp[i]) )
					return 0;
				 }							
    	      }
          	i++;//why i++? it's going to next element?
       	}
       	if(stack==NULL)//if stack is empty, return true; why do we need this part?
    		return 1;
      	else
        	return 0;
    } 
     
    int main()
    {
      	string exp;
     	cout<<"Enter parentheses:\n";
    	cin>>exp;
     	if(Check(exp)!=0)
        	cout<<"P. are  balanced";
      	else 
        	cout<<"P. are not balanced";  
     	return 0;
    }

MiiNiPaa (8886)
node *link; //node that points to link? why?
It is variable called link which is of type pointer to node. It will hold address of next node in chaint, so you could follow it from the beginning (your stack variable) to the end (when link winn hold null pointer)

new_node->data = value;//whats happening here?
We are setting data variable of newly created node to the passed value - saving it.

new_node->link = stack; //and here?
Setting first node of stack as next node for our new node

stack = new_node;//and here?
Setting our new node as first in stack

Whole function inserts new node at the beginning of stack


return result;//why do we have to return the result?
Whole point of stack is to store values. You do want to have some way of getting it back, right?

int i=0;//why do we equal i with 0?
we set integer i to zero because array indexes starts with 0

node *stack=NULL;//this checks if stack is empty or?
This sets stack pointer to null. It is special value of «no valid data here»

while(exp[i]) //how would you say this in words, i get it but dont know how to explain to someone else
First of all: this will only reliably work in C++11. On older version of standard it is undefined behavior.
It loops untill it encounters '\0' character, which is always terminates c-string. std::string was not guaranteed to have terminated 0 before C++11.

push(stack, exp[i]);//this to, in words..?
Save character in exp[i] on stack.

if(stack==NULL)//why?
If we found closing brackets, but there is no unmatched opening, than brackets are not balanced

i++;//why i++? it's going to next element?
You do want your loop to check next character instead of one over and over, right?

if(stack==NULL)//if stack is empty, return true; why do we need this part?
If there is no unmatched opening braces left, then brackets are balanced, else they are not.
Topic archived. No new replies allowed.