Balanced Symbol Checker

Balanced Symbol Checker



For this lab, write a C program that will determine whether input is given with properly balanced
symbols. We will often use symbols together to specify the beginning and ending of an item, such as
the use of parentheses in a mathematic expression or the use of curly braces in a C, C++ or Java
program. For this program, we will be checking the following symbol pairs:
• parentheses: ( )
• curly braces: { }
• square brackets: [ ]
• angle brackets: < >
This program will require the use of a stack implemented in a dynamic array. This dynamic array is
to grow to a larger size when a push operation would be done to a full array causing an array
overflow. For this program, your dynamic array is to start with 2 positions in the array. When the
array needs to grow, it size is to grow by 2 additional positions each time (note the array to grow in
size from 2 to 4 to 6 to 8 to 10 to ...).
The push operation is now defined as follows:
if (the stack array if full)
grow the array
add the value to the stack array
increment the top-of-stack value
The grow operation is defined as follows:
Allocate a new dynamic array of the larger size
Copy the existing values from the current stack array to the new dynamic array
Deallocate the current stack array
Have the stack array variable refer/point to the new dynamic array
Update the maximum stack size variable Input The input for this program will come from standard input. Each line of input will be a single
expression that is to be checked for balanced symbols. You may assume that each line of input is less
than 300 characters long. Since the only input we really care about are the 8 characters that form the
4 symbol pairs, any other input on the line can be ignored. The only exception is if the input on the
line just contains the letter q. In this case, quit the program.
Stack Use Algorithm
To check for balance symbols in an expression, the expression is read from left to right.
When an opening symbol is encountered, this symbol is pushed onto the stack. The opening symbols
are: ( { [ and <.
When a closing symbol is encountered, check the symbol at the top of the stack.
• If the symbol on the top of the stack is the corresponding opening symbol, pop the stack and
continue.
• If the symbol on the top of the stack is NOT the corresponding opening symbol, the expression
is NOT balanced and the wrong closing symbol was encountered.
• If the stack is empty, the expression is NOT balanced and there is a missing opening symbol.
When the end of the expression is encountered (i.e. the end of the input line), check to see if the stack
is empty.
• If the stack is empty, then the expression was balanced.
• If the stack is NOT empty, the expression was not balanced and there is a missing closing
symbol.
Output
For each line of input, your program should display the input and specify whether the expression
• is balanced
• is unbalanced because it is expecting a different closing symbol (the wrong closing symbol is
on the top of the stack)
• is unbalanced because it is missing an opening symbol (stack is empty when a closing symbol is
encountered)
• is unbalanced because it is missing a closing symbol (line ends while the stack is not empty)

code example
/*plaimanus Lueondee*/
// credit professor Pat Troy UIC
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX 301
#define QUIT "q"
  

typedef struct
{
  char *stkk;
  int stackSize;
  int top;
} stack;
typedef stack * stack_ptr;

    void stack_push (stack * s, char c);
    char stack_pop (stack * s);
    int stack_is_empty (stack * s);
   stack *stack_create (int n);
    void stack_delete (stack *stk);
    int check_balance (char *exp, int *error_at);
   int debug= FALSE;
    int check_balance (char *exp, int *error_at){
char paranthesis = '\0';
char temp;
int error = FALSE;
int i =0;
stack *stk;
stk = stack_create (MAX);
while (exp[i] != '\0')
{
paranthesis = exp[i];
if (paranthesis == '(' || paranthesis == '{' || paranthesis == '[' || paranthesis == '<')
stack_push (stk, paranthesis);
else if (paranthesis == ')' || paranthesis == '}' || paranthesis == ']'||  paranthesis == '>')
{
if (stack_is_empty (stk))
{
error = TRUE;
break;
}
temp = stack_pop (stk);
if (!((temp == '(' && paranthesis == ')') || (temp == '{' && paranthesis == '}')
||(temp == '[' && paranthesis == ']')||(temp == '<' && paranthesis == '>')))
{
error = TRUE;
break;
}
}
i++;
}
if (!stack_is_empty (stk))
error = TRUE;
if ((error == TRUE) && (error_at != NULL))
*error_at = i + 1;
stack_delete (stk);
return error;
}
void stack_push (stack_ptr stk, char paranthesis)
{
if (stk->top >= MAX)
{
//double stack size
printf ("\nStack FULL creating new stack");
char *temp = (char *)malloc( sizeof(char) * (stk->stackSize + 2) );
free(stk->stkk);
stk->stkk = temp;
stk->stkk += 2;
}
stk->stkk[++(stk->top)] = paranthesis;
}
char stack_pop (stack * stk)
{
if (stk->top <= -1)
return '\0';
return stk->stkk[(stk->top)--];
}
int stack_is_empty (stack * stk)
{
if (stk->top <= -1)
return TRUE;
return FALSE;
}
stack *stack_create (int n)
{
stack *temp;
temp = malloc (sizeof (stack)+2);
if (temp == NULL)
{
printf ("Terminating\n");
exit (1);
}
temp->stkk = malloc (sizeof (char) * n+2);
if (temp->stkk == NULL)
{
printf("Terminating\n");
exit (1);
}
temp->top = -1;
return temp;
}
void stack_delete (stack *stk)
{
if (stk != NULL)
{
if (stk->stkk)
free (stk->stkk);
free (stk);
}
}
main (int argc,char *argv[])
{
char exp[MAX];
int  retval;
int  error_at;
debug = FALSE;
if( argc > 2 ) {
printf("Please use: %s[-d]\n", argv[0]);
exit(0);
}
if( argc == 2 && argv[1][0] == '-' && argv[1][1] == 'd' ) {
printf("\nDebuging information\n");
debug = TRUE;
}
while( TRUE ) {
printf("Enter your expression or type 'q' to leave: ");
fgets(exp, MAX, stdin);
if(exp[0]=='q') {
exit(0);
}
retval = check_balance (exp, &error_at);
if(retval == FALSE){
printf ("\n%s\n",exp);
printf ("\nExpression are balance:\n");
}
else {
int i;
printf ("\nExpression is not balance:\n");
printf ("\n%s\n",exp);
printf("missing it's pair at %d\n",error_at);
}
}
return 0;
}