By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
432,009 Members | 1,643 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,009 IT Pros & Developers. It's quick & easy.

implement a stack using a standard linked list in the C programming

P: 5
You are provided with a sample C programs: calc.c, which implements a reverse polish notation
calculator. Study it carefully. This program uses a stack (of course!) but the stack implementation
is missing and you have to add it. You are to use the linked list structure defined within the
program, to implement a stack. In short, you need to implement the functions pop() and push()
using a linked list.
You are provided with calc-array.c which is a full implementation of the calculator, and uses an
array to implement the stack. Compile and run this program and test it (for instance enter 4 5 3 +
* <ENTER> as standard input and see that you get 32 as the answer). You should use the output
of this program to check that your own implementation is doing the right thing.
#include <stdio.h>
#include <stdlib.h> /* for atof() */

#define MAXOP 100 /* max size of operand or operator */
#define NUMBER '0' /* signal that a number was found */

/* useful prototypes. */
int getop(char []);

void push(double);
double pop(void);

/* reverse Polish calculator */

int main(void)
{
int type;
double op2;
char s[MAXOP];

while((type = getop(s)) != EOF)
{
switch(type)
{
case NUMBER:
push(atof(s));
break;
case '+':
push(pop() + pop());
break;
case '*':
push(pop() * pop());
break;
case '-':
op2 = pop();
push(pop() - op2);
break;
case '/':
op2 = pop();
if(op2 != 0.0)
push(pop() / op2);
else
printf("error: zero divisor\n");
break;
case '\n':
printf("\t%.8g\n", pop());
break;
default:
printf("error: unknown command %s\n", s);
break;
}
}

return 0;
}

#include <ctype.h>

int getch(void);
void ungetch(int);

/* getop: get next operator or numeric operand */
int getop(char s[])
{
int i, c;

while((s[0] = c = getch()) == ' ' || c == '\t')
;

s[1] = '\0';
if(!isdigit(c) && c != '.')
return c; /* not a number */
i = 0;
if(isdigit(c)) /* collect integer part */
while(isdigit(s[++i] = c = getch()))
;
if(c == '.')
while(isdigit(s[++i] = c = getch()))
;
s[i] = '\0';
if(c != EOF)
ungetch(c);
return NUMBER;
}

#define BUFSIZE 100

char buf[BUFSIZE]; /* buffer for ungetch */
int bufp = 0; /* next free position in buf */

int getch(void) /* get a (possibly pushed back) character */
{
return (bufp > 0) ? buf[--bufp] : getchar();
}

void ungetch(int c) /* push character back on input */
{
if(bufp >= BUFSIZE)
printf("ungetch: too many characters\n");
else
buf[bufp++] = c;
}


typedef struct list_t {
double item;
struct list_t *next;
} list_t;


list_t *st = NULL; /* To be used as our stack. Starts out as empty (NULL). */

/* push: push f onto value stack */
void push(double f)
{

/* Your code goes here. */
}

/* pop: pop and return top value from stack */
double pop(void)
{
/* Your code goes here. */
}
Sep 27 '06 #1
Share this Question
Share on Google+
2 Replies


Banfa
Expert Mod 5K+
P: 8,916
Expand|Select|Wrap|Line Numbers
  1. typedef struct list_t {
  2.     double item;
  3.     struct list_t *next;
  4. } list_t;
  5.  
  6.  
  7. list_t *st = NULL; /* To be used as our stack. Starts out as empty (NULL). */
  8.  
  9. /* push: push f onto value stack */
  10. void push(double f)
  11. {
  12.     /* Your code goes here. */
  13. }
  14.  
  15. /* pop: pop and return top value from stack */
  16. double pop(void)
  17. {
  18.     /* Your code goes here. */
  19. }
  20.  
Once you have had an attempt at writing these functions we will help you debug them.

Do you understand how a linked list works in concept?
Sep 28 '06 #2

P: 5
thanks but finally l got to learn about stacks and linked lists
Sep 28 '06 #3

Post your reply

Sign in to post your reply or Sign up for a free account.