Write a program non recursive using stacks The program shoul

Write a program (non recursive) using stacks. The program should evaluate the truth value of a given logical expression consisting of the two truth-value constants, TRUE (T) and FALSE (F), parentheses, and the three common logical operators: ­­­­¬ (NEGATION), (AND), and (OR). For example, (T (F ­­­­¬T) ) v ¬ (F v T T) should evaluate to F. Analyze the running time of your algorithm in terms of the input size n, which in this case is the number of symbols in the logical expression given as the input. Run your program on 3 randomly generated logic expression containing at least 100, 1000 and 10000 symbols to verify your running time analysis result. Assume this operator precedence: ­­(), ¬, , and . , i.e., ¬T v T F should be interpreted as (¬T) v (T F).

Feel free to use common symbols to represent those logical operators as well as the truth-value constants T and F, for the easiness of programming. For example, use 0 for F, 1 for T, and !, *, and + for ­­¬ , , and , in that order.

Solution

I hope that the problem has been given to you after teaching about infix to postfix expression. If not you should get the idea about it. Actually its difficult for computer to evaluate the infix(above expression or normally like 1+2*3+4-5) so first they convert it to postfix then evaluate it to certain value. You might be aware of arithematic operator precendcy similarly you can apply here too. Actually one famous person Dijkstra has developed an algorithm to change infix to postfix using queue. We can modify the algorithm using two stack to get our solution.

Example of infix to postfix -

1+2*3-4+5*6/8 infix

1 2 3 * + 4 - 5 6 * 8 / + postfix

Basically the algorithm is this -

1) If you see any number or here in this case its either 0 or 1 then push it into operandStack

2) if you see right parenthesis then do the following

   2.1) while operatorStack last value is not equal to left parenthesis pop the value of operatorStack.

       2.1.1) if pop value is equal to ¬(negation or uninary operator or here it is !) then pop one value from operandStack and apply   
           to it and push that value again to operandStack. So if it was previously 1 then it will change to 0 and vice versa.

       2.1.2) if pop value is equal to either + or - then pop two value from the operandStack apply | or & and push that value to
               operandStack again.

3) if you see left parenthesis push it into operatorStack
4) if you see any other operator
   4.1) while last value of non empty OperatorStack has higher precedency, pop the value from OperandStack depending on the operator then push again into operandStack after evaluation.

Now while OperatorStack is not empty pop the operands apply the operator value push it again and finally last value of OperandStack is our answer.

Now implementation in C++

#include <iostream>
#include <stack>
#include <typeinfo>
#include <string>
using namespace std;

int findPrecedency(char c){
   switch(c){
       case \'(\':return 5;
       case \')\':return 4;
       case \'!\':return 3;
       case \'-\':return 2;
       default:return 1;
   }
   return -1;// invalid operator
}
int main(){
   //Two important stack
   stack<char> operatorStack;
   stack<int> operandStack;

   char expression[10002];

   cin >> expression;

   for(int i = 0; expression[i] != \'\\0\'; ++i){
       //if left parenthesis push into operator stack
       if(expression[i] == \'(\'){
           operatorStack.push(\'(\');
       }
       // if it is a number push into operand stack
       else if(expression[i] == \'0\' || expression[i] == \'1\'){
           operandStack.push((expression[i] == \'0\')?0:1);
       }
       else if(expression[i] == \')\'){
           while(!operatorStack.empty() && operatorStack.top() != \'(\'){
               char k = operatorStack.top();
               operatorStack.pop();
               if(k == \'!\'){ // pop only one operand
                   int a = operandStack.top();
                   a ^= 1;
                   operandStack.pop();
                   operandStack.push(a);
               }else{
                   int a = operandStack.top();
                   operandStack.pop();
                   int b = operandStack.top();
                   operandStack.pop();

                   if(k == \'+\'){
                       a |= b;
                   }
                   else{
                       a &= b;
                   }
                   operandStack.push(a);// push after the operation
               }
           }
           // now pop the left parenthesis
           operatorStack.pop();
       }
       else{
           while(!operatorStack.empty() && operatorStack.top() != \'(\' &&
               findPrecedency(operatorStack.top()) > findPrecedency(expression[i])){
               char k = operatorStack.top();
               operatorStack.pop();
               if(k == \'!\'){ // pop only one operand
                   int a = operandStack.top();
                   a ^= 1;
                   operandStack.pop();
                   operandStack.push(a);
               }else{
                   int a = operandStack.top();
                   operandStack.pop();
                   int b = operandStack.top();
                   operandStack.pop();

                   if(k == \'+\'){
                       a |= b;
                   }
                   else{
                       a &= b;
                   }
                   operandStack.push(a);// push after the operation
               }
           }
           operatorStack.push(expression[i]);
       }
   }
   //empty the operator stack to get the value
  
   while(!operatorStack.empty()){
       char k = operatorStack.top();
       operatorStack.pop();
       if(k == \'!\'){ // pop only one operand
           int a = operandStack.top();
           a ^= 1;
           operandStack.pop();
           operandStack.push(a);
       }else{
           int a = operandStack.top();
           operandStack.pop();
           int b = operandStack.top();
           operandStack.pop();

           if(k == \'+\'){
               a |= b;
           }
           else{
               a &= b;
           }
           operandStack.push(a);// push after the operation
       }
   }
   cout << operandStack.top() << endl;

   return 0;

}

=> (1-(0+!1))+!(0+1-1)

0

=> (1+1)+!1

1

=> (1-0)+!0

1

Now if you get any doubt regarding that you can ask me.