Solved

Converting infix to postfix

Posted on 2011-03-07
3
630 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

Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

760 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

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now