The code below compiles but produces the wrong output. The code is supposed to convert an infix string to postfix. the current output is only the arithmetic operator, unless there are parenthesis then it will only show the right parenthesis. I have been woking on this for hours and am getting nowhere. Please help.

#ifndef H_stackType
#define H_stackType

#include <iostream>
#include <cassert>

using namespace std;

template<class Type>
class stackType
{
public:
	void initializeStack();
	bool isEmptyStack();
	bool isFullStack();
	void push(const Type& newItem);
  	Type top();
	void pop();
	stackType(int stackSize);
	~stackType();

private:
	int maxStackSize;
	int stackTop;
	Type *list;

};

template<class Type>
void stackType<Type>::initializeStack()
{
	stackTop = 0;
}

template<class Type>
bool stackType<Type>::isEmptyStack()
{
	return(stackTop == 0);
}

template<class Type>
bool stackType<Type>::isFullStack()
{
	return(stackTop == maxStackSize);
}

template<class Type>
void stackType<Type>::push(const Type& newItem)
{
 if(!isFullStack())
    {
		list[stackTop] = newItem;
		stackTop++;
    }
    else
		cerr<<"Cannot add to a full stack." << endl;
}

template<class Type>
Type stackType<Type>::top()
{
  assert(stackTop != 0);
  return list[stackTop - 1];
}

template<class Type>
void stackType<Type>::pop()
{
  if(!isEmptyStack())
	   stackTop--;
 	else
	   cerr<<"Cannot remove from an empty stack."<<endl;
}

template<class Type>
stackType<Type>::stackType(int stackSize) 
{
	if(stackSize <= 0)
	{
		cerr<<"Size of the array to hold the stack must "
			<<"be positive."<<endl;
		cerr<<"Creating an array of size 50."<<endl;

		maxStackSize = 50;
	}
	else
		maxStackSize = stackSize;

	stackTop = 0;	
	list = new Type[maxStackSize];
	assert(list != NULL);
}

template<class Type>
stackType<Type>::~stackType()
{
   delete [] list;
}

#endif

#include <iostream>
#include <string>
#include "stackType.h"

using namespace std;

string rpn(string infix);

int main()
{
  string infix;
  
  cout << "NOTE: Enter ! for infix expression to exit." << endl;
  for (;;)
  {
    cout << "Infix Expression?  ";
    getline(cin, infix);
    if (infix == "!") break;
	cout << "RPN Expression is: " << rpn(infix) << endl;
  } 
  return 0;
}

string rpn(string infix)
{
  char stackOpr;
  string RPNexp;
  const string BLANK = " ";
  stackType<char> stack(50);
  stack.initializeStack();
  for (unsigned i = 0; i < infix.length(); i++)
  {
    switch(infix[i])
	{
      case ' ' : break;

      case '(' : stack.push(infix[i]);
                 break;

      case ')' : stackOpr = stack.top();
						stack.pop();
						if(!stack.isEmptyStack())
							{
								stackOpr = stack.top();
								stack.pop();
							}
							else
								break;

      case '+' :  case '-' : 
      case '*' :  case '/' : 
                 for (;;)
                 {
                   if (stack.isEmptyStack() ||
                       stack.top() == '(' ||
                       (infix[i] == '*' || infix[i] == '/') &&
                       (stack.top() == '+' ||  stack.top() == '-')
                      )
                   {
                     stack.push(infix[i]);
                     break;
                   }
                   else
                   {
                     stackOpr = stack.top();
                     stack.pop();
                    }
                 }
                 break;
                 
      default : RPNexp.append(BLANK + stackOpr);
					}
										
			}
	
for (;;)
  {
    if (stack.isEmptyStack()) break;

    stackOpr = stack.top();
    stack.pop();
    if (stackOpr != '(')
    {
      RPNexp.append(BLANK + stackOpr);
    }
    else
    {
      cout << " *** Error in infix expression ***\n";
      break;
    }
  }
  return RPNexp;
}

