PostFixDemo.c
Main program used in both array and linked implementation
/**************************************************************/
/* File: PostFixDemo.c */
/* */
/* Demonstration of a postfix calculator using a stack module.*/
/* Author: Rick Coleman, Instructor CS207 */
/* Date: February 1998 */
/**************************************************************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include "StackInterface.h"
void GetExpression(char *);
float EvaluateExpression(char *, Stack *);
int main(void)
{
Stack theStack;
char PostFixString[81];
int done = FALSE;
float Result;
InitializeStack(&theStack);
do
{
GetExpression(PostFixString);
if(strcmp(PostFixString, "done")) /* if()==TRUE when PostFixString != "done" */
{
Result = EvaluateExpression(PostFixString, &theStack);
printf("%s = %f\n\n", PostFixString, Result);
printf("\n\n\nEnter another postfix expression or type \"done\" to exit?\n");
}
else
{
printf("\n\n\nBye, for now.\n");
done = TRUE;
}
}
while(!done);
return(0);
}
/************************************/
/* GetExpression() */
/* */
/* Input a postfix expression to */
/* be evaluated. */
/************************************/
void GetExpression(char *expression)
{
printf("\n\nInput an expression in postfix notation.\n");
printf("Single digit numbers only.");
gets(expression);
}
/************************************/
/* EvaluateExpression() */
/* */
/* Input a postfix expression to */
/* be evaluated. */
/************************************/
float EvaluateExpression(char *expression, Stack *S)
{
int i, sl;
float LOp, ROp, Result;
char s[2] = " "; /* Initialize 2 character array to space character. */
sl = strlen(expression);
for(i=0; i<sl; i++)
{
if(isdigit(expression[i]))
{
s[0] = expression[i]; /* Note: This is a sneaky way to build */
/* a string from a single char */
Push((float)atof(s), S);
}
else
{
Pop(S, &ROp);
Pop(S, &LOp);
switch(expression[i])
{
case '+' : Push(LOp + ROp, S);
break;
case '-' : Push(LOp - ROp, S);
break;
case '*' : Push(LOp * ROp, S);
break;
case '/' : if(ROp != 0)
Push(LOp / ROp, S);
else
printf("\n...Division by zero error...\n");
return(0);
break;
}
}
}
Pop(S, &Result);
return(Result);
}
The code shown above implements a stack as an array. The code below
shows how the same stack, using the same interface file and main()
can be implemented as a linked structure.
StackTypes.h
Linked Implementation
/**************************************************************/
/* File: StackTypes.h */
/* */
/* Data types header file for a demonstration of a stack in */
/* a postfix calculator. The stack is implemented as a */
/* linked list in this example. */
/* Author: Rick Coleman, Instructor CS207 */
/* Date: February 1998 */
/**************************************************************/
#define MAXSTACKSIZE 50
typedef float ItemType;
typedef float ItemType;
typedef struct StackItemtype
{
ItemType item;
struct StackItemtype *next;
} StackItem;
/* Note: put this pointer in a structure so we can change it easily. */
typedef struct Stacktype
{
StackItem *top;
} Stack;
#ifndef FALSE
#define FALSE (0)
#endif
#ifndef TRUE
#define TRUE (!FALSE)
#endif
Stack.c
Linked Implementation
/**************************************************************/
/* File: Stack.c */
/* */
/* Stack package for a demonstration of a stack in a postfix */
/* calculator. */
/* Author: Rick Coleman, Instructor CS207-02, */
/* Date: February 1998 */
/**************************************************************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include "StackTypes.h"
/*************************************/
/* InitializeStack() */
/* */
/* Clear stack. Assume this is a new */
/* stack. */
/*************************************/
void InitializeStack(Stack *S)
{
S->top = NULL;
}
/*************************************/
/* EmptyStack() */
/* */
/* Return TRUE if the stack is empty.*/
/*************************************/
int EmptyStack(Stack *S)
{
if(S->top == NULL) return TRUE;
else return FALSE;
}
/*************************************/
/* FullStack() */
/* */
/* Return TRUE if the stack is full. */
/*************************************/
int FullStack(Stack *S)
{
return FALSE; /* Assume a dynamic list can't fill up */
}
/*************************************/
/* Push() */
/* */
/* Push an item onto the stack if */
/* the stack is not full. */
/*************************************/
void Push(ItemType X, Stack *S)
{
StackItem *temp;
temp = (StackItem *)malloc(sizeof(StackItem));
temp->item = X;
temp->next = S->top;
S->top = temp;
}
/*************************************/
/* Pop() */
/* */
/* Pop an item from the stack if */
/* the stack is not empty. */
/*************************************/
void Pop(Stack *S, ItemType *X)
{
StackItem *temp;
if(!EmptyStack(S))
{
*X = S->top->item;
temp = S->top;
S->top = S->top->next;
free(temp); /* Dispose of the popped structure */
}
}
The code shown below shows how the linked implementation of the same
stack can be modified to create a C++ Stack Class. The two
header files have been combined into a single Class interface definition
header file. All standard I/O using printf(), scanf(), gets(), and
getch() has been replaced with stream I/O using cin (pronounced "cee-in")
and cout (pronounced "cee-out").
Stack.h
C++ Linked Implementation
/*********************************************************/
/* File: Stack.h */
/* */
/* Class header file for a demonstration of a stack */
/* class in a postfix calculator. */
/* Author: Rick Coleman, Instructor CS207, */
/* Date: June 2001 */
/*********************************************************/
#ifndef STACK_H
#define STACK_H
typedef float ItemType;
struct StackItem
{
ItemType item;
StackItem *next;
};
class Stack
{
private:
StackItem *top;
public:
Stack(); // Class constructor
~Stack(); // Class destructor
int EmptyStack();
int FullStack();
void Push(ItemType X);
ItemType Pop();
};
#ifndef FALSE
#define FALSE (0)
#endif
#ifndef TRUE
#define TRUE (!FALSE)
#endif
#endif
Stack.cpp
C++ Linked Implementation
/*********************************************************/
/* File: Stack.cpp */
/* */
/* Stack package for a demonstration of a stack in a */
/* postfix calculator. */
/* Author: Rick Coleman, Instructor CS207, */
/* Date: June 2001 */
/*********************************************************/
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include "Stack.h"
/*************************************/
/* Stack() */
/* */
/* Class constructor. Clear stack. */
/* Assume this is a new stack. */
/*************************************/
Stack::Stack()
{
top = NULL;
}
/*************************************/
/* ~Stack() */
/* */
/* Class destructor. */
/*************************************/
Stack::~Stack()
{
// Destroy anything remaining in stack
}
/*************************************/
/* EmptyStack() */
/* */
/* Return TRUE if the stack is empty.*/
/*************************************/
int Stack::EmptyStack()
{
if(top == NULL) return TRUE;
else return FALSE;
}
/*************************************/
/* FullStack() */
/* */
/* Return TRUE if the stack is full. */
/*************************************/
int Stack::FullStack()
{
return FALSE; /* Assume dynamic list can't fill up */
}
/*************************************/
/* Push() */
/* */
/* Push an item onto the stack if */
/* the stack is not full. */
/*************************************/
void Stack::Push(ItemType X)
{
StackItem *newItem;
newItem = new (StackItem);
newItem->item = X;
newItem->next = top;
top = newItem;
}
/*************************************/
/* Pop() */
/* */
/* Pop an item from the stack if */
/* the stack is not empty. */
/*************************************/
float Stack::Pop()
{
StackItem *temp;
ItemType X = 0;
if(!EmptyStack())
{
X = top->item;
temp = top;
top = top->next;
delete(temp); /* Dispose of popped structure */
}
return(X);
}
PostFixDemo.cpp
C++ Linked Implementation
/*********************************************************/
/* File: PostFixDemo.cpp */
/* */
/* Demonstration of a postfix calculator using a stack */
/* class. */
/* Author: Rick Coleman, Instructor CS207 */
/* Date: June 2001 */
/*********************************************************/
#include <iostream.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include "Stack.h"
void GetExpression(char *);
float EvaluateExpression(char *, Stack *);
int main(void)
{
Stack *theStack;
char PostFixString[81];
int done = FALSE;
float Result;
theStack = new (Stack);
do
{
GetExpression(PostFixString);
if(strcmp(PostFixString, "done"))
{
Result = EvaluateExpression(PostFixString, theStack);
cout << PostFixString << " = " << Result << "\n\n";
cout << "\n\n" << "Enter another postfix expression"
<< "or type \"done\" to exit?\n";
}
else
{
cout << "\n\n\nBye, for now.\n";
done = TRUE;
}
}
while(!done);
return(0);
}
/************************************/
/* GetExpression() */
/* */
/* Input a postfix expression to */
/* be evaluated. */
/************************************/
void GetExpression(char *expression)
{
cout << "\n\nInput an expression in postfix notation.\n";
cout << "Single digit numbers only: ";
cin >> expression;
}
/************************************/
/* EvaluateExpression() */
/* */
/* Input a postfix expression to */
/* be evaluated. */
/************************************/
float EvaluateExpression(char *expression, Stack *S)
{
int i, sl;
float LOp, ROp, Result;
char s[2] = " "; /* Init 2 char array to a space*/
sl = strlen(expression);
for(i=0; i<sl; i++)
{
if(isdigit(expression[i]))
{
/* Note: This is a sneaky way to built */
/* a string from a single char */
s[0] = expression[i];
S->Push((float)atof(s));
}
else
{
ROp = S->Pop();
LOp = S->Pop();
switch(expression[i])
{
case '+' : S->Push(LOp + ROp);
break;
case '-' : S->Push(LOp - ROp);
break;
case '*' : S->Push(LOp * ROp);
break;
case '/' : S->Push(LOp / ROp);
break;
}
}
}
Result = S->Pop();
return(Result);
}
