infix to postfix conversion

accounts for parenthesis

Page 1 of 1

4 Replies - 16090 Views - Last Post: 31 March 2010 - 09:13 AM Rate Topic: -----

#1 jessicalegner  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 1
  • View blog
  • Posts: 66
  • Joined: 05-June 09

infix to postfix conversion

Posted 29 March 2010 - 03:49 PM

Is it worth, what I think would be a hassle, to put this into a class? I am not the greatest with classes yet.
Asking for opinions.
To me, there isn't a whole lot of code. Not enough going on to put into a class. Am I wrong?

Also, my professor has encouraged us to use our own stack class vs. the existing one in C++, why exactly is that? I asked once, didn't get a good explanation and was "embarrassed" to ask a second time.

/*
Purpose---
INPUT:		A line containing an infix expression is read from the infix.txt file.
PROCESS:	For each line, the string is traversed character by character.  It is then determined
			if the character should be wrote to the string "postfixExpression" or dumped into the stack.
			precedence of operators is taken into account along with parenthesis.  The parenthesis are not
			printed in the postfix expression.  
OUTPUT:		The postfix expresion is wrote to the console.
On: 		03/29/2010
*/

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

#include "StackType.h"

// function prototypes
int precedence(char symbol);

int main()
{
	StackType<char> theStack(5);
	string aLine, postfixExpression;
	int i = 0;
	ifstream infixFile("infix.txt");
	infixFile >> aLine;				// priming read
	while(!infixFile.eof())
	{
		int length = aLine.length();
		postfixExpression = "";

		for(i = 0; i < length; i++)
		{
			char lineChar = aLine[i];
			//IF symbol is an operand (variable) append it to postfixExpression
			if (lineChar == 'A' || lineChar == 'B' || lineChar == 'C' || lineChar == 'D' || lineChar == 'E')
			postfixExpression += lineChar;

			//IF symbol is an operator ( + , -  , * , / ) determine to push or pop 
			else if(lineChar == '+' || lineChar == '-' || lineChar == '*' || lineChar == '/')
			{
				while(theStack.getTop() != '(' && precedence(theStack.getTop()) >= precedence(lineChar) && !theStack.isEmpty())
				{
					postfixExpression += theStack.pop(); 		// pop if top is greater than current
				}
				theStack.push(lineChar);						// push if current is greater than top
			}

			// IF symbol is ( push to stack
			else if(lineChar == '(')
				theStack.push(lineChar);

			// IF symbol is ) determine to pop and put into expression or discard the parenthesis
			else if(lineChar == ')')
			{
				while(theStack.getTop() != '(')
				{
					postfixExpression += theStack.pop();		// put operators into expression
				}
				theStack.pop(); 								// pop ( from stack and discard
			}
		}
		while(!theStack.isEmpty())
		{
			postfixExpression += theStack.pop();				// pop reamining symbols from stack
		}
		cout << postfixExpression << endl;						// display result
		infixFile >> aLine;										// continuation read
		
	}
	system("pause");
	return 0;
}

// This function determines the precedence of the symbol
int precedence(char symbol)
{
	if(symbol == '+' || symbol == '-')
		return 1;
	else if(symbol == '*' || symbol == '/')
		return 2;
	else
		return -1;
}

// Specification file for the generic stack class
// The variable "ItemType" is replaced with the chosen
// data type for the stack.

template <class ItemType>
class StackType
{
private:
    ItemType *stackArray;
    int stackSize;
    int top;

public:
    StackType(int);
    ~StackType();
    void push(ItemType);
    ItemType pop();
	ItemType getTop();
    void clear();
    bool isFull();
    bool isEmpty();

};
    
// Implementation file for the generic stack class
#include <iostream>
using namespace std;

//*******************
// Constructor      *
//*******************

template <class ItemType>
StackType<ItemType>::StackType(int size)
{
    stackArray = new ItemType[size]; 
    stackSize = size; 
    top = -1;
}

//*******************
// Destructor       *
//*******************

template <class ItemType>
StackType<ItemType>::~StackType()
{
    delete [] stackArray;
}


