//
// CS 202 demonstration program 11_stack.cpp
// Written by Dave Williams for 11/13/03 class
//
// Stack-based calculator using singly-linked list
//
// Functions just like Hewlett Packard RPN ("reverse Polish notation")
// calculator system dating back to HP-35 (circa 1973) and extending
// through HP-48 series and the brand new HP 49G+.
//
struct Data // note numerical-based structure
{
int level; // stack level
double data; // data for stack level
Data *pnext; // pointer to next record
};
void Show_stack(Data *); // pass by value
void Pop(Data *&, Data *&, Data *&, Data *&); // by reference - why?
void Push(Data *&, Data *&, Data *&, Data *&, double); // also by reference
void Swap(Data *&, Data *&, Data *&, Data *&); // and again
#include <iostream.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h> // for atof (ASCII to double conversion)
int main()
{
char choice[24]; // we want a char here - why?
float result;
Data *pnew = 0;
Data *pfirst = 0;
Data *plast = 0;
Data *pprev = 0;
Data *pactive = 0;
cout << "\n\nProgram to implement a stack-based 'RPN' calculator."
<< "\n\nEnter a number at prompt and press to push or"
<< "\nenter an operation and press to execute. Any"
<< "\nunrecognized character data will push 0 on the stack. "
<< "\n\nThe current stack is updated after every entry.";
cout << endl;
cout << "\n\n----------------------------------------------------\n";
Show_stack(pfirst) ; // show empty stack at the beginning
do
{
cout << "\n\n----------------------------------------------------";
cout << "\n(d)rop (s)wap (n)egate + - * / ^ (q)uit ";
cout << "\n---------------------------------------------------- --> ";
cin >> choice;
switch(choice[0])
{
case 'q':
exit(0);
break;
case '+': // perform operations:
if (pprev != 0) // check for at least two
{ // data on the stack,
result = pprev->data + plast->data; // capture data & operate,
Pop(pfirst, plast, pprev, pactive); // pop the stack,
plast->data = result; // then push result on stack.
}
else // if < 2 data for operation
cout << " "
<< "--> Stack underflow!";
break;
case '-': // These are, strictly
if (pprev != 0) // speaking, not "pure"
{ // stack operations because
result = pprev->data - plast->data; // they don't pop both data
Pop(pfirst, plast, pprev, pactive); // elements from the stack.
plast->data = result; // They are, however, a lot
} // faster and more efficient
// than that method.
else
cout << " "
<< "--> Stack underflow!";
break;
case '*': // Sometimes, being faster
if (pprev != 0) // and more efficient is
{ // better than being "pure".
result = pprev->data * plast->data; // see Swap() below for an
Pop(pfirst, plast, pprev, pactive); // example of "pure"
plast->data = result;
}
else
cout << " "
<< "--> Stack underflow!";
break;
case '/':
if (pprev != 0)
{
result = pprev->data / plast->data;
Pop(pfirst, plast, pprev, pactive);
plast->data = result;
}
else
cout << " "
<< "--> Stack underflow!";
break;
case '^':
if (pprev != 0)
{
result = pow(pprev->data , plast->data);
Pop(pfirst, plast, pprev, pactive);
plast->data = result;
}
else
cout << " "
<< "--> Stack underflow!";
break;
case 'd': // pop last data
Pop(pfirst, plast, pprev, pactive);
break;
case 's': // swap top two levels
Swap(pfirst, plast, pprev, pactive); // This one _is_ written as
break; // a 100% pure stack
// operation.
case 'n': // negate top level
plast->data = plast->data * -1;
break;
default: // create a new stack level & add data
Push(pfirst, plast, pprev, pactive, atof(choice));
}
Show_stack(pfirst); // show the stack after each operation
} while (1); // repeat endlessly until told to quit
return 0;
}
void Pop(Data *&pfirst, Data *&plast, Data *&pprev, Data *&pactive)
{
pactive = pfirst; // set pactive to bottom of stack
if (plast == 0) // means that stack is empty
cout << " "
<< "Stack underflow!";
else if (pactive->pnext == 0) // for one level in stack
{
pfirst = 0;
pactive = 0;
pprev = 0;
delete plast;
plast = 0;
}
else if (pactive->pnext == plast) // for two levels in the stack
{
pactive->pnext = 0;
pprev = 0;
delete plast;
plast = pactive;
}
else
{
while (pactive->pnext != pprev)
pactive = pactive->pnext; // find pactive that will become pprev
pprev->pnext = 0; // null this before deleting
pprev = pactive;
delete plast;
plast = pprev->pnext;
}
return;
}
void Push(Data *&pfirst, Data *&plast, Data *&pprev, Data *&pactive, double choice)
{
Data *pnew = 0; // a pointer for giving birth to new levels
pnew = new Data;
if (plast == 0) // if this is the first record,
{
plast = pnew; // then set all of these
pfirst = pnew;
pnew->level = 1;
}
else
{
pnew->level = plast->level + 1; // add stack level automatically
plast->pnext = pnew; // set pointer to new level
}
pnew->data = choice; // place the data
pnew->pnext = 0; // zero the pointer in new record
if (plast != pnew) // set pointer if not the first record
{
pprev = plast; // pprev points to second-newest level
plast = pnew; // and plast points to the newest
pnew = 0; // null this so it doesn't turn wild
}
return;
}
void Swap(Data *&pfirst, Data *&plast, Data *&pprev, Data *&pactive)
{
double value1, value2; // this the the 100% authentic "stack-approved"
// way to swap data values. It's done completely
if (pprev != 0) // with pops & pushes and without any data swaps
{
value1 = pprev->data; // capture data
value2 = plast->data;
Pop(pfirst, plast, pprev, pactive); // pop once
Pop(pfirst, plast, pprev, pactive); // pop twice
Push(pfirst, plast, pprev, pactive, value2); // then push one data back
Push(pfirst, plast, pprev, pactive, value1); // and then the other in
} // the reverse order
else
cout << " "
<< "--> Stack underflow!";
return;
}
void Show_stack(Data *pactive)
{
while(pactive != 0)
{
cout << "\n--------------------";
cout << "\nLevel " << pactive->level;
cout << ": " << pactive->data;
pactive = pactive->pnext;
}
cout << "\n====================";
return;
}
// 
// 
// 