RPN Calculator

[aeck]

I am having trouble with my RPN Calculator, I had it figured out with the stack<double> method, but I found out we have to use a linked list.

I am having trouble getting any output, it looks like the memory address is just being output, as well as the error checking, "too many operands", or "too many operators"
I have pasted the instructions and the code below, I have commented out a lot of my previous work to try to get it to work and I can't figure it out.

Any help would be appreciated.!




You must use a linked list to maintain the stack for this program
(array implementations of the stack will not receive full credit).

You must handle the following situations (errors):
Too many operators (+ - / *)
Too many operands (doubles)
Division by zero

The program will take in a Polish expression that separates the operators and
operands by a single space, and terminates the expression with an equals sign.

The program will continue to take and evaluate expressions until the user
enters a zero (0) on a line by itself followed by a new line.

Your sample output should show the handling of all the error conditions
as well as make use of all of the operators.

Sample IO: (note: formatting of output isn't a critical issue)
Input Output
10 15 + = 25
10 15 - = -5
2.5 3.5 + = 6 (or 6.0)
10 0 / = Error: Division by zero
10 20 * / = Error: Too many operators
12 20 30 / = Error: Too many operands
-10 -30 - = 20
100 10 50 25 / * - -2 / = -40

*/

#include <iostream>
#include <stack>
#include <string>
#include <sstream> //class called istringstream
#include<iomanip>

using namespace std;

class LinkedList
{
public:
double data;
LinkedList *top;
LinkedList *ptr;
int count;

LinkedList()
{
top = NULL;
ptr = NULL;
count = 0;
}

int size() { return count;}

void push(double val)
{
LinkedList *next = new LinkedList;
next -> data = val;
next -> ptr = top;
top = next;
}
double pop()
{
LinkedList *next = top -> ptr;
double ret = top -> data;
delete top;
top = next;
return ret;
}
void print()
{
LinkedList *node = NULL;
cout << "= " << data << endl << ">>";
}
};



//Function prototype for isOperator
bool isOperator(const string& input);

//Function prototype for performOperation
int performOperation(const string& input, LinkedList& calcStack);

int main()
{

//Linked list declaration
LinkedList calcStack;

//Variable declaration
//stack<double> calcStack; //Declare stack<double> class
string input; //Declare a string named input
double num;



cout << "RPN Calculator: " << endl;
//Prompt the user to input their expression to be calculated
cout << "Input\n";
//Declare a double named num

//Terminate program when 0 is entered by user
while(input != "0\n")
{

// Input from user
cin >> input;


/*Use istringstream function to read input where the
operators and operands are separated by a single space*/
if(istringstream(input) >> num)
{
//use push function
calcStack.push(num);
}

// check for operator, Call function isOperator
else if(isOperator(input))
{
//Call perforOperation function
performOperation(input, calcStack);
}
//terminates the expression with an equals sign

else if(input == "=")
{
//Error checking for too many operands by checking calcStack.size




if (calcStack.size() != 1)
{
cout << "Error: too many operands" << endl;
calcStack.print();
system("pause");
return 1;
}


else
{
/*Output the result- calcStack.top returns a
reference to the top element in the stack*/

//cout << "Output: " << data << endl;


//<< calcStack.top();

/*calcStack.pop() Removes the element on top
of the stack, effectively reducing its size by one.*/
calcStack.pop();
cout << endl << endl;
}

}
}
}

//Function definition for isOperator
bool isOperator(const string& input)
{
//Declare a static const string and initlialize te the operators
static const string operators = "-+*/";

//Error check for right size to be an operator.
if (input.length() == 1)
{
// look in the operator string for the first character in input
return operators.find_first_of(input[0]) != string::npos;
}
else
{
return false;
}

}

//Function defition for performOperation
int performOperation(const string& input, LinkedList& calcStack)
{
double firstOperand = 0; //Declare double for firstOperand
double secondOperand = 0; //Declare double for secondOperand
double result = 0; //Declare double for result



/*

//Error chceck for too many operators, if too many operators, exit program
if( calcStack.size() < 2 )
{
cout << "Error: too many operators" << endl;
system("pause");
exit(0);

}
*/


/*Assign secondOperand to calcStack.top returning a reference to the top element in the stack*/
//secondOperand = calcStack.top();

/*calcStack.pop() Removes the element on top of the stack, effectively reducing its size by one.*/
firstOperand = calcStack.pop();

//Assign firstOperant to calcStact.top()
//firstOperand = calcStack.top();
secondOperand = calcStack.pop();

//Switch statement for processing calculations
switch (input[0])
{//Begin switch
case '-': //Calculate subtraction, assign to result
//result = firstOperand - secondOperand;
calcStack.push(firstOperand - secondOperand);
break;
case '+': //Calculate addition, assign to result
calcStack.push(firstOperand + secondOperand);
break;
case '*': //Calculate multiplacation, assign to result
calcStack.push(firstOperand * secondOperand);
break;
case '/':
//Error checking for division by 0, if division by 0, exit program
if (secondOperand == 0)
{
cout << "Error: Division by 0.\n";
calcStack.print();
system("pause");
exit(0);
}
//Calculate division, assign to result
calcStack.push(firstOperand / secondOperand);
break;

}//End switch


//calcStack.push inserts a new element at the top of the stack, above its current top element.
//calcStack.push(result);

return 0;
}

[MikeyBoy]

Please use code tags when posting code, to make it readable:

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

[dhayden]

Unless the prof requires you to implement your own linked list, just use std::list instead of your LinkedList class.

If you call pop() when the stack is empty, you'll corrupt the heap.

Your print() method prints the data for a single item, not the entire stack.

[aeck]

I have changed and figured out some more of the code. Unfortunately my teacher does require me to use Linked List for this assignment.

I am having some trouble with the Error checking:

Too many operators (+ - / *)
Too many operands (doubles)
Division by zero
The program is supposed to continue to take and evaluate expressions until the user enters a zero (0) on a line by itself followed by a new line. I am also having some trouble with this. Since I put in my error checking for too many operands, it
WILL NOT ALLOW ME TO DO A SECOND CALCULATAION , OUTPUT WILL BE TOO MANY OPERANDS
I have tried several different things for the required error checking, as you can see through some of the things I tried and commented out.
Any help would be greatly appreciated!
Thanks

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

struct NODE
{
       float num;
       NODE *next;
};

class stack
{
    private:
      NODE *head;

    public:
      stack();
      void push(float);
      float pop();
      int nElements();
      float display();
};

class RPN: public stack
{
    public:
      void add();
      void subtract();
      void multiply();
      void divide();
};


stack::stack()
{
     head = NULL;
}

void stack::push(float a_number)
{
     NODE *temp = new NODE;
     if (temp)
	 {
        temp->num = a_number;
        temp->next = head;
        head = temp;
     }
}

float stack::pop()
{
	float number = 0;


    if (!head)
      {
         return 0;
      }
      else
      {
           NODE *temp = head;
           number = head->num;
           head = temp->next;
           delete temp;
      }
      return number;
}

int stack::nElements()
{
    int counter=0;
    for (NODE *node = head; node; node=node->next)
    {
        counter++;
    }
    return counter;
}

float stack::display()
{

	

	 //ERROR CHECKING TOO MANY OPERANDS???       PRINTING TOO MANY OPERANDS FOR :   100 10 50 25 / * - -2 / =	, but still giving correct output && WILL NOT ALLOW ME TO DO A SECOND CALCULATAION , OUTPUT WILL BE TOO MANY OPERANDS

	   if(nElements() !=1)
	  {
		   cout << "Error: too many operands" << endl;
			return 1;
	  }

	   /*
		//   if( nElements() < 2 )
			{
				cout << "Error: too many operators" << endl;
				return 1;
			}
*/



			   else //(nElements() > 0)
			   {
				 float temp = pop();
				 cout << temp << endl;
				 push(temp);

				 return temp;

			   }
	 

      
}


void RPN::add()
{
     if (nElements()>=2)
     {
        push(pop() + pop());
     }
}

void RPN::subtract()
{
     if (nElements()>=2)
     {
        push(0 - pop() + pop());
     }
}

void RPN::multiply()
{
     if (nElements()>=2)
     {
        push(pop() * pop());
     }
}

void RPN::divide()
{
     if (nElements()>=2)
     {
		 //if(pop() * pop() == 0)
		// {
			 //cout << "Error: Divide by 0.\n";
		// }
		
			 push(1 / pop() * pop());	
     }


	 //else if( nElements()>=2)
		// {
    	//	 cout << "Error: Divide by 0.\n";						//??????
		 //}
		
}

//Function prototype for isOperator
bool isOperator(const string& input);

//Function prototype for perforOperation
int performOperation(const string& input, RPN& calculator);

Int main(){

    RPN calculator;
    string input;
	
     float num;

    cout << "RPN Calculator: " << endl;
    cout << "Input\n";


    while(input != "0")
           {
               //Terminate program when 0 is entered by user
               while(true)
               {

               // get input
               cin >> input;

               // check for being numeric value

                   if(istringstream(input) >> num)
                   {
                       //use push function
                	   calculator.push(num);
                   }

                   // check for operator
                   else if(isOperator(input))
                   {
                       performOperation(input, calculator);
                   }

                   // If user enters 0 on a line followed by a new line, the program exits     ????????????
                   else if(input == "0\n")
                   {
                       return -1;
                   }


               }
               }
   }

bool isOperator(const string& input)
{
    static const string operators ="-+*/";
    if (input.length() == 1) // right size to be an operator.
    {
        return operators.find_first_of(input[0]) != string::npos;
        // look in the operator string for the first (and only) character in input
    }
    return false;
}



int performOperation(const string& input, RPN& calculator)
{
    //double firstOperand = 0;
    //double secondOperand = 0;
    //double result;



    /*
    if( calculator.size() > 2 )                      //Error check gives a false error for last input ???
    {
        cout << "Error: too many operands" << endl;
        return 1;
    }

    //Error chceck for too many operators           ////STILL PRINT OUTPUT???
    if( calculator.size() < 2 )
        {
            cout << "Error: too many operators" << endl;
            return 1;
        }
*/


    switch (input[0])
    {
    case '+': calculator.add();
              calculator.display();
              break;
    case '-': calculator.subtract();
              calculator.display();
              break;
    case '*': calculator.multiply();
              calculator.display();
              break;
    case '/':  calculator.divide();

				//if (firstOperand / 0) 
				//{
				//	cout << "Error: Divide by 0.\n";
				//}
    		   calculator.display();
    		  break;
    }
                        	/*
                        	if (secondOperand == 0)
                        	            { // moved this test to here because it's the only place it matters.
                        	                cout << "Error: Division by 0.\n";
                        	                return -1;
                        	            }
*/





return 0;

}

[aeck]

This is the sample input and output


Input Output
10 15 + = 25
10 15 - = -5
2.5 3.5 + = 6 (or 6.0)
10 0 / = Error: Division by zero
10 20 * / = Error: Too many operators
12 20 30 / = Error: Too many operands
-10 -30 - = 20
100 10 50 25 / * - -2 / = -40

[aeck]

I got the error division by 0 check to work, It just keeps printing the output in addition to the error : /

int RPN::divide()
{
	
	double op2;

	op2 = pop();

	if(op2 != 0.0)
	{
	push(pop() / op2);
	}
	else
	{
	cout << "Error: Division by zero.\n";
	return -1;
	}
}

[TheIdeasMan]

Hi,

With line 8 in your last snippet, Google & read up about floating point arithmetic. It's not exact, and not all numbers can be represented, and there are some different techniques to achieve things. There can be some surprising results if one doesn't follow the accepted way of doing things.

What you need is some kind of precision value (+0.001 or +1e-6 say - whatever suits you) - call it Epsilon say. To test for equality, check if the absolute value of the difference between the 2 numbers, is less than Epsilon. If so, they are "equal". Always use relational operators (<, > , <=, >= etc), never equality operators.



Hope this helps a bit :+)

