Evaluate Fixpost Expressions with Linked Stack

I have the linked stack files (header and implementation). But I don't know how to write a program with these.

/*-- LStack.h --------------------------------------------------------------

This header file defines a Stack data type.
Basic operations:
constructor: Constructs an empty stack
empty: Checks if a stack is empty
push: Modifies a stack by adding a value at the top
top: Accesses the top stack value; leaves stack unchanged
pop: Modifies stack by removing the value at the top
display: Displays all the stack elements
Note: Execution terminates if memory isn't available for a stack element.
--------------------------------------------------------------------------*/

#include <iostream>
using namespace std;

#ifndef LSTACK
#define LSTACK

typedef int StackElement;

class Stack
{
public:
/***** Function Members *****/
/***** Constructors *****/
Stack();
/*-----------------------------------------------------------------------
Construct a Stack object.
Precondition: None.
Postcondition: An empty Stack object has been constructed
(myTop is initialized to a null pointer).
------------------------------------------------------------------------*/

Stack(const Stack & original);
//-- Same documentation as in Figure 7.8

/***** Destructor *****/
~Stack();
/*------------------------------------------------------------------------
Class destructor

Precondition: None
Postcondition: The linked list in the stack has been deallocated.
------------------------------------------------------------------------*/

/***** Assignment *****/
const Stack & operator= (const Stack & rightHandSide);
/*------------------------------------------------------------------------
Assignment Operator
Precondition: rightHandSide is the stack to be assigned and is
received as a const reference parameter.
Postcondition: The current stack becomes a copy of rightHandSide
and a const reference to it is returned.
------------------------------------------------------------------------*/

bool empty() const;
/*------------------------------------------------------------------------
Check if stack is empty.
Precondition: None
Postcondition: Returns true if stack is empty and false otherwise.
-----------------------------------------------------------------------*/

void push(const StackElement & value);
/*------------------------------------------------------------------------
Add a value to a stack.

Precondition: value is to be added to this stack
Postcondition: value is added at top of stack provided there is space;
otherwise, a stack-full message is displayed and execution is
terminated.
-----------------------------------------------------------------------*/

void display(ostream & out) const;
/*------------------------------------------------------------------------
Display values stored in the stack.

Precondition: ostream out is open.
Postcondition: Stack's contents, from top down, have been output to out.
-----------------------------------------------------------------------*/

StackElement top() const;
/*------------------------------------------------------------------------
Retrieve value at top of stack (if any).

Precondition: Stack is nonempty
Postcondition: Value at top of stack is returned, unless the stack is
empty; in that case, an error message is displayed and a "garbage
value" is returned.
-----------------------------------------------------------------------*/

void pop();
/*------------------------------------------------------------------------
Remove value at top of stack (if any).

Precondition: Stack is nonempty.
Postcondition: Value at top of stack has been removed, unless the stack
is empty; in that case, an error message is displayed and
execution allowed to proceed.
-----------------------------------------------------------------------*/

private:
/*** Node class ***/
class Node
{
public:
StackElement data;
Node * next;
//--- Node constructor
Node(StackElement value, Node * link = 0)
/*-------------------------------------------------------------------
Precondition: None.
Postcondition: A Node has been constructed with value in its data
part and its next part set to link (default 0).
-------------------------------------------------------------------*/
: data(value), next(link)
{}
};

typedef Node * NodePointer;

/***** Data Members *****/
NodePointer myTop; // pointer to top of stack

}; // end of class declaration

#endif


//--- LStack.cpp -------------------------------------------------

#include <new>
using namespace std;

#include "LStack.h"

//--- Definition of Stack constructor
Stack::Stack()
: myTop(0)
{}

//--- Definition of Stack copy constructor
Stack::Stack(const Stack & original)
{
myTop = 0;
if (!original.empty())
{
// Copy first node
myTop = new Stack::Node(original.top());

// Set pointers to run through the stacksÕ linked lists
Stack::NodePointer lastPtr = myTop,
origPtr = original.myTop->next;

while (origPtr != 0)
{
lastPtr->next = new Stack::Node(origPtr->data);
lastPtr = lastPtr->next;
origPtr = origPtr->next;
}
}
}

//--- Definition of Stack destructor
Stack::~Stack()
{
// Set pointers to run through the stack
Stack::NodePointer currPtr = myTop, // node to be deallocated
nextPtr; // its successor
while (currPtr != 0)
{
nextPtr = currPtr->next;
delete currPtr;
currPtr = nextPtr;
}
}

//--- Definition of assignment operator
const Stack & Stack::operator=(const Stack & rightHandSide)
{
if (this != &rightHandSide) // check that not st = st
{
this->~Stack(); // destroy current linked list
if (rightHandSide.empty()) // empty stack
myTop = 0;
else
{ // copy rightHandSide's list
// Copy first node
myTop = new Stack::Node(rightHandSide.top());

// Set pointers to run through the stacks' linked lists
Stack::NodePointer lastPtr = myTop,
rhsPtr = rightHandSide.myTop->next;

while (rhsPtr != 0)
{
lastPtr->next = new Stack::Node(rhsPtr->data);
lastPtr = lastPtr->next;
rhsPtr = rhsPtr->next;
}
}
}
return *this;
}

//--- Definition of empty()
bool Stack::empty() const
{
return (myTop == 0);
}

//--- Definition of push()
void Stack::push(const StackElement & value)
{
myTop = new Stack::Node(value, myTop);
}

//--- Definition of display()
void Stack::display(ostream & out) const
{
Stack::NodePointer ptr;
for (ptr = myTop; ptr != 0; ptr = ptr->next)
out << ptr->data << endl;
}

//--- Definition of top()
StackElement Stack::top() const
{
if (!empty())
return (myTop->data);
else
{
cerr << "*** Stack is empty "
" -- returning garbage ***\n";
StackElement * temp = new(StackElement);
StackElement garbage = *temp; // "Garbage" value
delete temp;
return garbage;
}
}

//--- Definition of pop()
void Stack::pop()
{
if (!empty())
{
Stack::NodePointer ptr = myTop;
myTop = myTop->next;
delete ptr;
}
else
cerr << "*** Stack is empty -- can't remove a value ***\n";
}
What do you want to do?
To use this library? Or to modify it?

It might seem this is a simple data structure.
By using this library. But I'm confused on what to do here.
What if I could modify this version?
Then... modify it?

You've told us absolutely nothing about what it is you want to do. How do you expect us to help?
Oh never mind
You #include "LStack.h" in the file where you have your main function
Then you can write something like:

1
2
3
4
5
6
7
8
#include "LStack.h"

int main()
{
    Stack stack;
    stack.push(4);
    stack.pop();
}


You have to add LStack.cpp to the list of files to compile and link together.

If you want to do expression parsing, you will probably need more than just ints; perhaps a stack of strings which represent equation tokens (e.g. "42", "+", "31")
Last edited on
OK, thanks for that.
How would I know whether if it's a digit then I could push on the stack or else if it's an operator then I have to value the last 2 numbers that I pushed?
Registered users can post here. Sign in or register to post.