//*************************************************
// Member function push pushes the argument onto  *
// the stack.                                     *
// PRECONDITION: Stack is NOT FULL                *
//*************************************************

template <class ItemType>
void StackType<ItemType>::push(ItemType item)
{
    top++;
    stackArray[top] = item;
}

//****************************************************
// Member function pop pops the value at the top     *
// of the stack off, and copies it into the variable *
// passed as an argument.                            *
// PRECONDITION: Stack is NOT EMPTY                  *
//****************************************************

template <class ItemType>
ItemType StackType<ItemType>::pop()
{
    ItemType item = stackArray[top];
    top--;
    
    return item;
}

//****************************************************
// Member function clear "empties" the stack by      *
// altering the "top" pointer index                  *
//****************************************************

template <class ItemType>
void StackType<ItemType>::clear()
{
    top = -1;
}

//***************************************************
// Member function isFull returns true if the stack *
// is full, or false otherwise.                     *
//***************************************************

template <class ItemType>
bool StackType<ItemType>::isFull()
{
    bool status;

    if (top == stackSize - 1)
        status = true;
    else
        status = false;

    return status;
}

//****************************************************
// Member function isEmpty returns true if the stack *
// is empty, or false otherwise.                     *
//****************************************************

template <class ItemType>
bool StackType<ItemType>::isEmpty()
{
    bool status;

    if (top == -1)
        status = true;
    else 
        status = false;

    return status;
}

//****************************************************
// Member function get top loos at the value at the top     *
// of the stack off, and copies it into the variable 		*
// passed as an argument.                            		*
// PRECONDITION: Stack is NOT EMPTY                 	    *
//****************************************************

template <class ItemType>
ItemType StackType<ItemType>::getTop()
{
    ItemType item = stackArray[top];
    
    return item;
}

This post has been edited by jessicalegner: 29 March 2010 - 03:50 PM


Is This A Good Question/Topic? 0
  • +

Replies To: infix to postfix conversion

#2 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: infix to postfix conversion

Posted 29 March 2010 - 09:50 PM

I guess the reason for taking a programming class is to learn programming, and to really learn programming entails learning how various data structures work -- not just how to use them but also how to implement them. I think that is enough to justify writing your own stack.

As for putting the infix-postfix conversion in a class, that does sound like a stretch. Maybe your professor wanted to have you practice encapsulating code in the form of a class and just didn't come up with a perfect idea for the assignment. Since classes are about object-oriented programming, the first question I would ask is "what is the object that I'm modeling?" In this case, the thing you are modeling isn't a stack -- your class object will not BE a stack, it will HAVE a stack, because a stack is a generic type of data structure. But I guess you just have to go with the flow and program an "Expression Converter" class, with, say, two strings (one to hold an infix expression and the other to hold the equivalent postfix expression), a stack to use in the conversion processing, functions to do the conversions infix->postfix and postfix->infix, a function to handle input, and a function to handle output. If you think about it that way it's not completely far-fetched.
Was This Post Helpful? 1
  • +
  • -

#3 jessicalegner  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 1
  • View blog
  • Posts: 66
  • Joined: 05-June 09

Re: infix to postfix conversion

Posted 30 March 2010 - 08:11 PM

I understand that using my own stack will help me learn programming. I guess my question was does it have other benefits as far as functionality, efficiency over the built in stack.
Was This Post Helpful? 0
  • +
  • -

#4 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: infix to postfix conversion

Posted 30 March 2010 - 10:18 PM

Nope. There are tradeoffs. Your code will occupy less memory, but the STL stack dynamically resizes itself whereas yours doesn't. Neither of those factors are likely to be important in this instance. As a practical matter, a programmer should generally use the built-in library functions since those are thoroughly tested and optimized. On the other hand, if you were writing a program to run on a small embedded device where minimizing the program's memory requirement is important, you might reach a different conclusion.

This post has been edited by r.stiltskin: 30 March 2010 - 10:18 PM

Was This Post Helpful? 2
  • +
  • -

#5 jessicalegner  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 1
  • View blog
  • Posts: 66
  • Joined: 05-June 09

Re: infix to postfix conversion

Posted 31 March 2010 - 09:13 AM

Thank you. That information was quite helpful!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1