Solved

Converting infix to postfix

Posted on 2011-03-07
3
640 Views
Last Modified: 2012-05-11
Hello Everyone,

I am writing a program that will let a user enter in an equation and the program will change it to a postfix equation.  The program works fine until I enter over 7 different variables in the equation (Including parenthesis) .  When I enter over 7 characters the last few characters are not getting placed into the postfix_Equation vector which will holds the postfix equation. For example,

Please Enter In A Equation
( a + b ) * ( c / d ) + f
 a(b)+c(*d/

The + and f is not displaying in the postfix equation.  Also, I cannot get the parenthesis to not be stored into the vector.  The following line in main is not effective
while(!operator_Stack->isEmpty() && isHigh(tokenPtr, operator_Stack->top()))
                                          {
                                                if(operator_Stack->top() != '(' || operator_Stack->top() != ')' )
                                                      {
                                                            postfix_Equations.push_back(operator_Stack->topAndPop());
                                                      }

                                                else
                                                      continue;

Main.cpp
 
#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<iterator>
#include<vector>
#include<algorithm>

using namespace std;

#include"StackLi.h"

#include"BinaryNode.h"


bool isHigh(char *oper, char stck)
{
// Checks if operaotr just read in is of higher or equal presedence
// than the operator next on the stack


	if ((*oper == '+') || (*oper == '-'))
	{
		if ((stck == '+') || (stck == '-'))
			return true;
	}	
	
	else if((*oper == '+') || (*oper == '-'))
	{
		if ((stck == '*') || (stck == '/'))
			return true;
	}	

	else if ((*oper == '*') || (*oper == '/'))
	{
		if ((stck == '*') || (stck == '/'))
			return true;
	}

	else if((*oper == '*') || (*oper == '/'))
	{
		if ((stck == '+') || (stck == '-'))
			return false;
	}

	else if((*oper == ')'))
	{
		if((stck == '(')) 
			return true;
		else
			return false;
	}
	

}


int main()
{
	Stack<char> * operator_Stack = new Stack<char>;

	Stack<BinaryNode<char>*> * ptrStack = new Stack<BinaryNode<char>*>;
	

   char equation[20];
   char* tokenPtr;
   
   vector<char> postfix_Equations(1, 0);
   
   cout<<"Please Enter In A Equation"<<endl;

   cin.getline(equation, sizeof(equation), '\n');//To catch all of the char p
   
   tokenPtr = strtok(equation," ");

   
   
   
   while(tokenPtr != NULL)
   {
	    if( *tokenPtr == '+' || *tokenPtr=='-' || *tokenPtr == '/' || *tokenPtr == '*' || *tokenPtr == '^' || *tokenPtr == ')')
			   {
				   if(!operator_Stack->isEmpty())
				   {
					   while(!operator_Stack->isEmpty() && isHigh(tokenPtr, operator_Stack->top()))
							{
								if(operator_Stack->top() != '(' || operator_Stack->top() != ')' )
									{
										postfix_Equations.push_back(operator_Stack->topAndPop());
									}

								else
									continue;
									
									
							}

					   operator_Stack->push(*tokenPtr);
				   }

				   else
					   postfix_Equations.push_back(*tokenPtr);

				  
				}

		else if (*tokenPtr == '(')
			operator_Stack->push(*tokenPtr);

		else if(isalpha(*tokenPtr) || isalnum(*tokenPtr))
			postfix_Equations.push_back(*tokenPtr);
			   
				
			    tokenPtr = strtok(NULL, " ");
   }

   if(!operator_Stack->isEmpty())
   {
	   while(!operator_Stack->isEmpty())
		   postfix_Equations.push_back(operator_Stack->topAndPop());
   }


   for(int i =0; i!= postfix_Equations.size(); i++)
	   cout<<postfix_Equations[i];

   cout<<"\n"<<endl;

system("PAUSE");

	return 0;
}

Open in new window


Stack.h
 
#ifndef STACKLI_H_
#define STACKLI_H_

#include <stdlib.h>
#include<exception>

using namespace std;

#include"BinaryNode.h"
//#include "Except.h"


// Stack class -- linked list implementation.
//
// CONSTRUCTION: with no parameters.
//
// ******************PUBLIC OPERATIONS*********************
// void push( x )        --> Insert x
// void pop( )           --> Remove most recently inserted item
// Object top( )         --> Return most recently inserted item
// Object topAndPop( )   --> Return and remove most recently inserted item
// bool isEmpty( )       --> Return true if empty; else false
// void makeEmpty( )     --> Remove all items
// ******************ERRORS********************************
// UnderflowException thrown as needed.

template <class Object>
class Stack
{
  public:
    Stack( );
    Stack( const Stack & );
    ~Stack( );

    bool isEmpty( ) const;
    const Object & top( ) const;
    void makeEmpty( );
    void pop( );
    void push( const Object & );
    Object topAndPop( );

    const Stack & operator=( const Stack & );

  private:
    struct ListNode
    {
        Object    element;
        ListNode *next;

        ListNode( const Object & theElement, ListNode * n = NULL )
          : element( theElement ), next( n ) { }
    };

    ListNode *topOfStack;
};

//#include "StackLi.cpp"


// Construct the stack.
template <class Object>
Stack<Object>::Stack( )
{
    topOfStack = NULL;
}

// Copy constructor.
template <class Object>
Stack<Object>::Stack( const Stack<Object> & rhs )
{
    topOfStack = NULL;
    *this = rhs;
}


template<>
Stack<BinaryNode<char>*>::Stack()
{
	topOfStack = NULL;

}

// Destructor.
template <class Object>
Stack<Object>::~Stack( )
{
    makeEmpty( );
}

// Test if the stack is logically empty.
// Return true if empty, false, otherwise.
template <class Object>
bool Stack<Object>::isEmpty( ) const
{
    return topOfStack == NULL;
}

// Make the stack logically empty.
template <class Object>
void Stack<Object>::makeEmpty( )
{
    while( !isEmpty( ) )
        pop( );
}

// Return the most recently inserted item in the stack.
// or throw an UnderflowException if empty.
template <class Object>
const Object & Stack<Object>::top( ) const
{
    //if( isEmpty( ) )
        //throw UnderflowException( );
    return topOfStack->element;
}



// Remove the most recently inserted item from the stack.
// Throw Underflow if the stack is empty.
template <class Object>
void Stack<Object>::pop( )
{
   // if( isEmpty( ) )
       // throw UnderflowException( );

    ListNode *oldTop = topOfStack;
    topOfStack = topOfStack->next;
    delete oldTop;
}

// Return and remove the most recently inserted item
// from the stack.
template <class Object>
Object Stack<Object>::topAndPop( )
{
    Object topItem = top( );
    pop( );
    return topItem;
}

// Insert x into the stack.
template <class Object>
void Stack<Object>::push( const Object & x )
{
    topOfStack = new ListNode( x, topOfStack );
}

// Deep copy.
template <class Object>
const Stack<Object> & Stack<Object>::operator=( const Stack<Object> & rhs )
{
    if( this != &rhs )
    {
        makeEmpty( );
        if( rhs.isEmpty( ) )
            return *this;

        ListNode *rptr = rhs.topOfStack;
        ListNode *ptr  = new ListNode( rptr->element );
        topOfStack = ptr;

        for( rptr = rptr->next; rptr != NULL; rptr = rptr->next )
            ptr = ptr->next = new ListNode( rptr->element );
    }
    return *this;
}



#endif

Open in new window


BinaryNode.h
 
#ifndef BINARYNODE_H
#define BINARYNODE_H

template<class object>
class BinaryNode
{
public:
	BinaryNode(object&);
	void in_order(BinaryNode*);
	void pre_order(BinaryNode*);
	void post_order(BinaryNode*);

	object *data;
	BinaryNode *left;
	BinaryNode *right;
};

template<class object>
BinaryNode<object>::BinaryNode(object& node)
{
	data = &node;
	left = NULL;
	right = NULL;

}

template<class object>
void BinaryNode<object>::in_order(BinaryNode *root)
{
	if(root == NULL)
		return;

	in_order(root->left);
	cout<<root->data<<endl;
	in_order(root->right);
	
}

template<class object>
void BinaryNode<object>::post_order(BinaryNode *root)
{
	if(root == NULL)
		return;

	post_order(root->left);
	post_order(root->right);
	cout<<root->data<<endl;

}

template<class object>
void BinaryNode<object>::pre_order(BinaryNode *root)
{
	if(root == NULL)
		return;

	cout<<root->data<<endl;
	pre_order(root->left);
	pre_order(root->right);

}


#endif

Open in new window


Any other suggestion on my order of precedence will be greatly appreciated.
0
Comment
Question by:brich744
3 Comments
 
LVL 45

Accepted Solution

by:
Kdo earned 500 total points
ID: 35060297
Hi Brich,

Are you sure that the problem lies with 7 variables?  It looks like that might be an effect, not the cause.

The main program declares Equation as 20 characters.  That's pretty short.....



Kent
0
 
LVL 16

Expert Comment

by:imladris
ID: 35060381
OK. What you have here is a fairly sizeable piece of code. It is usually best to start simple; at least with testing. You should note, for instance, that the program is not coping with "a + b" correctly yet. Until you have something simple working, there is little point in trying to debug large and complex requirements.

The result for "a + b" is "a+b", which is not postfix notation.

Can you step through the code and see why it is doing that?
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35066990
Kdo is correct. This will help your immediate problem in that you didn't provide enough space for your input:
      char equation[100];
The result is now:
Please Enter In A Equation
( a + b ) * ( c / d ) + f
 a(b)+c(*d)/f+

Open in new window

All of the 8 tokens are now accounted for.

I concur with imladris that there is something wrong with the algorithm, but that is another question.

I think Kdo answered the question of why you are getting incomplete results. BTW, are you sure that you are supposed to have parenthesis in your postfix result? Usually, I don't see them. So, a + b would become a b +    (no parens needed).

BTW, if you use a debugger, this problem would have been immediately clear to you after stepping over line 72 in Main.cpp. In your program sizeof(equation) will evaluate to 20, but you entered 25 chars when you typed: ( a + b ) * ( c / d ) + f
0

Featured Post

Master Your Team's Linux and Cloud Stack

Come see why top tech companies like Mailchimp and Media Temple use Linux Academy to build their employee training programs.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticallā€¦
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to useā€¦
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

803 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question