Standish Chapter 7 (C/Unix)

**cchallenged** · 09-09-2006

Hello,

I am trying to run the example program in the C Programs from Chapter 7 of "Data Structures, Algorithms and Software Principles in C" by Thomas A. Standish.

Is this the correct syntax to run the following four files: StackInterface.h, PostfixString.c, StackTypes.h and StackImplementation.c

gcc -o PostfixString.c StackImplementation.c -lm ? If not, please advise.

Please note: I am using "typedef float" for StackTypes.h

| /* ------------< begin file "StackInterface.h" >------------ */
|
| #include "StackTypes.h" /* imports the data type definitions of */
| /* ItemType and Stack */
5 |
| /* defined operations */
|
| extern void InitializeStack(Stack *S);
| /* Initialize the stack S to be the empty stack */
10 |
| extern int Empty(Stack *S);
| /* Returns TRUE == 1 if and only if the stack S is empty */
|
| extern int Full(Stack *S);
15 | /* Returns TRUE == 1 if and only if the stack S is full */
|
| extern void Push(ItemType X, Stack *S);
| /* If S is not full, push a new item X onto the top of S */
|
20 | extern void Pop(Stack *S, ItemType *X);
| /* If S is non-empty, pop an item off the top of S and put it in X */
|
| /* ------------< end-of-file "StackInterface.h" >------------ */

Program 7.3 Stack ADT Interface "StackInterface.h"

/************************************************** *******************************/

| #include <stdio.h>
| #include <stdlib.h> /* contains the conversion function atof */
| #include <math.h> /* contains the exp and log functions */
| #include <ctype.h> /* contains the function, isdigit(d) */
5 | #include <string.h>
| #include "StackInterface.h" /* Here, assume float is the ItemType */
|
| Stack EvalStack; /* let EvalStack be a stack */
| char *PostfixString; /* the input string to evaluate */
10 |
| void InterpretPostfix(void)
| {
| float LeftOperand, RightOperand, Result;
| int i; /* the index of the ith character in the PostfixString */
15 | char c; /* c = the ith character of the input string */
| char *s = "x"; /* s is a string used to convert c to a float */
|
| InitializeStack(&EvalStack); /* let EvalStack be empty initially */
|
20 | for (i = 0; i < strlen(PostfixString); ++i) {
|
| s[0] = c = PostfixString[i]; /*set both s[0] and c to the ith character*/
| /* of the input string */
| if (isdigit(c)) { /* if c is a digit character, then push c's floating*/
25 | /* point value onto the stack, where s must be a */
| Push((float)atof(s),&EvalStack); /* null-terminated string for atof */
|
| } else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^') {
|
30 | Pop(&EvalStack, &RightOperand); /* but if c is an operator */
| Pop(&EvalStack, &LeftOperand ); /* then perform the operation */
|
| switch (c) {
| case '+' : Push(LeftOperand + RightOperand, &EvalStack);
35 | break;
| case '-' : Push(LeftOperand - RightOperand, &EvalStack);
| break;
| case '*' : Push(LeftOperand * RightOperand, &EvalStack);
| break;
40 | case '/ : Push(LeftOperand / RightOperand, &EvalStack);
| break;
| case '^' : Push(exp(log(LeftOperand)*RightOperand), &EvalStack);
| break;
| default : break;
45 | }
| }
| }
|
| Pop(&EvalStack,&Result); /* remove final result from stack */
50 | printf("Value of postfix expression = %f\n", Result); /* and print it */
|
| }

Program 7.7 Interpreting a Postfix String

