Was trying to get all the test cases to pass but I keep getting either very few or a lot of test cases wrong depending on the test case. I have a feeling like I am missing something major but after countless hours I still have no idea what I am missing.
Test case: 12 is the number of strings followed by the strings Empty line is the first string to be tested.
12
([])
(([()])))
([()[]()])()
(([()])
([])
(([()])))
([()[]()])()
(
(]
)(
][
Expected output:
Yes
Yes
No
Yes
No
Yes
No
Yes
No
No
No
No
My output:
Yes
Yes
No
Yes
Yes // should be no
Yes
No
Yes
Yes // should be no
No
No
No
Failed cases:
([])
(
main.c
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
void ClearKeyboardBuffer(void) {
char c;
int noc;
noc = scanf("%c", &c);
while (noc == 1 && c != '\n') {
scanf("%c", &c);
}
}
Boolean isMatch(void) {
STACK hStack;
int noc;
char c;
Boolean m = TRUE;
hStack = StackInitDefault();
if (hStack == NULL) {
printf("Failed to allocate space for stack object.\n");
exit(2);
}
noc = scanf("%c", &c);
while (noc == 1 && c != '\n') {
if (StackIsEmpty(hStack)) {
if (c == '(' || c == '[' || c == '{') {
StackPush(hStack, c);
} else if (c == ')' || c == ']' || c == '}') {
m = FALSE;
}
} else if (!StackIsEmpty(hStack)) {
if (c == '(' || c == '[' || c == '{') {
StackPush(hStack, c);
} else if (c == ')' || c == ']' || c == '}') {
if (c == ')' && StackTop(hStack, NULL) == '(') {
StackPop(hStack);
} else if (c == ']' && StackTop(hStack, NULL) == '[') {
StackPop(hStack);
} else if (c == '}' && StackTop(hStack, NULL) == '{') {
StackPop(hStack);
} else {
m = FALSE;
}
}
}
noc = scanf("%c", &c);
}
return m;
}
int main(int argc, const char * argv[]) {
STACK hStack;
int n;
hStack = StackInitDefault(); // initialize the object
if (hStack == NULL) {
printf("Failed to allocate space for stack object.\n");
exit(1);
}
scanf("%d", &n); // get number of strings that the user will be inputting
ClearKeyboardBuffer();
while (n--) {
if (isMatch()) {
printf("Yes\n");
} else {
printf("No\n");
}
while (!StackIsEmpty(hStack)) {
StackPop(hStack);
}
}
StackDestroy(&hStack);
return 0;
}
stack.c
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
#include "status.h"
struct node;
typedef struct node Node;
struct node {
char value;
Node* next;
};
struct stack {
Node* head;
};
typedef struct stack Stack;
STACK StackInitDefault(void) {
Stack* pStack = (Stack*)malloc(sizeof(Stack));
if (pStack != NULL) {
pStack->head = NULL;
}
return pStack;
}
Boolean StackIsEmpty(STACK hStack) {
Stack* pStack = (Stack*)hStack;
return (pStack->head == NULL)?TRUE:FALSE;
}
char StackTop(STACK hStack, Status* pStatus) {
Stack* pStack = (Stack*)hStack;
if (StackIsEmpty(hStack)) {
if (pStatus != NULL) {
*pStatus = FAILURE;
}
return 'e';
}
if (pStatus != NULL) {
*pStatus = SUCCESS;
}
return pStack->head->value;
}
Status StackPush(STACK hStack, char c) {
Stack* pStack = (Stack*)hStack;
Node* temp = (Node*)malloc(sizeof(Node));
if (temp == NULL) {
return FAILURE;
}
temp->value = c;
temp->next = pStack->head;
pStack->head = temp;
return SUCCESS;
}
Status StackPop(STACK hStack) {
Stack* pStack = (Stack*)hStack;
Node* temp;
if (StackIsEmpty(hStack)) {
return FAILURE;
}
temp = pStack->head;
pStack->head = pStack->head->next;
free(temp);
return SUCCESS;
}
void StackDestroy(STACK* phStack) {
Stack* pStack = (Stack*)*phStack;
Node* temp = pStack->head;
while (pStack->head != NULL) {
temp = pStack->head;
pStack->head = pStack->head->next;
free(temp);
}
free(pStack);
*phStack = NULL;
}
stack.h
#ifndef stack_h
#define stack_h
#include "status.h"
typedef void* STACK;
STACK StackInitDefault(void);
Status StackPush(STACK hStack, char c);
Status StackPop(STACK hStack);
char StackTop(STACK hStack, Status* pStatus);
void StackDestroy(STACK* phStack);
Boolean StackIsEmpty(STACK hStack);
#endif /* stack_h */
status.h
#ifndef STATUS_H
#define STATUS_H
enum status { FAILURE, SUCCESS };
typedef enum status Status;
enum boolean { FALSE, TRUE };
typedef enum boolean Boolean;
#endif
The comments have largely covered all the issues here, but I will try to summarize.
The primary issue is, in order for an expression to be balanced, the stack should be checked to be empty after the expression has finished being parsed. This is not being done in your code.
A secondary issue is that your expectations for some of the test cases appears wrong (e.g., expecting Yes for (([()])))).
Other issues include:
The STACK hStack; in main and the STACK hStack; in isMatch are not the same object. The object in isMatch is never passed to StackDestroy, whereas the object in main is pointless.
One of the most prevalent issues is that there is quite a bit of repetition in this code. Constructs such as
if (StackIsEmpty(hStack)) {
/* ... */
} else if (!StackIsEmpty(hStack)) {
/* ... */
are overly verbose. The branch condition can be implied by just an else statement.
The entire push & pop section of isMatch spends a lot of time checking unnecessary or redundant conditions. Really, there's only a couple of things to do for every character in the expression
(, [, {), push it to the stack.), ], }), if the stack is empty, or the top of the stack is not the associated opening character, return an invalid result.You are effectively working in terms of lines of input, but have done so by reading one character at a time from standard input. At the very least, one might suggest getchar instead of using scanf("%c", ...), but it would be remiss not to mention the possibility of reading an entire line with fgets, and then processing it as string. As long as your lines aren't extremely long, this is very simple.
Some clearly class/course/instructor/professor-specific critiques, taking into account this comment:
I am honestly not sure. I do agree that a lot of the things seem a bit pointless but the professor is really old school and he wants us to practice treating the stack object as an opaque object. It isn't the way I would make this program personally but it is the way he wants us to do it.
Both of these are basically noise:
enum status { FAILURE, SUCCESS };
typedef enum status Status;
enum boolean { FALSE, TRUE };
typedef enum boolean Boolean;
Both enumerations can easily be represented by the bool type: true and false have been available since C99, through <stdbool.h> (and C23 will make them keywords).
This typedef
typedef void* STACK;
is not great. void * is not required to facilitate an opaque type. An opaque type is essentially just a pointer to an incomplete type (an identifiable type with no definition, i.e., information about its size). For an opaque type, your header could simply contain
typedef struct stack Stack;
Stack *StackInitDefault(void);
with the definition of struct stack in the source file.
Additionally, typedef-ing a pointer is somewhat contentious, but the most common advice is to avoid doing it. On-top of this, the explicit casts of a void * to another pointer type are not required, as a void * can be implicitly converted to any other pointer type.
(If your compiler is complaining, you are probably using a C++ compiler, not a C compiler.)
Again, do whatever you need to do to pass the class, but some of these requirements are not good practices.
Here is an implementation that follows much of the advice laid out above. It avoids typedef-ing all together. StackTop is not present as it is not needed. It simply checks all lines of input (instead of a set number of lines derived from the first line), or it runs present test cases.
Some typical edge-cases: passing a null pointer to any library function, or popping an empty stack are both undefined behaviour, and StackDestroy leaves its argument as a dangling-pointer for the caller to deal with (mimics free).
Example usage:
$ ./a.out tests
"" -> PASS
"([])" -> PASS
"(([()])))" -> PASS
"([()[]()])()" -> PASS
"(([()])" -> PASS
"(([()])" -> PASS
"(([()])))" -> PASS
"([()[]()])()" -> PASS
"(" -> PASS
"(]" -> PASS
")(" -> PASS
"][" -> PASS
$ ./a.out
[]
"[]" true
({[]})
"({[]})" true
int main(int argc, char *argv[]) { puts("Hello world!"); }
"int main(int argc, char *argv[]) { puts("Hello world!"); }" true
)()(((){}{})()
")()(((){}{})()" false
The code:
stack.h:
#ifndef STACK_H
#define STACK_H
#include <stdbool.h>
struct stack;
struct stack *StackInitDefault(void);
bool StackIsEmpty(struct stack *);
bool StackPush(struct stack *, char);
char StackPop(struct stack *);
void StackDestroy(struct stack *);
#endif
stack.c:
#include <stdlib.h>
#include "stack.h"
struct node {
char value;
struct node *prev;
};
struct stack {
struct node *top;
};
struct stack *StackInitDefault(void)
{
return calloc(1, sizeof (struct stack));
}
bool StackIsEmpty(struct stack *s)
{
return !s->top;
}
bool StackPush(struct stack *s, char c)
{
struct node *n = malloc(sizeof *n);
if (!n)
return false;
n->value = c;
n->prev = s->top;
s->top = n;
return true;
}
char StackPop(struct stack *s)
{
struct node *n = s->top;
char value = n->value;
s->top = n->prev;
free(n);
return value;
}
/* slightly inefficient being written in terms of `StackPop`,
* but keeps things simple */
void StackDestroy(struct stack *s)
{
while (!StackIsEmpty(s))
(void) StackPop(s);
free(s);
}
main.c:
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"
#define stringify(b) ((b) ? "true" : "false")
/* running out of memory renders this program useless
* bail out, let the OS clean up */
static void fatal_memory(void)
{
fputs("CRITICAL: Out of memory.\n", stderr);
exit(EXIT_FAILURE);
}
static char invert(char c)
{
switch (c) {
case '(': return ')';
case '[': return ']';
case '{': return '}';
}
return '\0';
}
static bool is_balanced(const char *data)
{
struct stack *st = StackInitDefault();
if (!st)
fatal_memory();
for (char c; (c = *data); data++) {
switch (c) {
case '(':
case '[':
case '{':
if (!StackPush(st, c))
fatal_memory();
break;
case ')':
case ']':
case '}':
if (StackIsEmpty(st) || invert(StackPop(st)) != c) {
StackDestroy(st);
return false;
}
break;
}
}
bool result = StackIsEmpty(st);
StackDestroy(st);
return result;
}
static void do_basic_testcases(void)
{
const struct {
const char *string;
const bool expect;
} tests[] = {
{ "", true },
{ "([])", true },
{ "(([()])))", false },
{ "([()[]()])()", true },
{ "(([()])", false },
{ "(([()])", false },
{ "(([()])))", false },
{ "([()[]()])()", true },
{ "(", false },
{ "(]", false },
{ ")(", false },
{ "][", false }
};
for (size_t i = 0; i < sizeof tests / sizeof *tests; i++) {
bool expect = tests[i].expect;
bool actual = is_balanced(tests[i].string);
printf("\"%s\" -> ", tests[i].string);
if (expect == actual)
puts("PASS");
else
printf("FAIL: `%s` expected, got `%s`\n", stringify(expect), stringify(actual));
}
}
int main(int argc, char **argv)
{
if (argc > 1 && 0 == strcmp("tests", argv[1]))
do_basic_testcases();
else {
char line[4096];
while (fgets(line, sizeof line, stdin)) {
line[strcspn(line, "\n")] = '\0';
printf("\"%s\" %s\n", line, stringify(is_balanced(line)));
}
}
}