These things are more easily done using yacc and bison... I have a vague recollection about some statements of implementability of these types of grammar on a stack based machine so I suppose it should be possible... You probably want to save full tokens on the stack instead of just characters thought, thats what you got yacc for but it can easily be done manually thought... Damn it, you don't construct these adlib, try the recursive method first it tends to beasier to think that way, then if you need the stack based solution think about what you use the stack for there (It should result in a proper stack finite state machine, I have seen it somewhere I think)... The proper solution ofcourse would be to construct the finite state machine from the grammar by hand and then write the machine from that (if you have please post) or just use yacc/bison and let it do it for you...

~.l
- { return ADD }
+ { return SUB }
/ { return DIV }
* { return MUL }
( { return LEFT }
) { return RIGHT }
[0-9]\.?[0-9]* { yyval = $1 /* ??? */ ; return NUM ; }
. { }

~.y
// setup code
LINE = EXPR { print( $1 ) ; }
EXPR = EXPR DIV EXPR { $$ = $1 + ' ' + $3 + ' ' + $2 ; } 
 | EXPR MUL EXPR { $$.left = $1 ; $$.op = MUL ; $$.right = $2 ; }
 | TERM { $$ = $1 ; } 
TERM = TERM SUB EXPR { $$ = $1 + ' ' + $3 + ' ' + $2 ; }
TERM = LEFT EXPR RIGHT { $$ = " ( " + $2 + " ) " ; }
TERM = NUM { $$ = $1 ; }

Well my grammar is a little rustly... I usually just run it through till the result is what I would expect (and this has not been tested what so ever)...

This is a homework assignment and since we have never used yacc and bison I do not think I should do that for this assignment. I do thank you for your response though. What I need is to figure out why my alpha characters are not being outputed.

Well it does not output numbers since you dont print them (obviously) currently whenever a number is encountered the switch statement will fall through to the output stackopt statement producing the last encountered stackop instead of the current number...

Well it does not output numbers since you dont print them (obviously) currently whenever a number is encountered the switch statement will fall through to the output stackopt statement producing the last encountered stackop instead of the current number...

so how can i fix this?

Well I have been thinking about this one, I _could_ make a full parser (which would essentially parse the full expression tree and the spit it out after some tinkering)... however this solution you are thinking about may very well work since you only need to move the operator to the back...

practically you can put

case '0': case '1': case '2': case '3': case '4': 
case '5': case '6': case '7': case '8': case '9': 
  // handle numbers here, perhaps like this
  RPNexp.append( infix[i] ) ; 
  // or char buf[2] ; buf[0] = infix[ i ] ; buf[1] = 0 ; RPNexp.append(buf)

As long as you can guarantee the operators come in the right order this _could_ produce correct results (I have yet to figure out a example which would require relocation of number tokens, but that does not mean it does not exist)...

I imagine you have to be explicit about operator precedence
(consider 2+2*2 = 2 (2 2 *) +, but then again I'm not sure I am all into postfix
syntax, 2 2 2 * + might be a valid line aswell, it would still require modification so
that * is put before + when seen next to it in the stack, or so it feels anyway.

*Edit) I believe that is what you are trying to do in your +-*/ case, but it looks a little off... once you get it running thought you should be able to see if it works or not.

Member Avatar for iamthwee