[dhayden]

read up about floating point arithmetic. It's not exact, and not all numbers can be represented

He's checking for division by (exactly) zero. Inexact floating point values don't apply for that check.

Looking at the expected output, it appears to me that you need to read a line of text and then process the entire line. Only then can you tell if there are extra items on the stack. The easiest pattern for reading and processing a line of input is the one t

isOperator() could be better. For example, what if the user enters

10 15 -:)

?

performOperation() should just perform the operation, it shouldn't display the results or do any error checking.

Regarding error checking, I think this is one of the very few places where I'd recommend using exceptions. Create a stack method called checkSize(int n) that checks whether there are n or more items on the stack. If not, throw an exception. Then your add function can simply be:

void
RPN::add()
{
    checkSize(2);
    push(pop() + pop());
}

The nice thing about doing it this way is that it will catch errors like

1 2 - + 3 4 +

Similarly, throw an exception if you get divide by zero.
Since performOperation() takes an RPN as a parameter, it would be better to make it a method of class RPN. Also there's no need for it to return anything. See how this is cleaner?

void
RPN::performOperation(const string & input)
{
    switch (input[0]) {
    case '+':
	add();
	break;
    case '-':
	subtract();
	break;
    case '*':
	multiply();
	break;
    case '/':
	divide();
	break;
    }
}

