[Zerobu]

Ok so i am writing a program to calculate postfix operations. I am almost done with the program only two things are left for me to do, which is to tell if the postfix expression is valid, and tell wheter divison by zero is taking place.

Here are the requirements of the program.

Computer Science 245 - Programming Assignment #3
Due Date: Mar 22, 2009 (11:55 PM)
75 pts.
Reverse Polish Notation

Topic: Stack implemented as a linked list, Evaluating Postfix Expressions
Input file: postfix.dat

Output file: postfix.out
Application File: Postfix.cpp
Header File : Stack.h
Implementation File: Stack.cpp

The C++ application (postfix.cpp) will simply evaluate the postfix expressions found in postfix.dat and will write the answer to each to postfix.out. The application must use a stack class in the solution process. The stack class must be implemented using a linked list with dynamic memory allocation and pointer variables.
Within the file postfix.dat, a postfix expression will be on every line. The file will terminate with the dollar sign (‘$’). A postfix expression will not exceed one line of text (80 characters). Tokens (operand or operator) in the expression will be separated by one space. There will be no leading spaces in front of an expression. The last token in an expression will terminate with a carriage return (‘\n’).

You must be careful when you evaluate each postfix expression in postfix.dat. Not every expression is a correctly formed postfix expression. Also, insure that a mathematical operation can be performed correctly (e.g. – don’t allow divison by zero).
Below is given a sample input and sample output. You may assume that there will not be more than 15 postfix expressions to be evaluated in the actual test file.
Please turn in all three files using EASEL.

Sample I/O
postfix.dat
15 -33 +
7 2 + 3 15 * 5 / - 7 - 8 +
-8 4 + 24 13 2 * *
15 4 4 - /
$


postfix.out
The answers to the problems in postfix.dat are...
1) -18
2) 1
3) incorrect postfix expression
4) error, tried to divide by zero

Here are my three files

Stack.h

typedef double StackType;

struct node
{
	StackType data;
	node *next;
};


class Stack
{
public:
	Stack();
	~Stack();
	bool Push(StackType operand);
	bool Pop(StackType &operand);
	bool Empty();
	bool Full();

private:
	node *top;
};

Stack.cpp

#include "Stack.h"
#include<iostream>


Stack::Stack()
{
	top = NULL;
}

bool Stack::Full()
{
	node *temp;
	temp = new node;

	if(temp == NULL)
		return true;

	else
		return false;


}


bool Stack::Push(StackType operand)
{
	if( !Full() )

	{
		node *temp;

		temp=new node;

		if(temp==NULL)
			return false;

		else
		{
			temp->data = operand;
			temp->next = top;
			top=temp;

			return true;
		}

	}


	return false;
}

bool Stack::Empty()
{
	if(top == NULL)
		return true;
	else
		return false;

}
bool Stack::Pop(StackType &operand)
{
	if( !Empty() )
	{
	
		node *temp;

		temp = top;

		operand = temp->data;
		top = top->next;

		delete temp;
		return true;
	}
	

	return false;
}


Stack::~Stack()
{
	if(top==NULL)
		return;

	node *tmp;
	while(top!=NULL)
	{
		tmp=top;
		top=top->next;
		delete tmp;

	}
}

Postfix.cpp

#include<iostream>
#include<fstream>
#include<string>
#include<cctype>
#include"Stack.h"
using namespace std;

const string EXIT_CHAR = "$";


Stack operandStack;

void ParseToken(string &postfix, string & token)
{

	token.assign(postfix,0, postfix.find(' '));
	postfix.erase(0, postfix.find(' ')+1);

}

void PushOrPop(StackType &num1, StackType &num2, string token)
{

	StackType num_token = atoi(token.c_str());


	if(num_token != 0)
	{
		operandStack.Push(num_token);

	}
	else
	{
		operandStack.Pop(num1);
		operandStack.Pop(num2);

	}
}

void PerformOperation(StackType num1, StackType num2, string token)
{

	StackType result;

	if(token =="+")
	{
		result = num2 + num1;
		operandStack.Push(result);
	}
	else if(token =="-")
	{
		result = num2 - num1;
		operandStack.Push(result);
	}

	else if(token =="/")
	{
		result = num2/num1;
		operandStack.Push(result);
	}

	else if(token == "*")
	{
		result = num2 * num1;
		operandStack.Push(result);
	}

}

void WriteToFile(ofstream & fout )
{
	StackType result;

	operandStack.Pop(result);

	fout << result <<endl;
}	

void EvaluateExpression(string postfix)
{
	string token;
	StackType num1, num2;

	while( !postfix.empty() )
	{

		ParseToken(postfix, token);
		PushOrPop(num1, num2, token);
		PerformOperation(num1, num2, token);


		if(postfix.size()== 1 && postfix == token)		   //Erase postfix when last character is equal to token
			postfix.erase(0, postfix.size());

	}


}

void main()
{
	string postfix;
	ifstream fin;
	ofstream fout;

	fin.open("postfix.dat");
	fout.open("postfix.out");

	do
	{
		getline(fin, postfix);
		EvaluateExpression(postfix);

		if(postfix != EXIT_CHAR)				  //Only write to file when postfix = EXIT_CHAR
			WriteToFile(fout);

	}while(postfix != EXIT_CHAR);

	fin.close();
	fout.close();
}

[matthew180]

Okay, so what is your question?

Matthew

[Zerobu]

I want to write a Function to determine if the postfix expression tries to divide by zero. and also to try and find if it is a valid postfix expression

[mischief6]

Steffan, on 21 Mar, 2009 - 05:25 PM, said:

I want to write a Function to determine if the postfix expression tries to divide by zero. and also to try and find if it is a valid postfix expression

