Reverse Polish Stack Help

[WakeofMisery]

I have to create a Reverse Polish Stack that's managed or maintained by a linked list. I have done quite a bit of researching and versed myself in what big o notation, reverse polish expressions, and linked lists are, but am still falling short of coding it. I'm supposed to code it so that the program will take reverse polish expressions until the user enters 0, followed by a new line. I am currently way off on my code and need some guidance. The program separates the operators and operands by a single space, and terminates the expression with an equals sign. My instructions are to handle the following errors:
Too many operators (+ - / *)
Too many operands (doubles)
Division by zero

source.cpp

#include <iostream>
#include "node.h"
#include <string>
#include <sstream>

using namespace std;

float pop(node *top) {
	float x;
	x = top->input;
	top->tail = top;
	top->head = NULL;
	return x;
}

void push(node *top, node *net) {
	if (top == NULL) {
		top = net;
	}
	else {
		top->head = net;
		net->tail = top;
		top = net;
	}
}

int main() {
	node *top;
	float num;
	string input;
	string value;
	cout << "Please enter a string of numbers and operators." << endl;
	getline(cin, input);
	stringstream ins(input);

	while (getline(ins, value, ' ')) //Reads user's input, stores into the value variable, and uses a space delimiter.
	{
		stringstream stream(value);
		if (stream >> num) { //push
			if (num == 0)
				break;
			node net = node(num);
			push(top, &net);
		}
		else { //pop
			if (top->tail == NULL) {
				cout << "There aren't any more values on the stack." << endl;
			}
			else {
				if (value == "*") {
					cout << (top->input * top->tail->input) << endl;
				}
				if (value == "/") {
					if (top->tail->input == 0) {
						cout << "Division by zero error." << endl;
					}
					else
						cout << (top->input / top->tail->input) << endl;
				}
				if (value == "+") {
					cout << (top->input + top->tail->input) << endl;
				}
				if (value == "-") {
					cout << (top->input - top->tail->input) << endl;
				}
			}
			pop(top);
		}
	}
	system("pause");
	return 0;
}

node.cpp

#include <iostream>
#include <cstdlib>
#include "node.h"

using namespace std;

node::node(float input) {
	*head = NULL;
	*tail = NULL;
	input = input;
}

node::~node() {
}

node.h

#pragma once
#include "node.cpp"

using namespace std;

class node
{
public:
	float input;
	node *head;
	node *tail;
	node(float input);
	~node();
};

[TheIdeasMan]

Hi,

Could you please edit your post, remove the line numbers, and use code tags :+)

Using tags in this article:

http://www.cplusplus.com/articles/z13hAqkS/

[WakeofMisery]

Sorry about that... I copied and pasted from an older post that didn't get any replies. Should be fixed now.

[TheIdeasMan]

Hi,

Have you considered having a class for the stack? It maintains the nodes and has push and pop IsEmpty and other functions.

Then have a class for the RPN calculator. It accepts input in the constructor, then analyses it. It pushes it if it's a number, pops, calculates and push the answer if it's an operator.

Hope this helps :+)

[dhayden]

Do you have to write your own linked-list implementation or can you use std::list or std::forward_list? Using one of them will cut the amount of work in half because, as TheIdeasMan points out, there are basically two parts to the problem: a linked list, and an RPN calculator that uses it.

In the calculator, you should always push and pop the items to/from the front of the list. Also, when doing an operation, you need to pop TWO values of the list, do the operation, and push the resulting value back on. Or you could just pop one value and modify the top of the stack. For example

else { // pop
   v1 = pop();
   v2 = pop();
   float result;
   // set result to the result of the operation
   push(result);
}

If you want to see how this works in real life, buy or borrow an HP scientific calculator. Once you try RPN, you'll never go back :)

[WakeofMisery]

Good question. I actually have to code my own linked list. I'm not allowed to use any libraries that contain linked list capabilities within. Thus, my program gets harder for that reason lol. @TheIdeasMan: My node.h file is my class. I got the push and pop functions to work already. I have a few errors because the class is missing a static variable and it has trouble locating a node instance in my Source.cpp file. My program was working and then all of a sudden stopped working. I set it down to charge, came back, and it had 46 errors for whatever reason.

[TheIdeasMan]

My node.h file is my class. I got the push and pop functions to work already.

But I was saying you need to have a LinkedList class that has push, pop etc and uses the node class, and the logic you have in main() should be in the RPN class.

Don't be afraid to create more classes if you need them.

Consider using double rather than float. The precision of float is easily exceeded.

[dhayden]

Is node a single node in a list, or the head of the list? If it's a node in the list, then what are the head and tail pointers for a node in the middle of the list?

Your push method modifies the top, but that's just the parameter, it doesn't modify the variable that was passed in.

To avoid such confusion, you should use two classes for the list: class node is is a node in the list and class list is the list itself:

class node {
public:
    double value;
    class node *next;
    node(double v) : value(v), next(nullptr) {}
};

class list {
public:
    list() : head(nullptr) {}
    void push(double val);
    double pop(val);
    bool empty();
    double top();   // return the value at the top without popping it.
private:
    class node *head;
};

[WakeofMisery]

node top is the last value or object placed in the stack.

The node head and node tail points are like arms in this case. The head points to the value above and the tail points to the value below. Therefore, if top's tail = NULL, the stack is empty.

@TheIdeasMan: I'm kind of struggling with the whole concept of OOP. I'm using C++ for the class I'm in, which is Data Structures, but I actually skipped C++ in school. I regret testing out of it lol. I have a general understanding of inheritance, object instantiation, pointers, etc., but I'm not grasping the whole picture so well. I seem to be stumped when it comes to understanding what my entire program is doing or how to code it. I had someone help me get it started and explain it to me as we went along, but I don't understand the beginning part of why things need to be declared where and such. All I really understand about classes is that I can use the name of the class and create an instance of it with any object name. My questions are: How would I use this new object, call the constructor properly, declare static variables in the right places, etc.?

[TheIdeasMan]

My questions are: How would I use this new object, call the constructor properly, declare static variables in the right places, etc.?

You can review classes here:

http://www.cplusplus.com/doc/tutorial/classes/

Also, prefer C++11 nullptr over NULL

.... but I'm not grasping the whole picture so well.

dhayden has given some really good clues and code :+)