Evaluate Fixpost Expressions with Linked Stack

[mlanuri10]

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";
}

[Mitsuru]

What do you want to do?
To use this library? Or to modify it?

It might seem this is a simple data structure.

[mlanuri10]

By using this library. But I'm confused on what to do here.

[mlanuri10]

What if I could modify this version?

[MikeyBoy]

Then... modify it?

You've told us absolutely nothing about what it is you want to do. How do you expect us to help?

[mlanuri10]

Oh never mind

[Ganado]

You #include "LStack.h" in the file where you have your main function
Then you can write something like:

#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")

[mlanuri10]

OK, thanks for that.

[mlanuri10]

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?