Boolean Evaluation

[satsat111]

Hello everyone, I'd like to ask where should I add the brackets into the code.
The code doesn't seem right when implementing input without brackets. I would appreciate anyone's help, thanks in advance.

There is an arithmetic expression consisting of

Variables: A, B, C, D, E
Constants: 0,1
Brackets (, )
Boolean operators: & (and), | (or), ^ (xor)
Given the values assigned for the corresponding variables, please evaluate the expression.

Note that the priority of boolean operators is & > | > ^.

Input:

The first line is the arithmetic expression.

The second line is an integer, T .

The following T lines are T sets of value-assignment for variable A, B, C, D and E.

Constraints
Length of arithmetic expression <=200
The intermediate values during evaluation is 0 or 1 ( it is a boolean expression).
Assigned values for variables are either 0 or 1
Output Format

Output T lines, each line is the result of evaluation for corresponding set of value-assignment.

Sample Input 0

(A|C&E)^1|(B&D)
2
1 0 0 0 1
0 1 0 1 0
Sample Output 0

0
1
Sample Input 1

A|B|C|D|E
32
0 0 0 0 0
1 0 0 0 0
0 1 0 0 0
1 1 0 0 0
0 0 1 0 0
1 0 1 0 0
0 1 1 0 0
1 1 1 0 0
0 0 0 1 0
1 0 0 1 0
0 1 0 1 0
1 1 0 1 0
0 0 1 1 0
1 0 1 1 0
0 1 1 1 0
1 1 1 1 0
0 0 0 0 1
1 0 0 0 1
0 1 0 0 1
1 1 0 0 1
0 0 1 0 1
1 0 1 0 1
0 1 1 0 1
1 1 1 0 1
0 0 0 1 1
1 0 0 1 1
0 1 0 1 1
1 1 0 1 1
0 0 1 1 1
1 0 1 1 1
0 1 1 1 1
1 1 1 1 1
Sample Output 1

0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>
#include <charconv>
#include <string>
#include <cmath>


using namespace std;
 
int evaluateBoolExpr(string s)
{
    int n = s.length();
 
    // Traverse all operands by jumping
    // a character after every iteration.
    for (int i = 0; i < n; i += 2) {
        // If operator next to current operand
        // is AND.
        if (s[i + 1] == '&') {
            if (s[i + 2] == '0'|| s[i] == '0')
                s[i + 2] = '0';
            else
                s[i + 2] = '1';
        }
 
        // If operator next to current operand
        // is OR.
        else if (s[i + 1] == '|') {
            if (s[i + 2] == '1'|| s[i] == '1')
                s[i + 2] = '1';
            else
                s[i + 2] = '0';
        }
 
        // If operator next to current operand
        // is XOR (Assuming a valid input)
        else if (s[i + 1] == '^') {
            if (s[i + 2] == s[i])
                s[i + 2] = '0';
            else
                s[i + 2] = '1';
        }
    }
    return s[n - 1] -'0';
}
 

int main() {
     string str;
    long unsigned t {};
    int arr[5] = {1, 2, 3, 4, 5};

     getline( cin, str);

     cin >> t;

    while (t--) {
         cin >> arr[0] >> arr[1] >> arr[2] >> arr[3] >> arr[4];
         cout <<  evaluateBoolExpr(str) << '\n';
    }
}

[jonnin]

parentheses work just like they would in normal math.
the rule is simply that you treat what is inside them as a single entity.
so
(a & b) | c
is the same as
x | c
... but to do that, ... you need to know what x is.
so you have to evaluate a&b (which is x) first.

the best way to do that, in my eyes, is to use recursion to parse what is inside the parens. that way complex junk with 3, 5, 20 whatever sets of them is handled in sensible chunks.
unfortunately, I don't see a simple way to just poke them into your existing code, because of the nested groups problem. If you don't get nested samples, then you can just put them in directly I think. Do you need to handle ( (a|b)&(b|c))^f or something like that?

