Any Boolean Expression to Sum of Minterms

[Asif_NSU]

I have to write a program where the input is a Boolean Expression and the ouput is the corresponding sum of minterms for that particular expression.

My idea is that i need to convert the infix boolean expression to a postfix expression. From there I need to construct the truth-table for the function. Once i get the truth-table i can easily get the sum of minterms format.

So far I have wrote the code to convert infix to postfix, and i can print the sum of minterms. I have confusion regarding the construction of the truth-table, i m having so many ideas as how to do it that i dont know which one to follow, and most importantly i dont know if that's the correct way to do it. I was looking for some advice as how to construct the truth-table efficiently from the postfix expression. The idea i currently have is to keep track of the number of variables and run a loop from 0 to 2^(no of variables) -1, and then use bitwise operators to assign each boolean variable itz appropriate values to finally evaluate the expression.

These are the functions i have been working on:

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

and also this function to prouduce a minterm:

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

How do I go about defining a function to get the truth-table?

[Narue]

>i dont know which one to follow
Try them all, starting with the simplest.

>i dont know if that's the correct way to do it
Why? It sounds reasonable enough to me when that's one of the two established ways to find the canonical form of a boolean expression.

>I was looking for some advice as how to construct the truth-table
>efficiently from the postfix expression.
My advice is to get it working first, then make it fast.

>How do I go about defining a function to get the truth-table?
How would you do it on paper? Before you start writing code, make sure that you understand both the problem you're trying to solve, and the solution you came up with. It's important to understand your own solution before you write it, or you'll just end up debugging a broken program into existence.

[Asif_NSU]

well I wrote a function to evaluate the boolean expression for a particular combination of itz variables. So far it works for expressions like !A+!B (or A'+B')
But doesnt work for expressions like this: !(A+B).
Thatz bcos to get the postfix expression i assumed that in the infix expression a ! or ' character will always be followed by a variable.
I guess i need to consider the precedence of unary operator '!' or ' ' ' when converting to postfix. Since in the boolean expression there is only one such unary operator i need to know only itz precedence. Here's my fuctions for precedence, topostfix and evaluate:

the precedence function:

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

To convert infix to postfix:

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

Finally the function to evaluate the boolean expression:

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

What necessary changes shud i make to account for the boolean ! operator?

[Narue]

>i assumed that in the infix expression a ! or ' character will always be followed by a variable.
It has to be followed by a value, yes, not necessarily a variable though. The problem you have is that you aren't treating ! as an operator like you should. You're treating it as a first class token rather than a subset of the operators. Consider this:

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

[Asif_NSU]

Yes, thank you narue. I just did it myself though. I had to take in account the precedence of '!' like other operators. Everything works fine now. The program can evaluate the minterms of a VALID infix expression.

What i want to do now is to check for the validity of the input expression. I think it involves complex parsing techniques, and it alone will probably take more effort than what I have given so far for this program. Would you plz help me with this input error checking?

[Narue]

>I think it involves complex parsing techniques
Eeeeehhh, kind of. If you want, you could set up rules for each operator, but that would require more than simple push/pop access to the stack, and the validation still wouldn't be complete. Your best bet would be a recursive descent parser if you want true validation on the original expression.

A nice, simple alternative is to perform strong error handling while evaluating the expression, but that has a detrimental effect on how well you can report the error.

[Asif_NSU]

>A nice, simple alternative is to perform strong error handling while evaluating >the expression,
When i was writing the code I think i could guess when there could be an error in the original expression. But now i look at my code and i say to myself "Man! i need to take some rest".