For this project, design and implement Java code that will check a source code f
ID: 3666418 • Letter: F
Question
For this project, design and implement Java code that will check a source code for balanced parenthesis. You are to implement a dynamically allocated stack that will push and pop objects representing parenthesis as they are encountered in a source code. Since this part of the parser only cares about five different pairs of tokens, you can disregard any other tokens that you encounter along the way.
Do not over think this assignment. There is a little bit of business logic, parsing and a stack. Also, do not ask me if you can use a tokenizer for this assignment, since it will not help you – so no, since “while(“ is a valid syntax and so is “while (“. In other words you don’t have a character to tokenize on, instead read in one character of a line at a time.
These are the syntax specifications for the programming language that you are to check the parenthesisbalanceness for.
1. ( ) - cannot contain 2,4,5 inside but can contain 3.( This means the () can't have {}, /* */, and // in the () ) This type of parenthesis is like a function call or any argument list type of semantic of the code.
2. { } - These parenthesis delineate a block of code. Any number of nested parenthesis 1-5 can be encountered in this block.
3. [ ] - cannot contain 2, 4, 5 ( the [] brackets cant have (), /* */, and // in them) . These parenthesis are used to dereference an array element.
4. /* */ A comment construct must be a matching parenthesis pair that can contain any number of parenthesis 1-3, 5 which can be mismatched.
5. // A single line comment, do not have to have right matching but is terminated by a newline character.
Make sure that you implement and check for parenthesis nesting.
If your implementation encounters a mismatched parenthesis, then you should print out the source line of the parent construct that was not matched (whenever possible – if this cannot be determined, print the same line as when the error was encountered).
For example (of course your program must parse any source code with the above described specifications, not only the following example):
1 function foo (
2 array1 [],
3 array 2 [(),()],
4 asteroid ()
5 /* this function is for foo processing */
Error: unmatched parenthesis '(' from line 1
Hints:
a tricky part for the example above would be if the 5 line would be “5 /* this function ) is for fooprocessing */ “ you would still get the same error message.
push objects on the stack, where each object contains not only the type of the parenthesis, but also a line number. This way it is easy to detect which line has the matching construct.
The easiest way to parse the source code file might be using a String reader and then walk the buffer you read in with a “for” loop.
Your program will read input from a command line (standard input). That being said, I you are required to build a test suite of sample source code programs AND TURN IT IN to show how you went about testing your code.
Explanation / Answer
Design and implement Java code that will check a source code for balanced parenthesis.
Given an expression string exp, write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp. For example, the program should print true for exp = “[()]{}{[()()]()}” and false for exp = “[(])”
Algorithm:
1) Declare a character stack S.
2) Now traverse the expression string exp.
a) If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
b) If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
3) After complete traversal, if there is some starting bracket left in stack then “not balanced”
Implementation:
#include<stdio.h>
#include<stdlib.h>
#define bool int
/* structure of a stack node */
struct sNode
{
char data;
struct sNode *next;
};
/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data);
/* Function to pop an item from stack*/
int pop(struct sNode** top_ref);
/* Returns 1 if character1 and character2 are matching left
and right Parenthesis */
bool isMatchingPair(char character1, char character2)
{
if (character1 == '(' && character2 == ')')
return 1;
else if (character1 == '{' && character2 == '}')
return 1;
else if (character1 == '[' && character2 == ']')
return 1;
else
return 0;
}
/*Return 1 if expression has balanced Parenthesis */
bool areParenthesisBalanced(char exp[])
{
int i = 0;
/* Declare an empty character stack */
struct sNode *stack = NULL;
/* Traverse the given expression to check matching parenthesis */
while (exp[i])
{
/*If the exp[i] is a starting parenthesis then push it*/
if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
push(&stack, exp[i]);
/* If exp[i] is a ending parenthesis then pop from stack and
check if the popped parenthesis is a matching pair*/
if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']')
{
/*If we see an ending parenthesis without a pair then return false*/
if (stack == NULL)
return 0;
/* Pop the top element from stack, if it is not a pair
parenthesis of character then there is a mismatch.
This happens for expressions like {(}) */
else if ( !isMatchingPair(pop(&stack), exp[i]) )
return 0;
}
i++;
}
/* If there is something left in expression then there is a starting
parenthesis without a closing parenthesis */
if (stack == NULL)
return 1; /*balanced*/
else
return 0; /*not balanced*/
}
/* UTILITY FUNCTIONS */
/*driver program to test above functions*/
int main()
{
char exp[100] = "{()}[]";
if (areParenthesisBalanced(exp))
printf(" Balanced ");
else
printf(" Not Balanced ");
return 0;
}
/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data)
{
/* allocate node */
struct sNode* new_node =
(struct sNode*) malloc(sizeof(struct sNode));
if (new_node == NULL)
{
printf("Stack overflow ");
getchar();
exit(0);
}
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*top_ref);
/* move the head to point to the new node */
(*top_ref) = new_node;
}
/* Function to pop an item from stack*/
int pop(struct sNode** top_ref)
{
char res;
struct sNode *top;
/*If stack is empty then error */
if (*top_ref == NULL)
{
printf("Stack overflow ");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->data;
*top_ref = top->next;
free(top);
return res;
}
}
Time Complexity: O(n)
Auxiliary Space: O(n) for stack.
#include<stdio.h>
#include<stdlib.h>
#define bool int
/* structure of a stack node */
struct sNode
{
char data;
struct sNode *next;
};
/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data);
/* Function to pop an item from stack*/
int pop(struct sNode** top_ref);
/* Returns 1 if character1 and character2 are matching left
and right Parenthesis */
bool isMatchingPair(char character1, char character2)
{
if (character1 == '(' && character2 == ')')
return 1;
else if (character1 == '{' && character2 == '}')
return 1;
else if (character1 == '[' && character2 == ']')
return 1;
else
return 0;
}
/*Return 1 if expression has balanced Parenthesis */
bool areParenthesisBalanced(char exp[])
{
int i = 0;
/* Declare an empty character stack */
struct sNode *stack = NULL;
/* Traverse the given expression to check matching parenthesis */
while (exp[i])
{
/*If the exp[i] is a starting parenthesis then push it*/
if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
push(&stack, exp[i]);
/* If exp[i] is a ending parenthesis then pop from stack and
check if the popped parenthesis is a matching pair*/
if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']')
{
/*If we see an ending parenthesis without a pair then return false*/
if (stack == NULL)
return 0;
/* Pop the top element from stack, if it is not a pair
parenthesis of character then there is a mismatch.
This happens for expressions like {(}) */
else if ( !isMatchingPair(pop(&stack), exp[i]) )
return 0;
}
i++;
}
/* If there is something left in expression then there is a starting
parenthesis without a closing parenthesis */
if (stack == NULL)
return 1; /*balanced*/
else
return 0; /*not balanced*/
}
/* UTILITY FUNCTIONS */
/*driver program to test above functions*/
int main()
{
char exp[100] = "{()}[]";
if (areParenthesisBalanced(exp))
printf(" Balanced ");
else
printf(" Not Balanced ");
return 0;
}
/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data)
{
/* allocate node */
struct sNode* new_node =
(struct sNode*) malloc(sizeof(struct sNode));
if (new_node == NULL)
{
printf("Stack overflow ");
getchar();
exit(0);
}
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*top_ref);
/* move the head to point to the new node */
(*top_ref) = new_node;
}
/* Function to pop an item from stack*/
int pop(struct sNode** top_ref)
{
char res;
struct sNode *top;
/*If stack is empty then error */
if (*top_ref == NULL)
{
printf("Stack overflow ");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->data;
*top_ref = top->next;
free(top);
return res;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.