1 Replies - 2699 Views - Last Post: 11 September 2008 - 05:22 PM Rate Topic: -----

#1 G0oDFeLLa  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 03-September 08

Postfix Evaluation Help

Posted 03 September 2008 - 03:13 PM

Hello, I need to create a program that you input a postfix expression and then the program evaluates that expression. For example if I input: "32*", it will evaluate it as "3*2" and then give me the answer which in this case is 6. I already have it and it compiles alright but it always gives me the wrong answer. Don't know why...Please help me. Here is what I have till now:

This is the main:
#include <iostream>
#include <stack>
#include <string>
#include "stack.h"
using namespace std;

int main()
{
	int i, choice;
	string postfixExp;
	char token;
	float value, value1, value2;
	Stack <char> stack_one; 
	//stack <float> stack_one;



	while (choice != 0)
	{
		cout << "1. Evaluate a postfix expression" << endl;
		cout << "0. Exit " << endl;
		cout << "Enter the number for the option: ";

		cin >> choice;

		switch(choice)
		{
			case 1: cout << "Evaluate a postfix expression\n";
			cout << "Enter the expression: ";
			cin >> postfixExp;
			i = 0;
			token = postfixExp[i];

		while((i < postfixExp.size()) && (token != '='))
		{
			if(isdigit(token))
			{
				value = token;
				stack_one.push(value);
			}
			else
			{
				value2 = stack_one.peek(value);
				stack_one.pop(value);
				value1 = stack_one.peek(value);
				stack_one.pop(value);  

				switch(token)
				{
					case '+': value = value1 + value2;
					break;
					case '-': value = value1 - value2;
					break;
					case '*': value = value1*value2;
					break;
					case '/': value = value1/value2;
					break;
				}
				stack_one.push(value);
			}  
			
			i++;
			
			token = postfixExp[i];
		}

		stack_one.isEmpty();
		value = stack_one.peek(value);
		stack_one.pop(value);
		
		cout <<"\nThe Postfix Expression entered is: " << postfixExp <<" and the value of the Postfix Expression is: "<< value << endl;
		break;

		case 0: cout << "Exiting the program\n";
		break;

		default: cout << "Invalid option\n";
		break;
		}
cout << endl;
}
} 


These are the other header and class files:

1) Array.cpp:

// Array.cpp -- function definitions for an array

// Error codes -- use powers of 2
// 0	No error.
// 1	Nonpositive size passed into constructor.
// 2	Invalid index was used.
// 4	Nonpositive new size passed into changeSize function

template <class DataType>
Array<DataType>::Array( int size )
{
	if ( size < 1 ) {
		capacity = 1;
		errorCode = 1; // nonpositive size
	}
	else {
		capacity = size;
		errorCode = 0; // no error
	}

	elements = new DataType [capacity];
}

template <class DataType>
Array<DataType>::Array( const Array<DataType> & ap )
{
	deepCopy( ap );
}

template <class DataType>
Array<DataType>::~Array( )
{
	delete [ ] elements;
}

template <class DataType>
Array<DataType> & Array<DataType>::operator =( const Array<DataType> & right )
{ 
	if ( this == &right )
		return *this;
	delete [ ] elements;
	deepCopy( right );

	return *this;
}

template <class DataType>
inline DataType & Array<DataType>::operator [ ]( int index )
{
#ifdef DEBUG_ARRAY
	if ( index < 0 || index >= capacity ) {
		errorCode |= 2;  // invalid index
		return dud;
		}
#endif
	return elements[ index ];
}

// will not alter values unless newSize is smaller than current capacity; 
// in this case, the values from 0 to newSize - 1 will not be altered
template <class DataType>
void Array<DataType>::changeSize( int newSize )
{
	if ( newSize < 1 )
	{
		errorCode |= 4; // nonpositive new size 
		return;
	}

	DataType *newArray = new DataType [newSize];

	int limit = (newSize > capacity)? capacity : newSize;

	for ( int i = 0; i < limit; i++ )
		newArray[ i ] = elements[ i ];

	delete [ ] elements;

	elements = newArray;

	capacity = newSize;
}

template <class DataType>
inline int Array<DataType>::length( ) const
{
	return capacity;
}

template <class DataType>
string Array<DataType>::err( ) const
{

	if ( errorCode == 0 )
		return "No error.\n";

	string errorMessage = "";
	if ( errorCode & 1 ) { // nonpositive size
		errorMessage += "Nonpositive size passed into constructor, so\n";
		errorMessage += "the capacity was set to 1 by default.\n";
	}
	if ( errorCode & 2 )  // invalid index
		errorMessage += "Index out of range.\n";
	if ( errorCode & 4 ) { // nonpositive new size in changeSize
		errorMessage += "Nonpositive size passed into changeSize, so\n";
		errorMessage += "the size of the array was not changed.\n";
	}

	return errorMessage;
}

