using System;

using System.Text.RegularExpressions;

using System.Collections.Generic;

using System.Text;

​

#nullable enable

​

public class Program

{

    public static void Main(string[] args)

    {

        var tokeniser = new Tokeniser("b NOT a c");

        var parser = new Parser();

        var tokens = parser.Shunt(tokeniser);

        var ast = parser.BuildAst(tokens);

        var renderer = new Renderer();

        Console.WriteLine(renderer.Render(ast));

    }

}

​

public class Parser

{

    public INode BuildAst(IEnumerable<IToken> tokens)

    {

        var stack = new Stack<INode>();

​

        foreach (var token in tokens)

        {

            switch (token)

            {

                case VariableToken variable:

                    stack.Push(new UnaryOperatorNode(EqToken.Instance, new VariableNode(variable)));

                    break;

​

                case AndToken:

                case OrToken:

                    if (stack.Count < 2)

                    {

                        throw new Exception($"Expected 2 parameters for operator {token}, got fewer");

                    }

                    stack.Push(new BinaryOperatorNode((OperatorToken)token, stack.Pop(), stack.Pop()));

                    break;

​

                case EqToken:

                    // We treat EQ as a no-op: we'll add it when we add its variable

                    break;

​

                case NotToken:

                    if (stack.Count < 1)

                    {

                        throw new Exception($"Expected 1 parameter for operator {token}, got fewer");

                    }

                    // If we encounter a 'not', we invert the current tree

                    stack.Push(stack.Pop().Invert());

                    break;

            }

        }

        if (stack.Count != 1)

        {

            throw new Exception("Unexpected leftover tokens");

        }

​

        return stack.Pop();

    }

​

    public IEnumerable<IToken> Shunt(Tokeniser tokeniser)

    {

        var operators = new Stack<IToken>();

        bool lastTokenWasVariable = false;

​

        while (tokeniser.Next() is { } token)

        {

            if (lastTokenWasVariable && token is VariableToken or NotToken)

            {

                // A variable after a variable, or a NOT after a variable, has an implicit AND between them

                foreach (var t in ProcessOperator(AndToken.Instance))

                {

                    yield return t;

                }

            }

            switch (token)

            {

                case VariableToken variable:

                    yield return variable;

                    break;

                case OperatorToken op:

                    foreach (var t in ProcessOperator(op))

                    {

                        yield return t;

                    }

                    break;

                case LeftParenToken:

                    operators.Push(token);

                    break;

                case RightParenToken:

                    while (operators.TryPeek(out var peek) && peek is not LeftParenToken)

                    {

                        if (operators.Count == 0)

                        {

                            throw new Exception("Count not find matching '(' for ')'");

                        }

                        operators.Pop();

                        yield return peek;

                    }

                    if (!operators.TryPop(out var pop) || pop is not LeftParenToken)

                    {

                        throw new Exception("Expected a '(' at the top of the operators stack");

                    }

                    break;

            }

            lastTokenWasVariable = token is VariableToken;

        }

​

        while (operators.TryPop(out var op))

        {

            if (op is LeftParenToken)

            {

                throw new Exception("Unexpected '('");

            }

            yield return op;

        }

        IEnumerable<IToken> ProcessOperator(OperatorToken op1)

        {

            while (operators.TryPeek(out var peek) && peek is OperatorToken op2 && (op1.IsLeftAssociative ? op2.Precedence >= op1.Precedence : op2.Precedence > op1.Precedence))

            {

                operators.Pop();

                yield return op2;

            }

            operators.Push(op1);

        }

    }

}

​

public class Tokeniser

{

    private static readonly Regex tokenRegex = new Regex(@"(\(|\)|\w+)\s*");

​

    private readonly string input;

    private int position;

​

    public Tokeniser(string input)

    {

        this.input = input;

    }

​

    public IToken? Next()

    {

        if (position == input.Length)

            return null;

​

        var match = tokenRegex.Match(input, position);

        if (!match.Success || match.Index != position)

        {

            throw new Exception($"Unexpected token at start of '{input.Substring(position)}'");

        }

​

        string token = match.Groups[1].Value;

        position += match.Length;

​

        return token switch

        {

            "(" => LeftParenToken.Instance,

            ")" => RightParenToken.Instance,

            "AND" => AndToken.Instance,

            "OR" => OrToken.Instance,

            "NOT" => NotToken.Instance,

            "EQ" => EqToken.Instance,

            _ => new VariableToken(token),

        };

    }

}

