Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Converting infix to postfix

Posted on 2011-03-07
3
Medium Priority
?
675 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
3 Comments
 
LVL 46

Accepted Solution

by:
Kent Olsen earned 2000 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 Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
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…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

610 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