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");
}