Thread: problems on postfix conversion

i have a problem on converting infix to postfix evaluation and appending the characters in the string if the character is a digit

Code:

#include <iostream.h>
#include "D:/turboc/bin/stack.h"
#include <conio.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
void main()
{
   clrscr();
   Stack *stack=new Stack(100);
   char x[100] ;
   cout<<"Input Equation: ";
   gets(x);
   char dest[100];
   for(int i=0;i<strlen(x);i++)
   {

	if(isdigit(x[i]))
	{
		cout<<x[i]; //this must append from the string dest

	}
	else if((x[i]=='+')||(x[i]=='-')||(x[i]=='*')||(x[i]=='/'))
	{
		stack->push(x[i]);
	}
	else if(x[i]==')')
	{
		cout<<stack->pop(); //this must append from the string dest
	}



   }
   cout<<"\n\nPress any key to exit";
    getch();

}

the string dest used in evaluation of a postfix

Code:

evaluate(dest);

if i input as 2(3+6) the result instead of 236+*, it becomes 236+. the first result applies if the input is (2*(3+6)). which lines of code should be edited and why? and how to append a character array and a character popped from the stack into the string? and also, can this code worked with longer equations?why?


I HOPE you will find the way to correct that problem......

NOTE:files attached below are .txt files containing c/c++ codes and it should be runnable in TurboC

1) Don't use Turbo C/C++.
2) Use int main (http://cpwiki.sourceforge.net/Void_main)
3) Never ever use gets, use fgets for C (http://cpwiki.sourceforge.net/buffer_overrun) and std::getline and std::string for C++.
4) You allocate the stack on the heap when totally unnecessary plus you never delete it.

Perhaps you should start with correcting the problems in the code.

Code:

#include <iostream.h>
#include "D:/turboc/bin/stack.h"
#include <conio.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
int main()
{
   clrscr();
   Stack *stack=new Stack(100);
   char x[100] ;
   cout<<"Input Equation: ";
   fgets(x);
   char dest[100];
   for(int i=0;i<strlen(x);i++)
   {

	if(isdigit(x[i]))
	{
		cout<<x[i]; //this must append from the string dest

	}
	else if((x[i]=='+')||(x[i]=='-')||(x[i]=='*')||(x[i]=='/'))
	{
		stack->push(x[i]);
	}
	else if(x[i]==')')
	{
		cout<<stack->pop(); //this must append from the string dest
	}



   }
   cout<<"\n\nPress any key to exit";
    getch();
   return 0;

}

is this code clear?

Originally Posted by blacksnake

Code:

#include "D:/turboc/bin/stack.h" // Get rid of Turbo C
#include <conio.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
int main()
{
   clrscr(); // Avoid if possible, non-standard
   Stack *stack=new Stack(100); // Get rid of new
   char x[100] ;
   cout<<"Input Equation: ";
   fgets(x); // Use std::getline instead
   char dest[100];
   for(int i=0;i<strlen(x);i++)
   {

	if(isdigit(x[i]))
	{
		cout<<x[i]; //this must append from the string dest

	}
	else if((x[i]=='+')||(x[i]=='-')||(x[i]=='*')||(x[i]=='/'))
	{
		stack->push(x[i]);
	}
	else if(x[i]==')')
	{
		cout<<stack->pop(); //this must append from the string dest
	}



   }
   cout<<"\n\nPress any key to exit";
    getch(); // Avoid if possible
   return 0;

}

is this code clear?

Comments are in red.
But you also mention an evaluation function. Do you have one? The current code just prints out numbers.

Code:

#include <string>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <stack>
using namespace std;

int main()
{
   
   stack<char> stk;
   char x[100] ;
   cout<<"Input Equation: ";
   getline(cin,x);
   for(int i=0;i<strlen(x);i++)
   {

	if(isdigit(x[i]))
	{
		cout<<x[i]; //this must append from the string dest

	}
	else if((x[i]=='+')||(x[i]=='-')||(x[i]=='*')||(x[i]=='/'))
	{
		stk.push(x[i]);
	}
	else if(x[i]==')')
	{
		cout<<stk.pop(); //this must append from the string dest
	}



   }
   cout<<"\n\nPress any key to exit";

   return 0;

}

Code:

char x[100] ;

Should be

Code:

string x;

Otherwise it shouldn't compile.

Code:

#include <string>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <stack>
using namespace std;

int main()
{
   
   stack<char> stk;
   string x;
   cout<<"Input Equation: ";
   getline(cin,x);
   for(int i=0;i<x.length();i++)
   {

	if(isdigit(x[i]))
	{
		dest+=x[i];

	}
	else if((x[i]=='+')||(x[i]=='-')||(x[i]=='*')||(x[i]=='/'))
	{
		stk.push(x[i]);
	}
	else if(x[i]==')')
	{
		dest+=stk.pop(); 
	}



   }

   cout<<"The Prefix value is: "<<dest;
   cout<<"\n\nPress any key to exit";

   return 0;

}

"dest" is undefined. I believe you want it defined as a std::string, though.

Code:

#include <string>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <stack>
using namespace std;

int main()
{
   
   stack<char> stk;
   string x, dest;
   cout<<"Input Equation: ";
   getline(cin,x);
   for(int i=0;i<x.length();i++)
   {

	if(isdigit(x[i]))
	{
		dest+=x[i];

	}
	else if((x[i]=='+')||(x[i]=='-')||(x[i]=='*')||(x[i]=='/'))
	{
		stk.push(x[i]);
	}
	else if(x[i]==')')
	{
		dest+=stk.pop(); 
	}



   }

   cout<<"The Prefix value is: "<<dest;
   cout<<"\n\nPress any key to exit";

   return 0;

}

Your code doesn't seem to handle the opening bracket at all. Are you sure, though, that you want to allow expressions such as 2(3+4) instead of requiring typing all operators explicitly?

Neither does your code appear to handle operator precedence.

I suggest reading about the shunting yard algorithm.

Originally Posted by chottachatri

hello blacky,
i may be wrong but as far as i know the algorithm itself is wrong.You are popping the stack only when you encounter ")" which is entirely wrong

Here's the algorithm that may help you..

1) if you encounter "(" push on it on stack
2) if you encounter operators (+,-,*,/) then compare the operators with the top of the stack.As long as the top of the stack has operators with higher or equal priority to the scanned operators you have to keep popping the stack and store it in result

Lastly you have to push the scanned operator on the stack

3)If you encounter any digits or alphabets then store in in result

4)if you encounter ")" keep popping the stack unless you encounter "(" on the stack and store it in result

Lastly decrement top by 1 as "(" is of no importance to us

These are the four steps you have to follow.Now follow this and try to do it. If you still face difficulty then tell me i will give you the working code for it

-Chotti

can you prove about the 2nd step in this kind of algorithm
?

i was understood on appending the integers the problem was a precedence...can u show the code to me on the precedence of operators?