[dhayden]

Send me a PM if you want to go over this in more detail.

[LB]

dhayden wrote:

Send me a PM if you want to go over this in more detail.

Duoas wrote:

What, so you can decide who gets to understand and who doesn't?

What's wrong with continuing this thread in public?

[aeck]

Regarding error checking, I think this is one of the very few places where I'd recommend using exceptions. Create a stack method called checkSize(int n) that checks whether there are n or more items on the stack. If not, throw an exception. Then your add function can simply be:


I am having difficulty understanding this. Are you able to give an example of the exceptions?

[TheIdeasMan]

dhayden wrote:

He's checking for division by (exactly) zero. Inexact floating point values don't apply for that check.

I am having trouble seeing this. What happens when a number on the stack is very close to zero as result of some other operation? As in the following, the expression in parentheses is near to zero : -3e-16 say:

5.0 / (0.1 * 10.0 - 1.0)

That could result in a large number: -1.6e16 say.

As far as I understand equality operators with floating point is nearly always bad, so it is a good thing for someone to learn - or at least be aware of.

[dhayden]

As far as I understand equality operators with floating point is nearly always bad, so it is a good thing for someone to learn - or at least be aware of.

I agree 100%, but I think division by zero is a special case.

5.0 / (0.1 * 10.0 - 1.0)

Here I don't think the issue is dividing by by this value should be treated as division by zero, but rather whether the value of

0.1 * 10.0 - 1.0

should be rounded to zero. For division by zero, if you assume that "close to zero is probably zero" then you're basically throwing away precision bits on a number that might be what you want. Consider 1e-20 / 1e-20. Should this be 1, or should it result in division by zero?

I know for a fact that in the 70's and early 80's, HP paid an enormous amount of attention to issues like this in it's hand held calculators. You'll find that their (and most other manufacturers') calculators do arithmetic in base 10 to avoid unexpected results like your 0.1*10.0-1.0 example.

[TheIdeasMan]

@audreyeckman

Are you aware of the tutorial and reference sections at the top left of this page? There are example code snippets there, plus you should be able to find lots of stuff via Google. There is also

cppreference.com

for a detailed technical view of every aspect of c++.

http://en.cppreference.com/w/cpp/language/exceptions

You could make use of my earlier advice to write an IsZero function:

const bool RPN::IsZero (const double Value, const double Precision) const;

Although it might be better in a larger scope - that is, maybe not in the RPN class.

And it could be further improved by writing a template so it can handle float and long double as well.



@dhayden

Thanks for your as per usual great comments :+) With this part, though:

Consider 1e-20 / 1e-20. Should this be 1, or should it result in division by zero?

Would that not be taken care of via the selection of the epsilon value? If one was doing some calculation involving the mass of an electron say, then one would select an epsilon value appropriate for that range of numbers. I guess there are situations where one wouldn't use an epsilon value at all: as in situations where it is valid to have both small and large numbers.

Maybe this all gets back to what we have discussed before: there is general advice, which is good for most things; then situations where the opposite is appropriate for those who know what they are doing.

As a side note, IIRC it was proposed that c++17 would have exact decimal numbers (finally, lots of other systems have had them for a long time). This would be particularly useful for currency applications, amongst other things.

Mind, I wonder if Dennis Ritchie might roll in his grave if people start using doubles in the control expressions of for loops :+D

Another thing c++11 has std::nextafter and std::nexttoward, which someone might find useful.