template <class DataType>
inline void Array<DataType>::deepCopy( const Array<DataType> & original )
{
	capacity = original.capacity;
	errorCode = original.errorCode;
	elements = new DataType [capacity];
	for ( int i = 0; i < capacity; i++ )
		elements[ i ] = original.elements[ i ];
}



2) Array.h:

// Array.h -- class template for an adjustable array
// When debugging, use #define DEBUG_ARRAY above your #include "Array.h".
// When done debugging, comment out #define DEBUG_ARRAY for better performance. 
// The constructor, copy constructor, overloaded assignment, and changeSize 
// functions can cause an exception to be thrown if out of heap memory. 

#include <string>

using namespace std;

template <class DataType>
class Array
{
public:
	Array( int size );
	Array( const Array<DataType> & ap );
	~Array( );
	Array<DataType> & operator =( const Array<DataType> & right );
	inline DataType & operator [ ]( int index );   
	void changeSize( int newSize );	// will not alter values unless newSize is smaller
									// than current capacity; in this case, the values
									// from 0 to newSize - 1 will not be altered
	inline int length( ) const;		// returns the current capacity of the array
	string err( ) const;			// returns error message from errorCode
private:
	DataType *elements;		// points to the dynamic array
	int capacity;
	DataType dud;			// returned from operator [ ] if index error occurs
	int errorCode;			// contains code for error if array misuse occurs
	inline void deepCopy( const Array<DataType> & original );
};

#include "Array.cpp"



3) Stack.cpp
// stack.cpp -- the function definitions for the array implementation of a stack

template <class DataType>
Stack<DataType>::Stack( )
	: elements( 2 ), top( -1 )
{
}

template <class DataType>
void Stack<DataType>::push( DataType elementToPush )
{
	if ( ++top == elements.length( ) )
		elements.changeSize( elements.length( ) << 1 ); 
	elements[ top ] = elementToPush;
}

// removes an element from the top of the stack and returns it in poppedElement; 
// returns false if called on an empty stack; otherwise, returns true	
template <class DataType>
bool Stack<DataType>::pop( DataType & poppedElement )
{
	if ( top == -1  ) 
		return false;

	poppedElement = elements[ top ];
	top--;

	int trysize = elements.length( );
	while ( ( top + 1 <= trysize >> 2 ) && trysize > 2 )
		trysize >>= 1;	

	if ( trysize < elements.length( ) ) {
		try {
			elements.changeSize( trysize  );
		}
		catch( ... ) { }
	}

	return true;
}	

// returns the element at the top of the stack in topElement without removing it 
// returns false if called on an empty stack; otherwise, returns true	
template <class DataType>
bool Stack<DataType>::peek( DataType & topElement )
{
	if ( top == -1  ) 
		return false;
	topElement = elements[ top ];
	return true;
}

template <class DataType>
bool Stack<DataType>::isEmpty( ) const
{
	return top == -1;
}

template <class DataType>
void Stack<DataType>::makeEmpty( )
{
	top = -1;
	try {
		elements.changeSize( 2 );
	}
	catch( ... ) { }
}




4) Stack.h: This one includes all the other files( Array.cpp, Array.h, Stack.cpp)
// stack.h - the array implementation of a stack
// note:  the constructor, the (default) copy constructor, the (default) assignment operator,
// and push function can cause an exception to be thrown if heap memory is exhausted

#include "Array.h"

template <class DataType>
class Stack
{
public:
	Stack( );
	void push( DataType elementToPush );  

	// removes an element from the top of the stack and returns it in poppedElement; 
	// returns false if called on an empty stack; otherwise, returns true	
	bool pop( DataType & poppedElement );

	// returns the element at the top of the stack in topElement without removing it
	// returns false is called on an empty stack; otherwise, returns true
	bool peek( DataType & topElement ); 
	bool isEmpty( ) const;  // returns true if the stack is empty;
				// otherwise, returns false
	void makeEmpty( );
private:
	Array<DataType> elements;
	int top;
};

#include "stack.cpp"



I really need help so that I can have the correct answer of the evaluation of the postfix expression. Thanks in advance.

Is This A Good Question/Topic? 0
  • +

Replies To: Postfix Evaluation Help

#2 AngelE  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 11-September 08

Re: Postfix Evaluation Help

Posted 11 September 2008 - 05:22 PM

Change the following lines and the evaluation will do its thing

else
{
value2 = stack_one.peek(value);
stack_one.pop(value2);
value1 = stack_one.peek(value);
stack_one.pop(value1);

Greetz E

This post has been edited by PsychoCoder: 11 September 2008 - 05:42 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1