Calculating the truth value of a statement

Question

I have been struggling for days to solve this problem:

I have to write a recursive code that calculates the truth value of a statement (I can also use loops in the function);

Connectors: "&" (and) and "|" (or)
values: 1 and 0
The function must return either "1" or "0"

For instance -

For the statement 1 the function must return 1
For the statement 0 the function must return 0
For the statement (1&1) the function must return 1
For the statement (0|1) the function must return 1

So basically 0 & 0\1 = 0 , 1 | 1\0 = 1

And for more complex statements

(1&(1|0)) ; (1|0) is 1, so it is (1&1) which is 1
((1|0)&(0&1)) ; (1|0) = 1, (0&1) = 0 --> (1&0)=0

(The statement is defined as a string)

int st_value (char statement[], int length, int i) /* this can be changed*/
{
if (length == 1)
  return statement[0];
if (statement[i]=='(' && statement[length-1]==')')
            return st_val(statement, length--, i++);
else if (statement[i]=='(')
            return st_val(statement, length, i++);
if (statement[i]=='0' || statement[i]=='1')
   {
     if (a[i+1] == '|')
         return st_val(statement, length, i+2);
   .....
   }
if (statement[i]=='&')
.....
}

If I have to follow this, the code would be way too long and would have many holes, like when some part of the code returns 0...

Presumably `st_val` is actually `st_value` in the code snippet, i.e. a recursive call? Several obvious problems: 1) `if (length == 1) return statement[0]` seems wrong, I doubt you want to return the value of the last character (possibly a parenthesis?) from the function. 2) `return st_val(statement, length--, i++);` does nothing since `x--` and `x++` are postfix. — vgru, Apr 26 '19 at 08:15
Possible duplicate of [c expression Evaluator](https://stackoverflow.com/questions/1465909/c-expression-evaluator) — vgru, Apr 26 '19 at 08:21
"For the statement (0|1) the function must return 0" Eeh? What is | supposed to be if not OR? How does any of this make sense? — Lundin, Apr 26 '19 at 08:30
My bad, I just changed val to value for you to understand the purpose. (0|1) also must return 1. — prism, Apr 26 '19 at 08:31
Anyway, what you need to do here is to build up an ADT which is an expression parse tree, each operator has two operands, where an operand could be another operator for nested expressions. It is similar to a binary tree. You can go through it using recursion but like for any binary tree that isn't necessary, if you make nodes with a `parent` pointer. Which is a good idea, since skipping recursion means faster code and less severe bugs. — Lundin, Apr 26 '19 at 08:35
The problem is, pointers, structs and tress are not allowed in writing the function. — prism, Apr 26 '19 at 08:38
Hasn't a very similar question been asked a couple of days by someone else? — Jabberwocky, Apr 26 '19 at 09:00
Avoiding the issue: Is infix notation a prerequisite? Prefix notation is much simpler to parse... — Andreas, Apr 26 '19 at 10:48

kiran Biradar · Accepted Answer · 2019-04-26T11:22:08.483

The problem is, pointers, structs and tress are not allowed in writing the function.

Considering your above constraint.

Below code solves the expression by treating each (exp) as separate expression and finally combine the result.

int parse(char str[])
{

  int i = 0;
  int value = 0;

  for (i = 0; str[i]; i++)
  {
     if (str[i] == '&')
     {
         i++;
         if (str[i] == '('){
              value = value && parse(&str[i+1]);
              int brackCount = 1;
              while(brackCount)
             {
                 if (str[i] == '(') brackCount++;
                 else if (str[i] == ')') brackCount--;
                 i++;
              }
              i--;
         }
         else {
             value = value && (str[i]-'0');
         }
     }
     else if (str[i] == '|')
     {
         i++;
         if (str[i] == '('){
              value = value || parse(&str[i+1]);
              int brackCount = 1;
              while(brackCount)
             {
                 if (str[i] == '(') brackCount++;
                 else if (str[i] == ')') brackCount--;
                 i++;
              }
              i--;
         }
         else {
             value = value || (str[i]-'0');
         }
     }
     else if (str[i] == '(') {
          i++;
          value = parse(&str[i]);

          int brackCount = 1;
          while(brackCount)
          {
             if (str[i] == '(') brackCount++;
             else if (str[i] == ')') brackCount--;

             i++;
          }
          i--;
     }
     else if (str[i] == ')')
     {
       return value;
     }
     else value = str[i]-'0';
  }

  return value;
}

Note: I have used naive approach try to refactor it.

Calculating the truth value of a statement

1 Answers1