Any Boolean Expression to Sum of Minterms

Please support our C++ advertiser: Intel Parallel Studio Home
Reply

Join Date: Apr 2004
Posts: 353
Reputation: Asif_NSU is on a distinguished road 
Solved Threads: 2
Asif_NSU's Avatar
Asif_NSU Asif_NSU is offline Offline
Posting Whiz

Any Boolean Expression to Sum of Minterms

 
0
  #1
Mar 4th, 2005
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:
  1. void topostfix(char *infix,Queue<char> &post)
  2. {
  3. Stack<char> inter;
  4. char last = 0;
  5. char temp;
  6. for(; *infix; ++infix)
  7. {
  8. if (precedence(*infix, 1) > precedence(last,2))
  9. {
  10. inter.Push(last = *infix);
  11. if((temp = *(++infix)) == '\'')
  12. post.Append(temp);
  13. else
  14. --infix;
  15. }
  16.  
  17. else if(precedence(*infix,1) <= precedence(last,2))
  18. {
  19. while(!inter.isEmpty())
  20. {
  21. if(precedence(temp = inter.Pop(),1) >= precedence(*infix,1))
  22. {
  23. if(temp != '(' && temp != ')')
  24. post.Append(temp);
  25. }
  26. else
  27. {
  28. if(temp != '(' && temp != ')')
  29. inter.Push(last = temp);
  30. break;
  31. }
  32. }
  33. if (*infix != '(' && *infix != ')')
  34. inter.Push(last = *infix);
  35. }
  36. }
  37. while(!inter.isEmpty())
  38. post.Append(inter.Pop());
  39.  
  40.  
  41. post.Print();
  42. }
  43.  
  44. int precedence(char token, int type)
  45. {
  46. if((token >= 'A' && token <= 'Z') || (token >= '1' && token <= '9'))
  47. return 9;
  48. else if ( token == '*' || token == ' ')
  49. return 4;
  50. else if ( token == '+')
  51. return 3;
  52. else if ( token == '(')
  53. return (type == 1? 9: 2);
  54. else if (token == ')')
  55. return (type == 1? 2: 9);
  56. else
  57. return 0;
  58. }

and also this function to prouduce a minterm:
  1. void minterm(int nmin,int nvar, Queue<char> &q)
  2. {
  3.  
  4. unsigned int mask = 1 << (nvar -1);
  5. int i;
  6.  
  7.  
  8. for(i = 0; i < nvar; ++i, mask >>= 1)
  9. {
  10.  
  11. if ((nmin & mask) == 0)
  12. {
  13. q.Append('A' + i);
  14. q.Append('\'');
  15. }
  16.  
  17. else
  18. {
  19. q.Append('A' + i);
  20. q.Append(' ');
  21. }
  22. }
  23.  
  24. return;
  25. }

How do I go about defining a function to get the truth-table?
Reply With Quote Quick reply to this message  
Join Date: Sep 2004
Posts: 7,625
Reputation: Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute 
Solved Threads: 714
Team Colleague
Narue's Avatar
Narue Narue is offline Offline
Code Goddess

Re: Any Boolean Expression to Sum of Minterms

 
0
  #2
Mar 4th, 2005
>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.
I'm here to prove you wrong.
Reply With Quote Quick reply to this message  
Join Date: Apr 2004
Posts: 353
Reputation: Asif_NSU is on a distinguished road 
Solved Threads: 2
Asif_NSU's Avatar
Asif_NSU Asif_NSU is offline Offline
Posting Whiz

Re: Any Boolean Expression to Sum of Minterms

 
0
  #3
Mar 5th, 2005
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:
  1. int precedence(char token, int type)
  2. {
  3. if((token >= 'A' && token <= 'Z') || (token >= '1' && token <= '9'))
  4. return 9;
  5. else if ( token == '*' || token == '&')
  6. return 4;
  7. else if ( token == '+' | token == '|')
  8. return 3;
  9. else if ( token == '(')
  10. return (type == 1? 9: 2);
  11. else if (token == ')')
  12. return (type == 1? 2: 9);
  13. else
  14. return 0;
  15. }
To convert infix to postfix:
  1. void topostfix(LinkedList<char> &infix,LinkedList<char> &post)
  2. {
  3. Stack<char> inter;
  4. char last = 0;
  5. char temp;
  6. char item;
  7. for(Node<char> *current = infix.GetFirstNode(); current != NULL; current = current->GetNext())
  8. {
  9. item = current->GetItem();
  10. if( item == '!')
  11. post.InsertatLast(last = item);
  12. else if (precedence(item, 1) > precedence(last,2))
  13. {
  14. inter.Push(last = item);
  15.  
  16. if(current->GetNext() != NULL && (temp = ((current->GetNext())->GetItem())) == '\'')
  17. {
  18. post.InsertatLast(temp);
  19. current = current->GetNext();
  20. }
  21.  
  22. }
  23.  
  24. else if(precedence(current->GetItem(),1) <= precedence(last,2))
  25. {
  26. while(!inter.isEmpty())
  27. {
  28. if(precedence(temp = inter.Pop(),2) >= precedence(current->GetItem(),1))
  29. {
  30. if(temp != '(' && temp != ')')
  31. post.InsertatLast(temp);
  32. }
  33. else
  34. {
  35. if(temp != '(' && temp != ')')
  36. inter.Push(last = temp);
  37. break;
  38. }
  39. }
  40. if (item != '(' && item != ')')
  41. inter.Push(last = item);
  42. }
  43. }
  44. while(!inter.isEmpty())
  45. post.InsertatLast(inter.Pop());
  46.  
  47.  
  48. post.PrintList();
  49. }

