HW Assignment - Checking Brackets using Stack

Question

YoTaMiX 0 Light Poster

20 Years Ago

Hello to you all ,

I am required to write a program which gets a Math Expression (without checking it is good) and put in Stack only the Brackets .
Implementation of Stack is One-Way Linked List Only.

Examples for Good/Bad Expressions :
(a*{b+c}-4/x +[e-5]) - GOOD
(5+} - BAD
(5+{6*)-2} - BAD
(5+z - BAD

I have build up a Mechanism which checks for each entered char (other than Enter Key and also using closing brackets such as ) or ] or } at the beginning of Expression) what type of bracket it is and pushes it into a stack (we must use LIFO technique for check legal Expression).

I thought of 2 cases :

first case : for each open bracket there is a closing one so i check top of stack to bottom of stack and carry on till i reach to middle .
second case : what happens if i have this sequence - ()[]{} - meaning i need to check top against the next , and so on (top of stack to bottom of stack will not help in this case)

I kinda stuck on Algorithm Think Phase :-)

Code Added . Any Ideas ?

Thank you , Yotam , Israel

algorithm-pseudocode c linked-list

STACK6.C (1.62 KB)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct Node
{	char data;
	struct Node *next;
}node;

void push(char);
void display_stack();

node  *top;

int  main()
{
 char temp[80];
 int i=0,counter=0;
 clrscr();
 printf("\nEnter Math Expression\n");
 top=NULL;
 temp[i]=getche();
 if ( (temp[i]==')') || (temp[i]==']') || (temp[i]=='}') )
    { printf("\n Bad Expression! Run it Again... \n"); getch(); return 1; }
 else
  {
  while ( (int)temp[i]!=13 )
    {

    switch (temp[i])
       {
       case '(': { push(temp[i]); counter++; break; }
       case ')': { push(temp[i]); counter++; break; }
       case '[': { push(temp[i]); counter++; break; }
       case ']': { push(temp[i]); counter++; break; }
       case '{': { push(temp[i]); counter++; break; }
       case '}': { push(temp[i]); counter++; break; }
       }
     ++i;
     temp[i]=getche();
     }
  }

if ( (counter%2)!=0 ) printf("Bad Expression! \n");
else { display_stack(); }

return 0;
}


void push(char y)
{
	node *ptr;
	ptr=malloc(sizeof(node));
	ptr->data = y;
	ptr->next = top;
	top = ptr;
}

void display_stack()
 {
 int i =0;
 node * temp;
 temp = top;
 while(temp!=NULL)
  {
  printf("\nNode #%2d  :  Value= %c    next %5x ",i++,temp->data,temp->next);
  temp=temp->next;
  }
 }

/* REMOVES TOP NODE FROM  THE STACK AND RETURNS ITS VALUE*/

int pop()
{
  char a;
  if(top==NULL)
     { printf("\n\t\tSTACK EMPTY...\n\n"); return 0; }
  else
    {
    a=top->data;
    printf("\n\n\nB4 pop: value 2B returned : %c ",a);
    free(top);
    top=top->next;
    return a;
    }
}

4 Contributors
6 Replies
298 Views
3 Years Discussion Span
Latest Post 16 Years Ago Latest Post by Berkut

Dani AI

Generated 9 Months Ago

The standard LIFO approach does exactly what you need: push every opening bracket, and when you see a closing bracket pop the most recent opening and compare. That handles both nested cases (e.g. "{(…)}") and sequential pairs (e.g. "()[]{}") — you always compare the most-recent unmatched open to the next close, so you never need to scan the whole stack. That resolves the “top-to-bottom won’t work for ()[]{}” worry from : it does work, because each completed pair is popped immediately.

A few implementation points that commonly break students’ code:

Never free a node and then access it. Do not do: free(top); top = top->next; — that dereferences freed memory. Instead capture what you need, advance the head, then free the old node. Example pop pattern:

char pop(void) {
    if (!top) return '\0';   // indicate empty
    Node *tmp = top;
    char ch = tmp->bracket;
    top = tmp->next;
    free(tmp);
    return ch;
}

Match brackets explicitly rather than relying on ASCII arithmetic (that varies and is error-prone). For example:

int matches(char open, char close) {
    return (open=='(' && close==')') ||
           (open=='[' && close==']') ||
           (open=='{' && close=='}');
}

Read the whole input line with fgets (safer than getche) and iterate until '\0' or '\n' (watch for Windows CR '\r'). Check for a closing bracket when the stack is empty (error), and after the scan ensure the stack is empty (otherwise unmatched opens).

Quick debugging checklist: add unit tests for ")(", "([)]", "()[]{}", and "({[]})"; verify your pop returns a clear “empty” indicator; ensure switch/case handling has breaks to avoid fall-through; and run under a debugger to catch use-after-free. ’s high-level logic is correct — just fix the memory order and the matching test — and if you later want to evaluate the arithmetic once parentheses are balanced, look into the shunting-yard or two-stack evaluation techniques mentioned by .

All 6 Replies

dude543 2 Light Poster

20 Years Ago

The logic should be like this :
   while ( input != 13 )
      {
       if input is '(' or '{' or '[' or ')' or '}' or ']' 
          {
          if input is '(' or '{' or '['
              push it into the stack.
          else if input is  ')' or '}' or ']' 
              {
              if stack is empty
                       report error.
              pop cell from stack
              if cell "matches input" 
                       we are ok.
              else if cell dont "matches input" or stack is empty 
                       report error.
              }
          }
      }
   if  the stack is not empty
        report error.

Also I would suggest replacing your input function
with fgets.
A nice touch would be to add to the switch statment
a default case, checking if it is a number of math experssion.
Don't ever write code like this :

free(top);
    top=top->next;

Once you free(p), dont access it !!!!!!!!!!
It will probaly work, but its wrong, and
also your grade will be like it.

dude543 2 Light Poster

20 Years Ago

I already told you. Dont do this :

free(top);
    top=top->next;

Its very wrong !!!!!
And still you do it again !!!!
:mad:

First thing better change input by getche to fgets.

Do you think that this is nessary ???
if ( (temp==')') || (temp==']') || (temp=='}') )
{ printf("\n Bad Expression! Run it Again... \n");

add to

case ')': { flag=check(temp[i]);  }
       case ']': { flag=check(temp[i]);  }
       case '}': { flag=check(temp[i]);  }

break statemnts!

If the stack is not empty thats wrong

if ( top )
   {
   printf("Items on the stack\n");
   flag = 0;
   }

You are ignoring the case which pop returns zero.

last thing
'(' - ')' == -1

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

YoTaMiX 0 Light Poster · Answer 1 · 2006-05-27T19:51:39+00:00

The logic should be like this :
   while ( input != 13 )
      {
       if input is '(' or '{' or '[' or ')' or '}' or ']' 
          {
          if input is '(' or '{' or '['
              push it into the stack.
          else if input is  ')' or '}' or ']' 
              {
              if stack is empty
                       report error.
              pop cell from stack
              if cell "matches input" 
                       we are ok.
              else if cell dont "matches input" or stack is empty 
                       report error.
              }
          }
      }
   if  the stack is not empty
        report error.
Also I would suggest replacing your input function
with fgets.
A nice touch would be to add to the switch statment
a default case, checking if it is a number of math experssion.
Don't ever write code like this :
free(top);
    top=top->next;
Once you free(p), dont access it !!!!!!!!!!
It will probaly work, but its wrong, and
also your grade will be like it.

I see your point :-)
i build something , but for some reason , it will state all Expression are OK and i tried to Debug it , and i cant figure what went wrong... Code Added . The check is though ASCII code :
'(' - ')' = 1
'' = 2
'{' - '}' = 2

Thanx

YoTaMiX 0 Light Poster · Answer 2 · 2006-05-27T23:35:14+00:00

I already told you. Dont do this :
free(top);
    top=top->next;
Its very wrong !!!!!
And still you do it again !!!!
:mad:

First thing better change input by getche to fgets.

Do you think that this is nessary ???
if ( (temp==')') || (temp==']') || (temp=='}') )
{ printf("\n Bad Expression! Run it Again... \n");
add to
case ')': { flag=check(temp[i]);  }
       case ']': { flag=check(temp[i]);  }
       case '}': { flag=check(temp[i]);  }
break statemnts!

If the stack is not empty thats wrong
if ( top )
   {
   printf("Items on the stack\n");
   flag = 0;
   }
You are ignoring the case which pop returns zero.

last thing
'(' - ')' == -1

A few things :
1. how do you Take off the Top each time if not in that way?
2. Added Break Statements , still causes problems in Expression check ,
each EXP check gets OK ....
3. the If sentence - no Math Exp. starts with backwoards brackets. :-)
4. should i pass into the POP function a Pointer to FLAG ?

Thanx

hijab_89 -3 Newbie Poster · Answer 3 · 2009-11-29T01:13:32+00:00

The proramme was good..n i think output will be perfect..but i am in 3rd semester...it is a little bitdifficult for me to understand..is there any simpler code for this bracket checker.....?????

Hello to you all ,
I am required to write a program which gets a Math Expression (without checking it is good) and put in Stack only the Brackets .
Implementation of Stack is One-Way Linked List Only.
Examples for Good/Bad Expressions :
(a*{b+c}-4/x +[e-5]) - GOOD
(5+} - BAD
(5+{6*)-2} - BAD
(5+z - BAD
I have build up a Mechanism which checks for each entered char (other than Enter Key and also using closing brackets such as ) or ] or } at the beginning of Expression) what type of bracket it is and pushes it into a stack (we must use LIFO technique for check legal Expression).
I thought of 2 cases :
first case : for each open bracket there is a closing one so i check top of stack to bottom of stack and carry on till i reach to middle .
second case : what happens if i have this sequence - ()[]{} - meaning i need to check top against the next , and so on (top of stack to bottom of stack will not help in this case)
I kinda stuck on Algorithm Think Phase :-)
Code Added . Any Ideas ?
Thank you , Yotam , Israel

Berkut -3 Newbie Poster · Answer 4 · 2009-12-14T21:22:57+00:00

write a c++ program that reads from the user a mathematical expression like:
(3+(4-9) * (3/4) * (3+2))

1. your program should check if the expression is correct
1.1 An expression is correct if:
the parantheses are correctly added and are balanced
examples of not correct expressions can be:
)9+8(
(((8-1)

etc

Assume that the numbers are only one digit ( you can extend your program to read more than one digit numbers as a bonus)

2. If the expression is correct, your program should evaluate the expression and display the result.

hint ( use stacks ( certain types of linked lists ) to solve the problem.

givemetehcodez, lazy - thursday huh? you're screwed unless you start now

HW Assignment - Checking Brackets using Stack

Dani AI

Recommended Answers Collapse Answers

All 6 Replies

Recommended Answers