#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;
}

~.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 ; }

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)

#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;
}