| /* ------------< begin file "StackTypes.h" >------------ */
|
| #define MAXSTACKSIZE 100
|
5 | typedef arbitrary ItemType; /* the type "arbitrary" is */
| /* defined as "char" for Program 7.5 */
| typedef struct { /* and "float" for Program 7.7 */
| int Count;
| ItemType Items[MAXSTACKSIZE];
10 | }Stack;
|
| /* ------------< end-of-file "StackTypes.h" >------------ */
| /* --------------< begin file "StackImplementation.c" >-------------- */
|
15 | #include <stdio.h>
| #include <stdlib.h> /* the file "StackInterface.h" comes */
| #include "StackInterface.h" /* from Program 7.3 which includes */
| /* "StackTypes.h" on lines 1:12 above */
| /* -------------------- */
20 |
| void InitializeStack(Stack *S); /* S->Count gives */
| { /* the number of items in S */
| S->Count = 0; /* An empty stack S has 0 items in it */
| }
25 |
| /* -------------------- */
|
| int Empty(Stack *S);
| {
30 | return ( S->Count == 0 );
| }
|
| /* -------------------- */
|
35 | int Full(Stack *S);
| {
| return ( S->Count == MAXSTACKSIZE );
| }
|
40 | /* -------------------- */
|
| void Pop(Stack *S, ItemType *X);
| {
| if ( S->Count == 0 ) {
45 | SystemError("attempt to pop the empty stack");
| } else {
| --(S->Count) ;
| *X = S->Items[S->Count];
| }
50 | }
|
| /* -------------------- */
|
| void Push(ItemType X, Stack *S);
55 | {
| if ( S->Count == MAXSTACKSIZE ) {
| SystemError("attempt to push new item onto a full stack");
| } else {
| S->Items[S->Count] = X;
60 | ++(S->Count);
| }
| }
|
| /* ---------------< end-of-file "StackImplementation.c" >-------------- */

Program 7.8 Sequential Stack Implementation

**Salem** · 09-09-2006

> gcc -o PostfixString.c StackImplementation.c -lm ? If not, please advise.
No, it will most likely remove your first source file and replace it with the compiled result of the second file (not good).

Either drop the -o and accept that output files are called a.out or always remember to supply a filename (or have a good backup procedure).

> 15 | /* Returns TRUE == 1 if and only if the stack S is full */
1. Please don't use some tool to prefix each line with a | and a line number.
If you want to refer to a line, put in a comment like /* this is line 15 */
2. Always use [code][/code] tags when posting code.

**cchallenged** · 09-09-2006

Why do I get the following errors when I attempt to run it? I do not see any errors before/after line 6 or the other lines it references...

% gcc StackImplementation.c
StackImplementation.c:6: error: syntax error before '{' token
StackImplementation.c:11: error: syntax error before '{' token
StackImplementation.c:16: error: syntax error before '{' token
StackImplementation.c:21: error: syntax error before '{' token
StackImplementation.c:26: error: 'S' undeclared here (not in a function)
StackImplementation.c:26: warning: data definition has no type or storage class
StackImplementation.c:27: error: syntax error before '}' token
StackImplementation.c:31: error: syntax error before '{' token

vi StackImplementation.c

Code:

#include <stdio.h>
#include <stdlib.h>
#include "StackInterface.h"

void InitializeStack(Stack *S);
{
     S->Count = 0;
}

int Empty(Stack *S);
{
     return (S->Count == 0);
}

int Full(Stack *S);
{
     return (S->Count == MAXSTACKSIZE);
}

void Pop(Stack *S, ItemType *X);
{
     if (S->Count == 0) {
         SystemError("attempt to pop the empty stack");
     } else {
        --(S->Count);
        *X = S->Items[S->Count];
     }
}

void Push(ItemType X, Stack *S);
{
     if (S->Count == MAXSTACKSIZE) {
         SystemError("attempt to push item onto a full stack");
     } else {
         S->Items[S->Count] = X;
         ++(S->Count);
     }
}

vi StackInterface.h

Code:

#include "StackTypes.h"

extern void InitializeStack(Stack *S);
extern int Empty(Stack *S);
extern int Full(Stack *S);
extern void Push(ItemType X, Stack *S);
extern void Pop(Stack *S, ItemType *X);

vi StackTypes.h

Code:

#define MAXSTACKSIZE 100

typedef float ItemType;

typedef struct{
    int Count;
    ItemType Items[MAXSTACKSIZE];
} Stack;

vi post.c

Code:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <string.h>
#include "StackInterface.h"

