TastyPasta

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Perebor
{
   public class Program
    {
        public static string expression = "!X*X +X1 + NOT X AND X OR X && !X || NOT X AND NOT NOT X";
        public static Node Eparser(ref string expression)
        {
            expression = expression.Replace("AND", "*").Replace("OR", "+").Replace("NOT", "!");
            expression = expression.Replace(@"/\", "*").Replace(@"\/", "+").Replace("-", "!");
            expression = expression.Replace("^", "*").Replace("V", "+");
            expression = expression.Replace("&&", "*").Replace("||", "+");
            expression = expression.Replace("&", "*");
            expression = expression.Replace(" ", "");
            Node t = new Node();
            if (expression != "")
                t = E(ref expression);
            return t;
        }
        public static Node E(ref string expression)
        {
            Node t = new Node();
            t = T(ref expression);
            if (expression != "")
                while (expression != "" && (expression[0] == '+'))
                {
                    char op = expression[0];
                    expression = expression.Remove(0, 1);
                    Node t1 = T(ref expression);
                    Node MkNode = new Node(op, null, null, t, t1);
                    t = MkNode;
                }
            return t;
        }
        public static Node T(ref string expression)
        {
            Node t = new Node();
            t = P(ref expression);
            if (expression != "")
                while (expression != "" && expression[0] == '*')
                {
                    char op = expression[0];
                    expression = expression.Remove(0, 1);
                    Node t1 = P(ref expression);
                    Node MkNode = new Node(op, null, null, t, t1);
                    t = MkNode;
                }
            return t;
        }

        public static List<string> varNames = new List<string>();

        public static Node P(ref string expression)
        {
            string name = string.Empty;
            Node t = new Node();

                if (expression[0]==' ')
                {
                    expression = expression.Remove(0, 1);
                }
                if (expression != "" && expression[0] != ' ' && expression[0] != '+'
                        && expression[0] != '*' && expression[0] != '!' && expression[0] != '(' && expression[0] != ')')
                {
                    name += expression[0];
                    expression = expression.Remove(0, 1);
                    while (expression != "" && expression[0] != ' ' && expression[0] != '+'
                        && expression[0] != '*' && expression[0] != '!' && expression[0] != '(' && expression[0] != ')')
                    {
                        name += expression[0];
                        expression = expression.Remove(0, 1);
                    }
                    if (!varNames.Contains(name))
                        varNames.Add(name);
                    Node leaf = new Node(null, name, false, null, null);
                    return leaf;
                }
                else if (expression[0] == '(')
                {
                    expression = expression.Remove(0, 1);
                    t = E(ref expression);
                    if (expression[0] == ')')
                        expression = expression.Remove(0, 1);
                    return t;
                }
                else if (expression[0] == '!')
                {
                    expression = expression.Remove(0, 1);
                    t = P(ref expression);
                    Node not = new Node('!', null, null, t, null);
                    return not;
                }
                else throw new ArgumentOutOfRangeException("Something wrong happened");


        }
        static void Main(string[] args)
        {
            Console.WriteLine(Node.Perebirator(Eparser(ref expression)));
        }
        public class Node
        {
            char? operation;
            bool? value;
            string name;
            Node LeftChild;
            Node RightChild;
            public Node() { }
            public Node(char? inputOper, string inputName, bool? inputVal, Node inputLftChld, Node inputRghtChld)
            {
                operation = inputOper;
                name = inputName;
                value = inputVal;
                LeftChild = inputLftChld;
                RightChild = inputRghtChld;
            }
            public static Node Setter(Node node, string varName, bool value)
            {
                if (node.name == varName)
                    node.value = value;
                if (node.LeftChild != null)
                    Setter(node.LeftChild, varName, value);
                if (node.RightChild != null)
                    Setter(node.RightChild, varName, value);
                return node;
            }
            public static bool Evaluate(Node node)
            {
                if (node.value != null)
                    return (bool)node.value;
                else
                if (node.operation == '+')
                    return Evaluate(node.LeftChild) || Evaluate(node.RightChild);
                else if (node.operation == '*')
                    return Evaluate(node.LeftChild) && Evaluate(node.RightChild);
                else if (node.operation == '!')
                    return !(Evaluate(node.LeftChild));
                else throw new Exception();
            }

            public static bool Perebirator(Node node, int count = 0)
            {
                if (count<varNames.Count)
                {
                   return Perebirator(Setter(node, varNames[count], true), count+1)
                        ||
                   Perebirator(Setter(node, varNames[count], false), count+1);
                }
                return Evaluate(node)==true;

            }
        }
    }
}