472,983 Members | 2,700 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 472,983 software developers and data experts.

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

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
2 19262
Banfa
9,065 Expert Mod 8TB
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
thanks but finally l got to learn about stacks and linked lists
Sep 28 '06 #3

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

Similar topics

66
by: Mike Stenzler | last post by:
I am new to Template programming and I would like to create an array of user-defined class objects using MFC CArray. Normally I would use linked list processing - create an object class and then an...
14
by: Kevin Grigorenko | last post by:
Hello, I couldn't find an obvious answer to this in the FAQ. My basic question, is: Is there any difference in allocating on the heap versus the stack? If heap or stack implementation is not...
25
by: Brian Lindahl | last post by:
I'm using a temporary buffer to transfer some data and would rather not allocate it on the heap. The problem is that the size of the buffer is only known upon entry into the function that utilizes...
13
by: Kenneth Lantrip | last post by:
In Ansi-C C99 or Standard C or in GCC... Is there a way to push a value onto the stack and then later retrieve it within the same function? void foo(void) {
4
by: anonymous | last post by:
Thanks your reply. The article I read is from www.hakin9.org/en/attachments/stackoverflow_en.pdf. And you're right. I don't know it very clearly. And that's why I want to understand it; for it's...
3
by: AMRaymo | last post by:
Can someone guide me in the right direction on how to enqueue and dequeue/pop and push within a linked list? I've figured out the basic idea, but getting the other options in it seems ot be a...
1
by: yaarnick | last post by:
Create a linked list data structure library to hold strings. Then library should support the following linked list operations. Create() Creates the linked list Insert() Insert a string into the...
60
by: harshal | last post by:
Hi all, Can we read the stack frame's of the current process. as we know that whenever a function call is made in c new functions stack frame is created and pushed on to the stack. and when the...
30
by: asit | last post by:
We kno that data can be pushed onto the stack or popped 4m it. Can stack be traversed ??
0
by: lllomh | last post by:
Define the method first this.state = { buttonBackgroundColor: 'green', isBlinking: false, // A new status is added to identify whether the button is blinking or not } autoStart=()=>{
2
by: DJRhino | last post by:
Was curious if anyone else was having this same issue or not.... I was just Up/Down graded to windows 11 and now my access combo boxes are not acting right. With win 10 I could start typing...
0
by: Aliciasmith | last post by:
In an age dominated by smartphones, having a mobile app for your business is no longer an option; it's a necessity. Whether you're a startup or an established enterprise, finding the right mobile app...
0
tracyyun
by: tracyyun | last post by:
Hello everyone, I have a question and would like some advice on network connectivity. I have one computer connected to my router via WiFi, but I have two other computers that I want to be able to...
4
NeoPa
by: NeoPa | last post by:
Hello everyone. I find myself stuck trying to find the VBA way to get Access to create a PDF of the currently-selected (and open) object (Form or Report). I know it can be done by selecting :...
1
by: Teri B | last post by:
Hi, I have created a sub-form Roles. In my course form the user selects the roles assigned to the course. 0ne-to-many. One course many roles. Then I created a report based on the Course form and...
3
by: nia12 | last post by:
Hi there, I am very new to Access so apologies if any of this is obvious/not clear. I am creating a data collection tool for health care employees to complete. It consists of a number of...
0
NeoPa
by: NeoPa | last post by:
Introduction For this article I'll be focusing on the Report (clsReport) class. This simply handles making the calling Form invisible until all of the Reports opened by it have been closed, when it...
0
isladogs
by: isladogs | last post by:
The next online meeting of the Access Europe User Group will be on Wednesday 6 Dec 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, Mike...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.