Stack  EvalStack;
char   *PostfixString;

void InterpretPostfix(void)
{
   float LeftOperand, RightOperand, Result;
   int  i;
   char c;
   char *s= "x";

InitializeStack(&EvalStack);

for (i = 0; i < strlen(PostfixString); ++i) {

   s[0] = c = PostfixString[i];

   if (isdigit(c)) {
      Push((float)atof(s),&EvalStack);

   } else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^' ) {

        Pop(&EvalStack, &RightOperand);
        Pop(&EvalStack, &LeftOperand);

        switch (c) {
        case '+' : Push(LeftOperand + RightOperand, &EvalStack);
                     break;
        case '-' : Push(LeftOperand - RightOperand, &EvalStack);
                     break;
        case '*' : Push(LeftOperand * RightOperand, &EvalStack);
                     break;
        case '/' : Push(LeftOperand / RightOperand, &EvalStack);
                     break;
        case '^' : Push(exp(log(LeftOperand) * RightOperand), &EvalStack);
                     break;
        default  : break;
        }
    }
}

Pop(&EvalStack,&Result);
printf("Value of postfix expression = %f\n", Result);

}

**Salem** · 09-10-2006

Code:

void InitializeStack(Stack *S);
{
     S->Count = 0;
}

All your function definitions still have a trailing ; like you just copy/pasted them from the prototypes.

**cchallenged** · 09-10-2006

Ah..Thank you Salem! I removed the semicolons and that resolved those errors but now I get the following error when I run:

% gcc StackImplementation.c
Undefined first referenced
symbol in file
main /COEnet/Local/Gnu/bin/../lib/gcc/sparc-sun-solaris2.10/4.0.2/crt1.o
SystemError /var/tmp//ccwM3pb3.o
ld: fatal: Symbol referencing errors. No output written to a.out
collect2: ld returned 1 exit status

What is this error referring to? My header files?

#include <stdio.h>
#include <stdlib.h>
#include "StackInterface.h"

Please help.

**kermit** · 09-10-2006

First of all, when compiling with gcc, you may as well use the -Wall flag, as it does not cost you much as far as typing, but may give you that little bit of helpful info (such as a line number in the program) while debugging your program.

Code:

gcc -Wall -o StackImplementation StackImplementation.c

-Wall combines a lot of the separate warnings into one switch, but it does not really get all warnings. For full description, consult the gcc man page.

Now as to your problem..

The compiler is telling you that you are trying to use a function which has not yet been defined. In your case, that function call is this:

Code:

void Pop(Stack *S, ItemType *X)
{
     if (S->Count == 0) {
         SystemError("attempt to pop the empty stack");
     } else {
        --(S->Count);
        *X = S->Items[S->Count];
     }
}

Obviously, if you call a function which has no definition there will be problems.

**cchallenged** · 09-10-2006

I replaced the SystemError function with a printf statement and reran the code. Now I get the following when I run the code:

% gcc -Wall -o StackImplementation StackImplementation.c
Undefined first referenced
symbol in file
main /COEnet/Local/Gnu/bin/../lib/gcc/sparc-sun-solaris2.10/4.0.2/crt1.o
ld: fatal: Symbol referencing errors. No output written to StackImplementation
collect2: ld returned 1 exit status

**Salem** · 09-10-2006

> gcc -o PostfixString.c StackImplementation.c -lm ? If not, please advise.
But you started with two source files, and now you only have one source file?

Maybe drop the -o and accept that your files will be called a.out from now on, and go with
gcc -Wall PostfixString.c StackImplementation.c -lm

Or use it like so
gcc -Wall -o myProgram PostfixString.c StackImplementation.c -lm

**cchallenged** · 09-10-2006

This is the output of this command.

% gcc -Wall PostfixString.c StackImplementation.c -lm
Undefined first referenced
symbol in file
main /COEnet/Local/Gnu/bin/../lib/gcc/sparc-sun-solaris2.10/4.0.2/crt1.o
ld: fatal: Symbol referencing errors. No output written to a.out
collect2: ld returned 1 exit status