Finally the function to evaluate the boolean expression:
  1. int evaluate(LinkedList<char> &post, int combination, int no_var)
  2. {
  3. int mask = 1;
  4. char token;
  5. int temp;
  6. for(Node<char> * walk = post.GetFirstNode(); walk != NULL; walk = walk->GetNext())
  7. {
  8. token = walk->GetItem();
  9. if( token >= '1' && token <= (char)(no_var + '0'))
  10. {
  11. mask <<= (no_var - (token - '0'));
  12. temp = combination & mask;
  13. walk->SetItem(temp == 0? 0 :1);
  14. mask = 1;
  15. }
  16. }
  17. cout<<"\n";
  18. post.PrintList();
  19. cout<<"\n";
  20. Stack<int> result;
  21. for(Node<char> * walk = post.GetFirstNode(); walk != NULL; walk = walk->GetNext())
  22. {
  23. token = walk->GetItem();
  24. if((int)token == 0 || (int)token == 1)
  25. result.Push(token);
  26. else if( ispunct(token))
  27. {
  28. if(token == '\'' || token == '!')
  29. (walk->GetNext())->SetItem((walk->GetItem() == 0? 1: 0));
  30.  
  31. else if(token == '+' || token == '|')
  32. {
  33. temp = result.Pop() | result.Pop();
  34. result.Push(temp);
  35. }
  36.  
  37. else if(token == '*' || token == '&')
  38. {
  39. temp = result.Pop() & result.Pop();
  40. result.Push(temp);
  41. }
  42. }
  43. }
  44.  
  45. return result.Pop();
  46.  
  47. }

What necessary changes shud i make to account for the boolean ! operator?
Reply With Quote Quick reply to this message  
Join Date: Sep 2004
Posts: 7,625
Reputation: Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute 
Solved Threads: 714
Team Colleague
Narue's Avatar
Narue Narue is offline Offline
Code Goddess

Re: Any Boolean Expression to Sum of Minterms

 
0
  #4
Mar 5th, 2005
>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:
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <iterator>
  4. #include <list>
  5. #include <stack>
  6. #include <sstream>
  7. #include <string>
  8.  
  9. using namespace std;
  10.  
  11. int priority(const string& token)
  12. {
  13. if (token == "(")
  14. return 3;
  15. else if (token == "!")
  16. return 2;
  17. else if (token == "+")
  18. return 1;
  19. else
  20. return 0;
  21. }
  22.  
  23. list<string> infix_to_postfix(const list<string>& infix)
  24. {
  25. list<string> result;
  26. stack<string> save;
  27.  
  28. for (list<string>::const_iterator it = infix.begin(); it != infix.end(); ++it) {
  29. if (isdigit((*it)[0]) || isalpha((*it)[0])) { // Operand
  30. result.push_back(*it);
  31. } else if (*it == ")") { // Nested expression
  32. while (true) {
  33. string item = save.top(); save.pop();
  34.  
  35. if (item == "(")
  36. break;
  37.  
  38. result.push_back(item);
  39. }
  40. } else { // Operator
  41. while (!save.empty() && priority(save.top()) > priority(*it)) {
  42. if (save.top() == "(" && *it != ")") // Don't pop paren unless handling paren
  43. break;
  44.  
  45. result.push_back(save.top()); save.pop();
  46. }
  47.  
  48. save.push(*it);
  49. }
  50. }
  51.  
  52. while (!save.empty()) { // Finish up
  53. result.push_back(save.top()); save.pop();
  54. }
  55.  
  56. return result;
  57. }
  58.  
  59. void process(const string& expr)
  60. {
  61. list<string> infix;
  62.  
  63. istringstream in(expr);
  64. copy(istream_iterator<string>(in), istream_iterator<string>(), back_inserter(infix));
  65.  
  66. list<string> postfix = infix_to_postfix(infix);
  67. copy(postfix.begin(), postfix.end(), ostream_iterator<string>(cout, " "));
  68. cout<<endl;
  69. }
  70.  
  71. int main()
  72. {
  73. process("! ( A + B )");
  74. process("! A + ! B");
  75. }
I'm here to prove you wrong.
Reply With Quote Quick reply to this message  
Join Date: Apr 2004
Posts: 353
Reputation: Asif_NSU is on a distinguished road 
Solved Threads: 2
Asif_NSU's Avatar
Asif_NSU Asif_NSU is offline Offline
Posting Whiz

Re: Any Boolean Expression to Sum of Minterms

 
0
  #5
Mar 5th, 2005
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?
Reply With Quote Quick reply to this message  
Join Date: Sep 2004
Posts: 7,625
Reputation: Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute 
Solved Threads: 714
Team Colleague
Narue's Avatar
Narue Narue is offline Offline
Code Goddess

Re: Any Boolean Expression to Sum of Minterms

 
0
  #6
Mar 5th, 2005
>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.
I'm here to prove you wrong.
Reply With Quote Quick reply to this message  
Join Date: Apr 2004
Posts: 353
Reputation: Asif_NSU is on a distinguished road 
Solved Threads: 2
Asif_NSU's Avatar
Asif_NSU Asif_NSU is offline Offline
Posting Whiz

Re: Any Boolean Expression to Sum of Minterms

 
0
  #7
Mar 5th, 2005
>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".
Reply With Quote Quick reply to this message  
Reply

This thread is more than three months old.
Perhaps start a new thread instead?
Message:



Similar Threads
Other Threads in the C++ Forum
Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC