void topostfix(char *infix,Queue<char> &post)
{
	Stack<char> inter;
	char last = 0;
	char temp;
	for(; *infix; ++infix)
	{
		if (precedence(*infix, 1) > precedence(last,2))
		{
			inter.Push(last = *infix);
			if((temp = *(++infix)) == '\'')
				post.Append(temp);
			else
				--infix;
		}
			
		else if(precedence(*infix,1) <= precedence(last,2))
		{
			while(!inter.isEmpty())
			{
				if(precedence(temp = inter.Pop(),1) >= precedence(*infix,1))
				{
					if(temp != '(' && temp != ')')
						post.Append(temp);
				}
				else
				{
					if(temp != '(' && temp != ')')
							inter.Push(last = temp);
					break;
				}
			}
			if (*infix != '(' && *infix != ')')
				inter.Push(last = *infix);
		}
	}
	while(!inter.isEmpty())
		post.Append(inter.Pop());
	
	
	post.Print();
}

int precedence(char token, int type)
{
	if((token >= 'A' && token <= 'Z') || (token >= '1' && token <= '9'))
		return 9;
	else if ( token == '*' || token == ' ')
		return 4;
	else if ( token == '+')
		return 3;
	else if ( token == '(')
		return (type == 1? 9: 2);
	else if (token == ')')
		return (type == 1? 2: 9);
	else 
		return 0;
}

void minterm(int nmin,int nvar, Queue<char> &q)
{
	
	unsigned int mask = 1 << (nvar -1);
	int i;
	
	
	for(i = 0; i < nvar; ++i, mask >>= 1)
	{
		
		if ((nmin & mask) == 0)
		{
			q.Append('A' + i);
			q.Append('\'');
		}
		
		else
		{
			q.Append('A' + i);
			q.Append(' ');
		}
	}
		
	return;
}

int precedence(char token, int type)
{
 if((token >= 'A' && token <= 'Z') || (token >= '1' && token <= '9'))
  return 9;
 else if ( token == '*' || token == '&')
  return 4;
 else if ( token == '+' | token == '|')
  return 3;
 else if ( token == '(')
  return (type == 1? 9: 2);
 else if (token == ')')
  return (type == 1? 2: 9);
 else 
  return 0;
}

void topostfix(LinkedList<char> &infix,LinkedList<char> &post)
{
Stack<char> inter;
char last = 0;
char temp;
char item;
for(Node<char> *current = infix.GetFirstNode(); current != NULL; current = current->GetNext())
{
item = current->GetItem();
if( item == '!')
post.InsertatLast(last = item);
else if (precedence(item, 1) > precedence(last,2))
{
inter.Push(last = item);
 
if(current->GetNext() != NULL && (temp = ((current->GetNext())->GetItem())) == '\'')
{
	post.InsertatLast(temp);
	current = current->GetNext();
}
 
}
 
else if(precedence(current->GetItem(),1) <= precedence(last,2))
{
while(!inter.isEmpty())
{
	if(precedence(temp = inter.Pop(),2) >= precedence(current->GetItem(),1))
	{
	 if(temp != '(' && temp != ')')
	 post.InsertatLast(temp);
	}
	else
	{
	 if(temp != '(' && temp != ')')
	 inter.Push(last = temp);
	 break;
	}
}
if (item != '(' && item != ')')
	inter.Push(last = item);
}
}
while(!inter.isEmpty())
post.InsertatLast(inter.Pop());
 
 
post.PrintList();
}

int evaluate(LinkedList<char> &post, int combination, int no_var)
{
int mask = 1;
char token;
int temp;
for(Node<char> * walk = post.GetFirstNode(); walk != NULL; walk = walk->GetNext())
{
token = walk->GetItem();
if( token >= '1' && token <= (char)(no_var + '0'))
{
mask <<= (no_var - (token - '0'));
temp = combination & mask;
walk->SetItem(temp == 0? 0 :1);
mask = 1;
}
}
cout<<"\n";
post.PrintList();
cout<<"\n";
Stack<int> result;
for(Node<char> * walk = post.GetFirstNode(); walk != NULL; walk = walk->GetNext())
{
token = walk->GetItem();
if((int)token == 0 || (int)token == 1)
result.Push(token);
else if( ispunct(token))
{
if(token == '\'' || token == '!')
	(walk->GetNext())->SetItem((walk->GetItem() == 0? 1: 0));
 
else if(token == '+' || token == '|')
{
	temp = result.Pop() | result.Pop();
	result.Push(temp);
}
 
else if(token == '*' || token == '&')
{
	temp = result.Pop() & result.Pop();
	result.Push(temp);
}
}
}
 
return result.Pop();
 
}

#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <stack>
#include <sstream>
#include <string>

using namespace std;

int priority(const string& token)
{
  if (token == "(")
    return 3;
  else if (token == "!")
    return 2;
  else if (token == "+")
    return 1;
  else
    return 0;
}

list<string> infix_to_postfix(const list<string>& infix)
{
  list<string> result;
  stack<string> save;

  for (list<string>::const_iterator it = infix.begin(); it != infix.end(); ++it) {
    if (isdigit((*it)[0]) || isalpha((*it)[0])) { // Operand
      result.push_back(*it);
    } else if (*it == ")") {                      // Nested expression
      while (true) {
        string item = save.top(); save.pop();

        if (item == "(")
          break;

        result.push_back(item);
      }
    } else {                                      // Operator
      while (!save.empty() && priority(save.top()) > priority(*it)) {
        if (save.top() == "(" && *it != ")")      // Don't pop paren unless handling paren
          break;

        result.push_back(save.top()); save.pop();
      }

      save.push(*it);
    }
  }

  while (!save.empty()) {                         // Finish up
    result.push_back(save.top()); save.pop();
  }

  return result;
}

void process(const string& expr)
{
  list<string> infix;

  istringstream in(expr);
  copy(istream_iterator<string>(in), istream_iterator<string>(), back_inserter(infix));

  list<string> postfix = infix_to_postfix(infix);
  copy(postfix.begin(), postfix.end(), ostream_iterator<string>(cout, " "));
  cout<<endl;
}

int main()
{
  process("! ( A + B )");
  process("! A + ! B");
}