I had renamed PostfixString.c to post.c o shorten my typing, but have changed it back to PostfixString.c to be consistent with the start of my problem.

Here is the code that was modified thus far:

vi PostfixString.c

Code:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <string.h>
#include "StackInterface.h"

Stack  EvalStack;
char   *PostfixString;

void InterpretPostfix(void)
{
   float LeftOperand, RightOperand, Result;
   int  i;
   char c;
   char *s= "x";

InitializeStack(&EvalStack);

for (i = 0; i < strlen(PostfixString); ++i) {

   s[0] = c = PostfixString[i];

   if (isdigit(c)) {
      Push((float)atof(s),&EvalStack);

   } else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^' ) {

        Pop(&EvalStack, &RightOperand);
        Pop(&EvalStack, &LeftOperand);

        switch (c) {
        case '+' : Push(LeftOperand + RightOperand, &EvalStack);
                     break;
        case '-' : Push(LeftOperand - RightOperand, &EvalStack);
                     break;
        case '*' : Push(LeftOperand * RightOperand, &EvalStack);
                     break;
        case '/' : Push(LeftOperand / RightOperand, &EvalStack);
                     break;
        case '^' : Push(exp(log(LeftOperand) * RightOperand), &EvalStack);
                     break;
        default  : break;
        }
    }
}

Pop(&EvalStack,&Result);
printf("Value of postfix expression = %f\n", Result);

}

vi StackImplementation.c

Code:

#include <stdio.h>
#include <stdlib.h>
#include "StackInterface.h"

void InitializeStack(Stack *S)
{
     S->Count = 0;
}

int Empty(Stack *S)
{
     return (S->Count == 0);
}

int Full(Stack *S)
{
     return (S->Count == MAXSTACKSIZE);
}

void Pop(Stack *S, ItemType *X)
{
     if (S->Count == 0) {
         printf("Stack empty, cannot delete.\n");
         exit(0);
     } else {
        --(S->Count);
        *X = S->Items[S->Count];
     }
}

void Push(ItemType X, Stack *S)
{
     if (S->Count == MAXSTACKSIZE) {
         printf("Stack full. Aborting...\n");
         return;
     } else {
         S->Items[S->Count] = X;
         ++(S->Count);
     }
}

**cchallenged** · 09-10-2006

Also, when I run the command below, it displays the following as well:

% gcc -Wall -o myProgram PostfixString.c StackImplementation.c -lm
Undefined first referenced
symbol in file
main /COEnet/Local/Gnu/bin/../lib/gcc/sparc-sun-solaris2.10/4.0.2/crt1.o
ld: fatal: Symbol referencing errors. No output written to myProgram
collect2: ld returned 1 exit status

**Salem** · 09-10-2006

OK, so which module has main() in it?

Every program needs a main() to get the whole thing going.

Given the very bad interface of your code, it would be say

Code:

int main ( void ) {
  PostfixString = "2 + 3 * 4";
  InterpretPostfix();
  return 0;
}

Save this in main.c, then compile
gcc -Wall -o myProgram PostfixString.c StackImplementation.c main.c -lm

**cchallenged** · 09-10-2006

I added the "int main(void) in PostfixString.c as so:

Code:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <string.h>
#include "StackInterface.h"


Stack  EvalStack;
char   *PostfixString;

void InterpretPostfix(void);

int main(void)
{
   PostfixString = "2 + 3 * 4";
   InterpretPostfix();
   return 0;
}

void InterpretPostfix(void)
{
   float LeftOperand, RightOperand, Result;
   int  i;
   char c;
   char *s= "x";

InitializeStack(&EvalStack);

for (i = 0; i < strlen(PostfixString); ++i) {

   s[0] = c = PostfixString[i];

   if (isdigit(c)) {
      Push((float)atof(s),&EvalStack);

   } else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^' ) {

        Pop(&EvalStack, &RightOperand);
        Pop(&EvalStack, &LeftOperand);

        switch (c) {
        case '+' : Push(LeftOperand + RightOperand, &EvalStack);
                     break;
        case '-' : Push(LeftOperand - RightOperand, &EvalStack);
                     break;
        case '*' : Push(LeftOperand * RightOperand, &EvalStack);
                     break;
        case '/' : Push(LeftOperand / RightOperand, &EvalStack);
                     break;
        case '^' : Push(exp(log(LeftOperand) * RightOperand), &EvalStack);
                     break;
        default  : break;
        }
    }
}

Pop(&EvalStack,&Result);
printf("Value of postfix expression = %f\n", Result);

}

Then I ran:

% gcc -Wall -o myProgram PostfixString.c StackImplementation.c -lm
% ls
PostfixString.c StackInterface.h
StackImplementation.c StackTypes.h myProgram

% ./myProgram
Segmentation Fault (core dumped)
%

How do I determine why I received the segmentation fault?

**dwks** · 09-10-2006

You can debug it. You could put millions of printf() statements in to determine where it crashed, or you could use gdb.

Code:

$ gdb core  # where core is the name of the core file
// ... debugging the instance of the program that segfaulted ...
$ gdb myProgram
// ... debugging from the start ...
$

[edit] Calling strlen in a loop is quite expensive:

Code:

for (i = 0; i < strlen(PostfixString); ++i) {

You might want to save the result of strlen.

Code:

size_t PosfixStringLen;
// ...
PostfixStringLen = strlen(PostfixString);
for (i = 0; i < PostfixStringLen; ++i) {

strlen returns a size_t, by the way. Your compiler will emit warnings if you let it about signed/unsigned comparisons, because int is signed and size_t is unsigned. Make i size_t or cast the result of strlen() to int (ugh). [/edit]

**dwks** · 09-10-2006

Code:

   } else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^' ) {

        Pop(&EvalStack, &RightOperand);
        Pop(&EvalStack, &LeftOperand);

        switch (c) {
        case '+' : Push(LeftOperand + RightOperand, &EvalStack);
                     break;
        case '-' : Push(LeftOperand - RightOperand, &EvalStack);
                     break;
        case '*' : Push(LeftOperand * RightOperand, &EvalStack);
                     break;
        case '/' : Push(LeftOperand / RightOperand, &EvalStack);
                     break;
        case '^' : Push(exp(log(LeftOperand) * RightOperand), &EvalStack);
                     break;
        default  : break;
        }
    }

It seems to me that you're doing unnessesary work here. You could get rid of the if/else, keep the switch and put the if(isdigit()) in the default case.

Code:

void InterpretPostfix(void)
{
   float LeftOperand, RightOperand, Result;
   int  i;
   char c;
   char *s= "x";

InitializeStack(&EvalStack);

for (i = 0; i < strlen(PostfixString); ++i) {

   s[0] = c = PostfixString[i];

   if (isdigit(c)) {
      Push((float)atof(s),&EvalStack);

s exists merely to call atof; why not just use PostfixString[i]-'0'?

Your error handling differs somewhat:

Code:

void Pop(Stack *S, ItemType *X)
{
     if (S->Count == 0) {
         printf("Stack empty, cannot delete.\n");
         exit(0);
     } else {
        --(S->Count);
        *X = S->Items[S->Count];
     }
}

void Push(ItemType X, Stack *S)
{
     if (S->Count == MAXSTACKSIZE) {
         printf("Stack full. Aborting...\n");
         return;
     } else {
         S->Items[S->Count] = X;
         ++(S->Count);
     }
}

For an empty stack, you quit, but for a full stack, you don't. You should probably be consistent.

**Salem** · 09-11-2006

> PostfixString = "2 + 3 * 4";
Perhaps because I mis-read your code and decided it was infix rather than post-fix

Always try to think a bit about what is being said - sometimes it's a clue to the answer and not the answer

PostfixString = "2 3 + 4 *";
This looks more like a post-fix expression

Thread: Standish Chapter 7 (C/Unix)

Thread Tools

Search Thread

Display

Standish Chapter 7 (C/Unix)

Similar Threads

In need of guidance

please help with binary tree, urgent.