​

public class Renderer

{

    public string Render(INode rootNode)

    {

        var sb = new StringBuilder();

​

        Visit(rootNode);

​

        void Visit(INode node)

        {

            switch (node)

            {

                case BinaryOperatorNode op:

                    VisitWithParens(op.Left);

                    sb.Append($" {op.Operator} ");

                    VisitWithParens(op.Right);

                    break;

​

                case UnaryOperatorNode op:

                    sb.Append($"({op.Operator} ");

                    Visit(op.Child);

                    sb.Append(")");

                    break;

​

                case VariableNode variable:

                    sb.Append(variable.Variable);

                    break;

            }

        }

​

        void VisitWithParens(INode node)

        {

            if (node is BinaryOperatorNode)

            {

                sb.Append("( ");

            }

            Visit(node);

            if (node is BinaryOperatorNode)

            {

                sb.Append(" )");

            }

        }

​

        return sb.ToString();

    }

}

​

public interface IToken

{

}

​

public class LeftParenToken : IToken

{

    public static LeftParenToken Instance { get; } = new LeftParenToken();

    private LeftParenToken() { }

    public override string ToString() => "(";

}

public class RightParenToken : IToken

{

    public static RightParenToken Instance { get; } = new RightParenToken();

    private RightParenToken() { }

    public override string ToString() => ")";

}

public abstract class OperatorToken : IToken

{

    public int Precedence { get; }

    public bool IsLeftAssociative { get; }

    protected OperatorToken(int precedence, bool isLeftAssociative) => (Precedence, IsLeftAssociative) = (precedence, isLeftAssociative);

}

public class AndToken : OperatorToken

{

    public static AndToken Instance { get; } = new AndToken();

    private AndToken() : base(1, true) { }

    public override string ToString() => "AND";

}

public class OrToken : OperatorToken

{

    public static OrToken Instance { get; } = new OrToken();

    private OrToken() : base(1, true) { }

    public override string ToString() => "OR";

}

public class EqToken : OperatorToken

{

    public static EqToken Instance { get; } = new EqToken();

    private EqToken() : base(2, false) { }

    public override string ToString() => "EQ";

}

public class NotToken : OperatorToken

{

    public static NotToken Instance { get; } = new NotToken();

    private NotToken() : base(2, false) { }

    public override string ToString() => "NOT";

}

​

public class VariableToken : IToken

{

    public string Name { get; }

    public VariableToken(string name) => Name = name;

    public override string ToString() => Name;

}

​

public interface INode

{

    INode Invert();

}

​

public class BinaryOperatorNode : INode

{

    public OperatorToken Operator { get; }

    public INode Left { get; }

    public INode Right { get; }

​

    public BinaryOperatorNode(OperatorToken op, INode right, INode left) => (Operator, Right, Left) = (op, right, left);

​

    public INode Invert()

    {

        return Operator switch

        {

            AndToken => new BinaryOperatorNode(OrToken.Instance, Right.Invert(), Left.Invert()),

            OrToken => new BinaryOperatorNode(AndToken.Instance, Right.Invert(), Left.Invert()),

            _ => throw new Exception($"Unexpected binary operator type {Operator}"),

        };

    }

}

​

public class UnaryOperatorNode : INode

{

    public OperatorToken Operator { get; }

    public INode Child { get; }

    public UnaryOperatorNode(OperatorToken op, INode child) => (Operator, Child) = (op, child);

    public INode Invert()

    {

        return Operator switch

        {

            NotToken => new UnaryOperatorNode(EqToken.Instance, Child.Invert()),

            EqToken => new UnaryOperatorNode(NotToken.Instance, Child.Invert()),

            _ => throw new Exception($"Unexpected unary operator type {Operator}"),

        };

    }

}

​

public class VariableNode : INode

{

    public VariableToken Variable { get; }

    public VariableNode(VariableToken variable) => Variable = variable;

​

    public INode Invert()

    {

        return this;

    }

}