CSc 352: Linked Stack Write a C program, in a file linkstack.c to construct a li
ID: 3910913 • Letter: C
Question
CSc 352: Linked Stack
Write a C program, in a file linkstack.c to construct a linked stack according to input, perform push and pop operations, and iterate through the stack, as specified below.
A brief discussion of stacks in the context of this assignment is given here.
Input: A sequence of stack operations to be read in from stdin, each operation begins with an operator "push" or "pop". Push operator is followed by a decimal integer. An operation may or may not be in the same line. If you use scanf to read in operations, this should not matter.
Output: Iterate through the linked stack after performing the input operations and print out the content of nodes in order from stack top to stack bottom. (You can impelment this traversal by repeatedly pop the top element in stack and print it out.) For the content of each node, print it to stdout using the following statement:
printf("%d ", num)
where num is the decimal integer being printed out.
Assumptions:
You can assume that each integer input is smaller than the maximum integer size and larger than the minimum integer size. (In other words, you can store them in an integer variable.)
Implementation Requirement: You are supposed to construct a linked stack for this project. Implementations that rely on dynamically resized array or fixed array will not receive credit.
Error Conditions: It is an error if an operation does not starting with "push" or "pop", or operation starting with "push" does not followed by an integer.
In each case, print an error message to stderr. Use the exit status of your program to indicate whether any errors were encountered during processing.
"pop" operation on empty stack should be ignored without any error message and the program should not exit in this case.
Example: Suppose the input consists of the following lines:
push -34 push 97
push 5
push 27
pop
pop push 23
push -128
push 12
push 6 pop
Then the output should be
12
-128
23
97
-34
This problem is to introduce you to construct linked stack using pointers. You do not need to free the allocated memory.
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
// this is main struct of a node of the linked list
struct LL {
int number;
struct LL *next;
};
// this function allocates memory for a node and returns the
// allcoated node item
struct LL *makeNode(int num) {
struct LL *node = (struct LL *) malloc( sizeof(struct LL) );
node->number = num;
return node;
}
int main() {
char input[10]; // this is the string which is input.
struct LL * stack_head; // the start of the linked list, also serving as stack
bool wasPush = false; // this specifies if the last word was a push.
while(EOF != scanf("%s", input )) {
if( 0 == strcmp(input, "push") ) { // if the word is push, then next item is a number, so keep a flag
wasPush = true; // to track this
} else if( 0 == strcmp( input, "pop" ) ) { // if we have a pop
wasPush = false; // then we need to ensure next one isn;t pushed
if( stack_head != NULL ) { // and this one is removed
stack_head = stack_head->next; // the current head just points to the next item, effectively losing the current node
}
} else {
// probably a number
if( !wasPush ) continue; // and last word was a push
int number = atoi(input); // so convert this to a number
if( stack_head == NULL ) { // if we have an empty linked list then this is the first node
stack_head = makeNode(number);
stack_head->next = NULL;
} else { // this is aolder list and can have a next item in it
struct LL * prev_head = stack_head;
stack_head = makeNode(number);
stack_head->next = prev_head;
}
wasPush = false;
}
}
// we print the items on the stack now by iterating
// from the top to the bottom of the stack
while( stack_head != NULL ) {
printf("%d ", stack_head->number );
stack_head = stack_head->next;
}
return 0;
}