Well I have been thinking about this one, I _could_ make a full parser (which would essentially parse the full expression tree and the spit it out after some tinkering

Yes i wud forget your method. It may not work. if u use an expression tree it will like perniciosus said.

So this is wat i wud do. It can't be that hard to make a tree can it?

:cool:

Thoughts: case ')': Should probably output all ops untill a '(' is found on the stack.
The Big if statement on operators should probably be broken up, empty and '(' cases looks correct, but precedence rules should probably be something like (infix[i] == '+' && stack.top() != '+') for +
since all operators but + has precedence over + and similary for other ones (you need to tell me if I have understood this part of the code right thought).

I dont really get the need to store stackOpr and output it on default, it makes little sence to me (feel free to elaborate).

Yes i wud forget your method. It may not work. if u use an expression tree it will like perniciosus said.

So this is wat i wud do. It can't be that hard to make a tree can it?

Nope, once you've done it it feels like the most natural way to do parsing ;) A shorter step might be to do it recursivly, that is rather intuative, probably the first thing I would have done (before seeing the beauty of syntax trees), let the compiler handle the stack for you... thought since you were using a stack i guessed it was part of the assignment...

Thoughts: case ')': Should probably output all ops untill a '(' is found on the stack.

This is exactly what i am looking to do below is the algorithm for this assignment. I think I am on the right path just a little lost. Please help me figure out tje next step.

Note: Uses a stack to store operators.
1. Initialize an empty stack of operators.
2. While no error has occurred and the end of the infix expression has not been reached, do the following:
a. Get the next input token (constant, variable, arithmetic operator, left parenthesis, right parenthesis) in the infix expression.
b. If token is
i. a left parenthesis: Push it onto the stack.
ii. a right parenthesis: Pop and display stack elements until a left parenthesis is encountered, but do not display it. (It is an error if the stack becomes empty with no left parenthesis found.)
iii. an operator: If the stack is empty or token has a higher priority than the top stack element, push token onto the stack.
Otherwise, pop and display the top stack element: then repeat the comparison of token with the new top stack item.
Note: A left parenthesis in the stack is assumed to have a lower priority than that of operators
iv. an operand: Display it.
3. When the end of the infix expression is reached, pop and display stack items until the stack is empty.

made a few changes now the program outputs in prefix (i need postfix) and crashes if i use parenthesis? can someone look at the code and tell me what i am doing wrong? same .h file posted above

#include <iostream>
#include <string>
#include "stackType.h"

using namespace std;

int precedence (char x );
string rpn(string infix);

int main()
{
  string infix;
  
  cout << "Note: Enter ! for infix expression to exit." << endl;
  for (;;)
  {
    cout << "Infix Expression?  ";
    getline(cin, infix);
    if (infix == "!") break;
	cout << "RPN Expression is: " << rpn(infix) << endl;
  } 
  return 0;
}

int precedence (char x )
{
  switch ( x ) {
    case '+':
    case '-':
	return 1;
    case '*':
    case '/':
	return 2;
  }
  return 0;
}

string rpn(string infix)
{
  string rpnExp;
  stackType<char> stack;
  
  for (unsigned i = 0; i < infix.length(); i++)
  {
    switch(infix[i])
	{
      case ' ' : break;

      case '(' : stack.push(infix[i]);
                 break;

      case ')' : while ( stack.top() != '(' ){
					rpnExp += stack.top();
					stack.pop();
					}
					stack.pop();
					break;
      default :
		  while ( !stack.isEmptyStack() && precedence( infix[i]) <=  precedence( stack.top() ) ){
	    rpnExp += stack.top();
	    stack.pop();
	  } 
	  stack.push( infix[i] );
	}									
}
	
  while ( !stack.isEmptyStack() ) {
			rpnExp += stack.top();
			stack.pop();
		}

 return rpnExp;
}

changed the while to for and no more crashes but still prefix instead of postfix ... any ideas?

case ')' : for ( stack.top() != '(' ){
					rpnExp += stack.top();
					stack.pop();
					}
					stack.pop();
					break;
      default :
		 for ( !stack.isEmptyStack() && precedence( infix[i]) <=  precedence( stack.top() ) ){
	    rpnExp += stack.top();
	    stack.pop();
	  } 
	  stack.push( infix[i] );

Well then, thanks for including algorithm, I had a feeling it could be done but I did not feel like adlibbing it... (I assume it is correct even if it looks a little odd at times, may be smart thinking)...

precedence need to handle '(' , suggestion return 0.

default action should not pop stack... ')' should pop stack like so while( !stack.empty() && stack.top() != '(' ) // out top and pop (I dont even se how the current expression can even compile)
And return error if stack is empty after this loop, else pop and discard '('.

op: should be something like

if( stack.empty() || precedence( stack.top() ) > precedence( infix[ i ] ) )
    stack.push( infix[ i ] ) ;
else {
    // output stack.top() && pop stack
    if( stack.empty() || precedence( stack.top() ) > precedence( infix[ i ] ) )
       stack.push( infix[ i ] ) ;
    // It is not clear what to do if this is not the case, is it suppose to be a loop ?
}

And possible spaces should be output at '(' ops and ')' to hide the fact that no token recognicion is done... (else expression like 2+2 would produce 22+, or worse 10+10 => 1010+ whats the operators then?)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.