[Peter87]

Your way of parsing is unfortunately a bit too simplistic. The assumption that every other character is an operator breaks down with parentheses and you don't take the priority of the operators into account.

The way I would approach this is to start writing a function that parses (and evaluates) the operator with the lowest priority. Inside that function you would call another function that parses the second lowest priority to get the first operand. If the character that follows matches the operator then you parse the second operand by calling the function recursivly and then you calculate the result and return it, otherwise if the character does not match the operator you just return the value you got from the first operand. Parsing always continues from where it last left off, from left-to-right, as if you had a global variable telling you the position to continue parsing. You need to update the position when you "consume" an operator or constant (I have left out this detail in the pseudocodes below).

function parseXor():
  a = parseAnd()
  if next char is '^'
    b = parseXor()
    return a ^ b;
  else
    return a;

The functions for the other operators could be implemented in the same fashion. If you have multiple operators with the same priority you would probably want to handle them in the same function (that's what I normally do).

The parsing function for the operator with the highest priority would call a function for parsing a constant (or variable, if you have not already replaced them with constants).

function parseConstant():
  if next char is '1'
    return 1;
  else if  next char is '0'
    return 0;
  else
    error!

To start parsing you would call the parsing function for the lowest priority operator (parseXor()) and when you are ready you might want to check if the whole string has been parsed. If it hasn't that means the string that you tried to parse had a syntax error (or there is a bug in your implementation). There might be other errors that I don't think about that you might also want to check for.

Now I haven't told you how to implement parentheses but if you get what I've explained so far to work it's not very difficult to add some code to handle parentheses (Hint: you can do it on the same level as the constants).

----------------------------------------------------

I have used this technique before and personally I think it's a relatively simple approach that is both powerful and robust. I have even used it to implement simple scripting languages for my particular needs. One thing that can cause problems however is if you have symbols made up of multiple characters and the individual characters are also valid symbols (e.g. + and +=). This might require some workarounds, or you will have to do proper tokenization before starting to parse so that instead of parsing raw characters you do it token by token (https://en.wikipedia.org/wiki/Lexical_analysis#Tokenization).

[Duthomhas]

Peter87’s recommendation is spot on. It is called “recursive descent parsing”, and is exactly what you need for this assignment.

I also recommend the following three helper functions:

  void error( const std::string & message );
  Print an error and quit

  char accept( std::istream & es, const std::string & acceptable_chars );
  If the next available token (non-whitespace character) is one of the acceptable characters,
  extract it and return it. Otherwise return 0.

  char expect( std::istream & es, const std::string & acceptable_chars );
  Same as accept() but calls error() instead of returning 0.

The es argument is the expression stream, which you should obtain as a string from your input and then manage as an istringstream for each call to your symbolic expression parser. For example:

// This is the top level of our parser -- the function the user calls
// It is also the function the _lowest_ levels of our parser will call
// in order to invoke recursion.
//
// The values[] are the 0 or 1 integer

int eval( std::istream & es, const std::vector<int> & values )
{
  return parseXor( es, values );
}

int eval( const std::string & expression, const std::vector<int> & values )
{
  std::istringstream es( expression );
  return eval( es, values );
}

Good luck!

[satsat111]

Hi,thanks all. I didn't know it would be that complicated, I will try using your suggestions, thanks a lot.

[Duthomhas]

It isn’t all that bad. Before posting answers for questions like these I almost always write up a little program that actually solves it. I did it in under a hundred lines of code with:

  • the 3 functions I recommended to you
  • 1 function to get a terminal value (0 or 1 or lookup the value of A, B, ... E)
  • 4 functions for the operators, one for each level of precedence: (), AND, OR, XOR
  • the 2 “eval” functions I exampled to you above
  • main

That’s only eleven functions, and each one is between one and four lines of code long.


Peter87 actually made a mistake: The functions to parse the operators (parentheses, AND, OR, XOR) should each work using a loop, not an “if”. The last four should be nearly identical, differing only in recognizing the operator symbol and calling the next level of precedence functions. For example:

int parseXor( std::istream & es, const std::vector<int> & values )
{
  int x = parseOr( es, values );  // get the left-hand-side value
  while (accept( es, "^" ))       // get all right-hand-side values...
    x ^= parseOr( es, values );   // ...and apply them to the left-hand-side
  return x;                       // return the final value
}

The only function that actually needs the “values” argument is the terminal parsing function (which you might name parseValue) so that it can look up what a “B” is, for example.

That way in main you can have a loop that just reads the values for A..E and then parse the expression and print the result for as many lines of values you are given for input.

(In a grammar where you have multiple symbols at the same level of precedence the functions get a tiny bit larger. For example, an arithmetic term function would need to handle both addition and subtraction in the same function. Each function exists to handle levels of precedence between operators, and handles all operators with the same level of precedence [and associativity].)

R E C U R S I V E   D E S C E N T

The idea behind RD is to take an EBNF-style expression grammar and turn it into code with relatively simple functions. Your grammar is pretty easy:

    expression  ::= xor
    xor         ::= or ('^' or)*
    or          ::= and ('|' and)*
    and         ::= parentheses ('&' parentheses)*
    parentheses ::= '(' expression ')' | value
    value       ::= '0' | '1' | 'A' | 'B' | 'C' | 'D' | 'E'

The EBNF stuff looks weird, and if you are familiar with regular expressions you will be able to read it easily enough. Things in quotes appear in your input exactly. Anything followed by an asterisk is repeated zero or more times. Things separated by the vertical bar are either-or.

So, a “value” may be the literal symbol 1, or B, etc.

Hopefully you can see how the XOR rule

    xor         ::= or ('^' or)*

translates directly to a little function:

int parseXor( std::istream & es, const std::vector<int> & values )
{
  int x = parseOr( es, values );  // get the left-hand-side value
  while (accept( es, "^" ))       // get all right-hand-side values...
    x ^= parseOr( es, values );   // ...and apply them to the left-hand-side
  return x;                       // return the final value
}

The function is really only complicated because we are carrying some state along as arguments: the current expression stream and the vector of values for 'A'..'F'.

The “terminal” rule/node/function is the one that gets a 0 or 1 value, because it expects there to be a value and nothing else.

On the other end is the top-level “expression” function (which I named eval in my examples), which does nothing more than hand-off to the parse function with the lowest precedence. We do this to make modifying the grammar safe and easy.

Oh, yeah, before I forget, since this is a recursive solution, you will have to provide a forward declaration of the eval function so that parseParentheses can call it.


RD is one of the fundamental concepts in language parsing. You typically encounter this first in a compiler design course, though... I am not sure I would have made this a 101 assignment.

Anyway, let us know if you have further questions. Try to make it work and make sure to google around Recursive Descent.

Good luck!

[seeplus]

As a variation on RDP, convert first to RPN and then stack evaluate. Note minimal expression error checking!

#include <iostream>
#include <string>
#include <stack>
#include <cctype>
#include <iomanip>

using ITR = std::string::iterator;

bool L4(ITR& it, ITR itend, std::string& post);

bool l1(ITR& it, ITR itend, std::string& post) {
	if (it != itend) {
		if (*it == '0' || *it == '1' || (*it >= 'A' && *it <= 'E'))
			post += *it++;
		else if (*it == '(') {
			if (!L4(++it, itend, post))
				return false;

			if (*it != ')')
				return false;

			++it;
		} else
			return false;

		return true;
	}

	return false;
}

bool L2(ITR& it, ITR itend, std::string& post) {
	if (!l1(it, itend, post))
		return false;

	while (*it == '&') {
		const auto op {*it};

		if (!l1(++it, itend, post))
			return false;

		post += op;
	}

	return true;
}

bool L3(ITR& it, ITR itend, std::string& post) {
	if (!L2(it, itend, post))
		return false;

	while (*it == '|') {
		const auto op {*it};

		if (!L2(++it, itend, post))
			return false;

		post += op;
	}

	return true;
}

bool L4(ITR& it, ITR itend, std::string& post) {
	if (!L3(it, itend, post))
		return false;

	while (*it == '^') {
		const auto op {*it};

		if (!L3(++it, itend, post))
			return false;

		post += op;
	}

	return true;
}

bool parse(ITR& it, ITR itend, std::string& post) {
	return L4(it, itend, post) && it == itend;
}

bool eval(const std::string& rpn, const int args[5]) {
	std::stack<int> stk;

	for (unsigned ch : rpn) {
		if (std::isdigit(ch))
			stk.push(ch - '0');
		else if (std::isalpha(ch))
			stk.push(args[ch - 'A']);
		else
			if (stk.size() >= 2) {
				const auto i1 {stk.top()};
				stk.pop();
				const auto i2 {stk.top()};
				stk.pop();

				switch (ch) {
					case '|':
						stk.push(i1 | i2);
						break;

					case '&':
						stk.push(i1 & i2);
						break;

					case '^':
						stk.push(i1 ^ i2);
						break;

					default:
						return (std::cout << "Something went wrong!\n"), 0;
				}
			} else
				return (std::cout << "Something went wrong!\n"), 0;
	}

	if (stk.size() != 1)
		return (std::cout << "Something went wrong!\n"), 0;
	else
		return stk.top();
}

int main() {
	std::string str, rpn;
	unsigned t {};

	int arr[5] {};

	std::getline(std::cin, str);

	ITR it {str.begin()};

	if (!parse(it, str.end(), rpn))
		return (std::cout << "Bad expression\n"), 1;

	std::cin >> t;

	while (t--) {
		std::cin >> arr[0] >> arr[1] >> arr[2] >> arr[3] >> arr[4];
		std::cout << "Evaluates as " << std::boolalpha << eval(rpn, arr) << '\n';
	}
}

A|B
4
0 0 0 0 0
Evaluates as false
1 0 0 0 0
Evaluates as true
0 1 1 1 1
Evaluates as true
1 1 1 1 1
Evaluates as true

[Duthomhas]

I don’t typically recommend Shunting Yard as the first foray into a symbolic expression parser, simply because it has zero error checking ability — which means that extra code (and thought) must be put into doing that first.

But it is a lot of fun!

[satsat111]

Thank you everyone for the detailed suggestion and methods, problem solved:D

[Duthomhas]

Mischief managed?

[seeplus]

@satsat111 - what you should now do is add the ! (not) operator...

[Duthomhas]

I actually have an entire tutorial written out about designing and implementing a full-fledged programming language. The objective to add Infix Expressions is split into two strategies: Recursive Descent and Shunting Yard. (Meaning that the example code divides into two branches at that point — one moving forward with RD and the other with SY.)

Alas, my website is currently down so I cannot share it right now. And my life is a bit of a mess ATM (I’m moving), so I can’t spend any time on it and don’t know when I’ll get it up.

Maybe I’ll see if I can host it on github or something...

...someday...


Anyway, the point I was leading to with that prelude is that that is exactly how I present it. I give a basic grammar that handles basic arithmetic and all but hold your hand writing it. Then I add homework of adding remainder, bit shifts, and unary minus, each which builds upon the previous understanding to test the reader’s understanding and see how minor changes affect things like associativity.

[Peter87]

Duthomhas wrote:

Peter87 actually made a mistake: The functions to parse the operators (parentheses, AND, OR, XOR) should each work using a loop, not an “if”. The last four should be nearly identical, differing only in recognizing the operator symbol and calling the next level of precedence functions.

It was not a mistake. Note that to parse the second operand I called the function on the same priority again. That will accomplish the same thing as the loop.

[Duthomhas]

Oop! Yes, I misread your code.

Dumb ORs and XORs and lotsoflettersXors