although bulky, boost::regex would make this insanely simple. almost as simple as perl

[Zerobu]

mischief6, on 21 Mar, 2009 - 05:31 PM, said:

Steffan, on 21 Mar, 2009 - 05:25 PM, said:

I want to write a Function to determine if the postfix expression tries to divide by zero. and also to try and find if it is a valid postfix expression

although bulky, boost::regex would make this insanely simple. almost as simple as perl

whats boost:: regex?

[mischief6]

it's a part of the boost library, for doing regex-related things.

[Zerobu]

I'm doing this for Data Structures class, so i don't think our teacher wants us to use the boost library.

[matthew180]

What is wrong with something like this?

	else if(token =="/")
	{
		// Check for divide by 0
		if ( num1 == 0 )
			return false;

		result = num2/num1;
		operandStack.Push(result);
	}

You need to modify your function to return true of false, then check that return.

As for detecting an invalid postfix, if you have numbers left over with no operator, then you have an error. Also, if you have an operator token, but not two numbers on your stack, then there is an error with the input.

I've never had to write one of these, but if I did, following the pseudo code on the wikipedia page seems easy enough. You might want to check it out to see if you are doing something similar. WikiPedia RPN

Here is the excerpt:

The algorithm for evaluating any postfix expression is fairly straightforward:

	* While there are input tokens left
		  o Read the next token from input.
		  o If the token is a value
				+ Push it onto the stack.
		  o Otherwise, the token is an operator.
				+ It is known a priori that the operator takes n arguments.
				+ If there are fewer than n values on the stack
					  # (Error) The user has not input sufficient values in the expression.
				+ Else, Pop the top n values from the stack.
				+ Evaluate the operator, with the values as arguments.
				+ Push the returned results, if any, back onto the stack.
	* If there is only one value in the stack
		  o That value is the result of the calculation.
	* If there are more values in the stack
		  o (Error) The user input too many values.

Matthew

This post has been edited by matthew180: 21 March 2009 - 08:15 PM

[Zerobu]

Ok i got it give an error message when divison by zero is done all i need to do is to tell if the postfix expression is correct or not.

Here is my updated cpp file

#include<iostream>
#include<fstream>
#include<string>
#include"Stack.h"
using namespace std;


/*************************************************************************
GLOBAL DECLARATIONS
*************************************************************************/

const string EXIT_CHAR = "$";
const string ADD = "+";
const string MINUS = "-";
const string MULTIPLY = "*";
const string DIVIDE = "/";

//Instantiate the operand stack
Stack operandStack;


void ParseToken(string & postfix, string & token)
{

	token.assign(postfix,0, postfix.find(' '));			//Assigns a character untill whitespace is reached
	postfix.erase(0, postfix.find(' ')+1);				//Erase the character that was assigned, from postfix

}

void PushOrPop(StackType & num1, StackType & num2, string token)
{

	StackType num_token = atoi(token.c_str());


	if(token == "0" || num_token != 0)					//If atoi returns a zero and num token == 0 then push 0
	{
		operandStack.Push(num_token);

	}
	else
	{
		operandStack.Pop(num1);
		operandStack.Pop(num2);

	}
}

void PerformOperation(StackType num1, StackType num2, string token, ofstream & fout)
{

	StackType result;

	if(token == ADD)
	{
		result = num2 + num1;
		operandStack.Push(result);
	}
	else if(token == MINUS)
	{
		result = num2 - num1;
		operandStack.Push(result);
	}

	else if(token == DIVIDE)
	{
		if(num1 == 0)
		{
			fout << "error, tried to divide by zero" <<endl;
			operandStack.~Stack();									//Stack is cleared
		}
		else
		{

			result = num2/num1;
			operandStack.Push(result);
		}
	}

	else if(token == MULTIPLY)
	{
		result = num2 * num1;
		operandStack.Push(result);
	}

}

void ValidateExpression(string & postfix, ofstream & fout)
{
	int operand_count = 0;
	int operator_count = 0;
	int num_token = 0;
	string token;

	for(unsigned int i = 0; i < postfix.length(); i++)
	{
		token = postfix[i];

		num_token = atoi(token.c_str() );

		if(token == "0" || num_token != 0)					
		{
			operand_count++;
		}
		else if(token != " ")
		{
			operator_count++;

		}

	}

	if(operator_count == (operand_count - 1))
	{
		fout << "incorrect postfix expression" <<endl;
		postfix.clear();
		
	}
	
}

void EvaluateExpression(string postfix, ofstream & fout)
{
	string token;
	StackType num1, num2;

	while( !postfix.empty() )		
	{
		//ValidateExpression(postfix, fout);
		ParseToken(postfix, token);
		PushOrPop(num1, num2, token);
		PerformOperation(num1, num2, token, fout);

		

		if(postfix.size()== 1 && postfix == token)		   //Erase postfix when last character is equal to token
			postfix.erase(0, postfix.size());

	}


	
}

void WriteToFile(ofstream & fout)
{
	if(!operandStack.Empty() )							//An empty stack means an error was encountered.
	{													//So nothing is written when stack is empty
		StackType result;

		operandStack.Pop(result);


			fout << result << endl;
		
	}

	
}	

void main()
{
	string postfix;
	ifstream fin;
	ofstream fout;
									 

	fin.open("postfix.dat");
	fout.open("postfix.out");

	do
	{
		getline(fin, postfix);
		EvaluateExpression(postfix, fout);			//fout is passed to write divison by zero error if encounterd.

		if(postfix != EXIT_CHAR)					 //Only write to the file when postfix = EXIT_CHAR
			WriteToFile(fout);

	}while(postfix != EXIT_CHAR);

	fin.close();
	fout.close();
}

This post has been edited by Steffan: 22 March 2009 - 03:04 PM